資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學僅用一種資料結構實現多棧 (K 個棧)
動態多棧是一種優秀的資料結構，它能夠儲存多個棧中的元素，並且棧的數量可以動態變化。使用單一資料結構實現 K 個棧可能是一項艱鉅的任務。在本教程中，我們將探討兩種使用 C++ 實現動態多棧 (K 個棧) 的不同方法。第一種方法使用一個數組來儲存元素，以及另外兩個陣列來跟蹤棧的頂部和下一個索引。第二種方法使用節點向量來儲存元素，以及一個向量來跟蹤每個棧的頭部。
本文將重點介紹如何使用 C++ 中的一種資料結構來實現動態多棧。
方法
方法 1 − 使用陣列儲存資料結構的元素，並使用兩個輔助陣列儲存每個棧的頂部元素和陣列中下一個可用槽的索引。
方法 2 − 使用雙向連結串列儲存資料結構的元素，並使用向量儲存每個棧的頭節點。
語法
給定的語法是在 C++ 中宣告名為 KStacks 的類的宣告。該類具有以下成員函式或方法：
一個建構函式方法 KStacks，它接受兩個引數 k 和 n。
一個名為 push 的方法，它接受兩個引數 item 和 sn，用於將元素插入到棧 sn 中。
一個名為 pop 的方法，它接受單個引數 sn，用於從棧 sn 中移除元素。
一個名為 is_empty 的方法，它接受單個引數 sn，並返回一個布林值，指示棧 sn 是否為空。
一個名為 is_full 的方法，它返回一個布林值，指示整個資料結構是否已滿。
class KStacks {
public:
KStacks(int k, int n); // Constructor
void push(int item, int sn); // Insert an element into stack 'sn'
int pop(int sn); // Remove an element from stack 'sn'
bool is_empty(int sn); // Check if stack 'sn' is empty
bool is_full(); // Check if the entire data structure is full
};
演算法
以下是使用單個數據結構實現 K 棧動態多包的演算法：
步驟 1 − 從建立一個包含大小為 n 的陣列（用於儲存元素）以及兩個大小為 k 的輔助陣列的資料結構開始。一個數組將儲存每個棧的頂部元素的資訊，而另一個數組將跟蹤主陣列中的下一個可用索引。
步驟 2 − 接下來，我們使用 -1 和 0 值呼叫父陣列及其對應的陣列。
步驟 3 − 使用 cart() 函式，我們可以將物件新增到特定棧中。此函式需要兩個輸入：要新增的專案和組號。在新增專案之前，push() 函式透過將下一個可用索引值與 n 進行比較來檢查資料結構是否已滿。如果有空間，則將專案新增到下一個可用索引，並更新下一個可用索引的值。
步驟 4 − pop() 函式用於從特定棧中移除專案，其引數為組號。pop() 函式透過將父陣列值與 -1 進行比較來檢查棧是否為空。如果棧不為空，則 pop() 函式會從棧中移除頂部元素，並將父陣列值更新為指向新的頂部元素。
步驟 5 − 要檢查特定棧是否為空，我們使用 is_empty() 函式，其引數為組號。此函式檢查父陣列值是否等於 -1。
步驟 6 − 要檢查所有棧是否已滿，我們使用 is_full() 函式，該函式檢查下一個可用索引值是否等於 n。
方法 1
我們將採用一種方法，該方法使用一個數組來保留元素，以及另外兩個陣列來監視棧的頂部和後續索引。雖然這是一個簡單有效的解決方案，但它需要預定義預定的棧數。
以下是相同的程式程式碼。
示例
該程式碼表示 K 棧資料結構的實現，它是棧資料結構的動態解釋，允許在單個數組中容納多個棧。
KStacks 類包含三個成員變數：
arr − 一個用作所有棧的元素儲存的陣列。
top − 一個用作每個棧頂部的儲存的陣列。
next − 一個用作陣列中下一個可用位置的儲存的陣列。
push − 將元素插入到指定的棧中。
pop − 從指定的棧中移除元素。
is_empty − 驗證指定的棧是否為空。
is_full − 驗證陣列是否完全被佔用。
在主函式中，生成 KStacks 類的例項，並以棧數和陣列大小作為輸入引數。然後，元素被推入三個不同的棧中。最後，從每個棧中移除頂部元素並顯示。
#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
我們將採用一種方法，其中將使用節點向量來儲存元素。這種方法將由一個向量補充，該向量用於維護每個棧的頭部。我們的方法被證明是一個更靈活的解決方案，它可以容納數量發生動態變化的棧。但是，這種方法可能會帶來更大的記憶體負擔，並帶來更多開銷成本。
示例 2
該程式碼構成一個 C++ 程式，它實現了名為“KStacks”的資料架構。這種資料結構透過應用稱為“固定劃分”的方法，允許在單個數組中儲存多個棧。
“KStacks”類包含一系列成員函式，包括“push”、“pop”、“is_empty”和“is_full”。“push”操作允許將專案新增到指定的棧中，“pop”函式則從指定的棧中刪除頂部專案。
“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++ 中的單個數據結構建立動態多棧的不同方法。這兩種方法都有其優點和缺點，選擇哪種方法將取決於問題的具體需求。
2000+ 瀏覽量
