1 つのデータ構造を使用して複数のスタック (K 個のスタック) を実装します
- WBOY転載
- 2023-09-11 13:05:08688ブラウズ
動的マルチスタックは、要素を複数のスタックに格納できる優れたデータ構造であり、スタックの数は常に変化します。 1 つのデータ構造のみを使用して K スタックを実装するのは、困難な作業になる可能性があります。このチュートリアルでは、C を使用して動的マルチスタック (K スタック) を実行する 2 つの異なる方法を検討します。最初の方法では、要素を格納するために配列を使用し、スタックの先頭と次のインデックスを監視するために 2 つの追加の配列を使用します。 2 番目の方法では、ノード ベクトルを使用して要素を格納し、ベクトルを使用して各スタックの先頭を追跡します。
この記事では、C でデータ構造を使用して動的なマルチスタックを実行する方法に焦点を当てます。
＃＃＃方法＃＃＃- 方法 1
- 配列を使用してデータ構造の要素を格納し、2 つの補助配列を使用して各スタックの最上位要素と次に使用可能な空のスロットのインデックスを格納します。配列。
- 方法 2
- 二重リンク リストを使用してデータ構造の要素を格納し、ベクトルを使用して各スタックのヘッド ノードを格納します。
＃＃＃文法＃＃＃ 指定された構文は、C で KStacks という名前のクラスを宣言することです。このクラスには次のメンバー関数またはメソッドがあります-
コンストラクター メソッド KStacks。2 つのパラメーター k と n を受け取ります。
push という名前のメソッドは、item と sn の 2 つのパラメーターを受け入れ、要素をスタック sn に挿入するために使用されます。
pop という名前のメソッド。パラメータ sn を受け取り、スタック sn から要素を削除するために使用されます。
is_empty という名前のメソッドは、単一のパラメーター sn を受け取り、スタック sn が空かどうかを示すブール値を返します。
is_full という名前のメソッド。データ構造全体がいっぱいかどうかを示すブール値を返します。
-
リーリー
＃＃＃アルゴリズム＃＃＃
以下は、単一のデータ構造を使用して K ヒープの動的複数バックパックを実装するためのアルゴリズムです。
ステップ 1
- まず、要素を格納するためのサイズ n の配列と、サイズ k の 2 つの補助配列を含むデータ構造を作成します。 1 つの配列には各スタックの最上位の要素に関する情報が格納され、もう 1 つの配列はメイン配列で次に使用可能なインデックスを追跡します。-
ステップ 2 - 次に、親配列とそれに対応する配列を値 -1 と 0 で呼び出します。
-
ステップ 3 - cart() 関数を使用して、オブジェクトを特定のスタックに追加できます。この関数には、追加する項目とグループ番号の 2 つの入力が必要です。項目を追加する前に、push() 関数は、次に利用可能なインデックス値を n と比較することによって、データ構造がいっぱいかどうかをチェックします。まだスペースがある場合、項目は次に利用可能なインデックスに追加され、次に利用可能なインデックスの値が更新されます。
-
ステップ 4 - Pop() 関数は、引数としてグループ番号を受け取り、特定のスタックから項目を削除するために使用されます。 Pop() 関数は、親配列の値を -1 と比較することによって、スタックが空かどうかをチェックします。スタックが空でない場合、pop() 関数はスタックから最上位の要素を削除し、新しい最上位の要素を指すように親配列の値を更新します。
-
ステップ 5 - 特定のスタックが空かどうかを確認するには、is_empty() 関数を使用し、グループ番号をパラメータとして受け取ります。この関数は、親配列の値が -1 に等しいかどうかをチェックします。
-
ステップ 6 - すべてのスタックがいっぱいかどうかを確認するには、次に利用可能なインデックス値が n に等しいかどうかを確認する is_full() 関数を使用します。
- 方法 1
配列を使用して要素を保持し、さらに 2 つの追加の配列を使用してスタックの最上位および後続のインデックスを監視するアプローチを採用します。これはシンプルで効果的なソリューションですが、事前に所定の数のスタックを定義する必要があります。
以下は同じプログラムコードです。
＃＃＃例＃＃＃
KStacks クラスには 3 つのメンバー変数が含まれています -
arr
-すべてのスタック要素として保存される配列。- top
- -各スタックの上部でストレージとして使用される配列。
- -配列内の次に使用可能な位置を格納するために使用される配列。
- -指定されたスタックに要素を挿入します。
- -指定されたスタックから要素を削除します。
- -指定されたスタックが空かどうかを検証します。
- - アレイが完全に占有されていることを確認します。
main 関数では、スタックの数と配列のサイズを入力パラメーターとして使用して、KStacks クラスのインスタンスが生成されます。次に、要素は 3 つの異なるスタックにプッシュされます。最後に、各スタックの最上位要素を削除して表示します。
#include <iostream>
#include <vector>
#include<climits>
using namespace std;
class KStacks {
private:
int *arr;
int *top;
int *next;
int n, k;
public:
KStacks(int k, int n) {
this->k = k;
this->n = n;
arr = new int[n];
top = new int[k];
next = new int[n];
for (int i = 0; i < k; i++)
top[i] = -1;
for (int i = 0; i < n - 1; i++)
next[i] = i + 1;
next[n - 1] = -1;
}
void push(int item, int sn) {
if (is_full()) {
cout << "Stack Overflow\n";
return;
}
int i = next[sn];
next[sn] = top[sn];
top[sn] = i;
arr[i] = item;
}
int pop(int sn) {
if (is_empty(sn)) {
cout << "Stack Underflow\n";
return INT_MAX;
}
int i = top[sn];
top[sn] = next[i];
next[i] = i;
return arr[i];
}
bool is_empty(int sn) {
return top[sn] == -1;
}
bool is_full() {
return next[0] == -1;
}
};
int main() {
KStacks ks(3, 10);
ks.push(15, 2);
ks.push(45, 2);
ks.push(17, 1);
ks.push(49, 1);
ks.push(39, 1);
ks.push(11, 0);
ks.push(9, 0);
ks.push(7, 0);
cout << "Popped element from stack 2: " << ks.pop(2) << endl;
cout << "Popped element from stack 1: " << ks.pop(1) << endl;
cout << "Popped element from stack 0: " << ks.pop(0) << endl;
return 0;
}
输出
Stack Overflow Stack Overflow Popped element from stack 2: Stack Underflow 2147483647 Popped element from stack 1: 39 Popped element from stack 0: 11
方法二
我们将采用一种方法，其中使用节点向量来存储元素。这种方法应该由一个用于维护每个堆栈头部的向量来补充。事实证明，我们的方法是一种更灵活的解决方案，可以容纳经历动态变化的可变数量的堆栈。然而，这种方法可能会带来更重的内存负担并带来更多的开销。
示例 2
该代码构成了一个 C++ 程序，该程序实现了称为“KStacks”的数据架构。这种数据结构通过应用一种称为“固定划分”的方法，可以在单个数组中存储多个堆栈。
“KStacks”类包含一系列成员函数，包括“push”、“pop”、“is_empty”和“is_full”。 “推入”操作允许将项目添加到指定的堆栈，而“弹出”功能则从指定的堆栈中消除顶部项目。
如果指定的堆栈未被占用，则“is_empty”函数返回true，如果所有堆栈都完全被占用，则“is_full”函数返回true。在主函数中，建立了三个容量为10的堆栈，并从每个堆栈中推入和弹出项目。最终，弹出的项目将显示在控制台上。
代码
#include <iostream>
#include <vector>
#include<climits>
using namespace std;
class Node {
public:
int data;
int prev;
int next;
};
class KStacks {
private:
vector<Node> arr;
vector<int> head;
int n, k;
int free;
public:
KStacks(int k, int n) {
this->k = k;
this->n = n;
arr.resize(n);
head.resize(k, -1);
free = 0;
for (int i = 0; i < n - 1; i++)
arr[i].next = i + 1;
arr[n - 1].next = -1;
}
void push(int item, int sn) {
if (is_full()) {
cout << "Stack Overflow\n";
return;
}
int i = free;
free = arr[i].next;
arr[i].data = item;
arr[i].prev = head[sn];
arr[i].next = -1;
if (head[sn] != -1)
arr[head[sn]].next = i;
head[sn] = i;
}
int pop(int sn) {
if (is_empty(sn)) {
cout << "Stack Underflow\n";
return INT_MAX;
}
int i = head[sn];
head[sn] = arr[i].prev;
if (head[sn] != -1)
arr[head[sn]].next = -1;
arr[i].next = free;
free = i;
return arr[i].data;
}
bool is_empty(int sn) {
return head[sn] == -1;
}
bool is_full() {
return free == -1;
}
};
int main() {
KStacks ks(3, 10);
ks.push(15, 2);
ks.push(45, 2);
ks.push(17, 1);
ks.push(49, 1);
ks.push(39, 1);
ks.push(11, 0);
ks.push(9, 0);
ks.push(7, 0);
cout << "Popped element from stack 2: " << ks.pop(2) <<endl;
cout << "Popped element from stack 1: " << ks.pop(1) <<endl;
cout << "Popped element from stack 0: " << ks.pop(0) <<endl;
return 0;
}
输出
Popped element from stack 2: 45 Popped element from stack 1: 39 Popped element from stack 0: 7
结论
在本文中，我们讨论了使用 C++ 中的单个数据结构创建动态多堆栈的两种不同方法。两种方法都有其优点和缺点，选择使用哪一种方法将取决于当前问题的具体需求。
以上が1 つのデータ構造を使用して複数のスタック (K 個のスタック) を実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。