# 在一個數組中實現兩個堆棧 > 原文： [https://www.geeksforgeeks.org/implement-two-stacks-in-an-array/](https://www.geeksforgeeks.org/implement-two-stacks-in-an-array/) 創建代表兩個堆棧的數據結構 *twoStacks* 。 *twoStacks 的實現*應該僅使用一個數組，即兩個堆棧都應使用相同的數組來存儲元素。 *twoStacks* 必須支持以下功能。 push1（int x）– >將 x 推送到第一堆棧 push2（int x）– >將 x 推送到第二堆棧 pop1（）– >從第一個堆棧中彈出一個元素，然后返回彈出的元素 pop2（）– >從第二個堆棧中彈出一個元素，然后返回彈出的元素 *twoStack* 的實現應節省空間。 **方法 1（將空間分成兩半）** 實現兩個堆棧的簡單方法是將數組分成兩半，并將一半的一半空間分配給兩個堆棧，即使用 arr [0 ]到 arr [n / 2]（對于 stack1），以及 arr [（n / 2）+1]到 arr [n-1]（對于 stack2），其中 arr []是要用于實現兩個堆棧的數組，數組的大小為 。 這種方法的問題是無法有效利用數組空間。 即使 arr []中有可用空間，堆棧推入操作也可能導致堆棧溢出。 例如，假設數組大小為 6，我們將 3 個元素壓入 stack1，而不壓入第二個 stack2。 當我們將第 4 個元素壓入 stack1 時，即使我們在數組中還有 3 個元素的空間，也會有溢出。 ``` #include <iostream> #include <stdlib.h> using namespace std; class twoStacks { ????int* arr; ????int size; ????int top1, top2; public: ????// Constructor ????twoStacks(int n) ????{ ????????size = n; ????????arr = new int[n]; ????????top1 = n / 2 + 1; ????????top2 = n / 2; ????} ????// Method to push an element x to stack1 ????void push1(int x) ????{ ????????// There is at least one empty ????????// space for new element ????????if (top1 > 0) { ????????????top1--; ????????????arr[top1] = x; ????????} ????????else { ????????????cout << "Stack Overflow" ?????????????????<< " By element :" << x << endl; ????????????return; ????????} ????} ????// Method to push an element ????// x to stack2 ????void push2(int x) ????{ ????????// There is at least one empty ????????// space for new element ????????if (top2 < size - 1) { ????????????top2++; ????????????arr[top2] = x; ????????} ????????else { ????????????cout << "Stack Overflow" ?????????????????<< " By element :" << x << endl; ????????????return; ????????} ????} ????// Method to pop an element from first stack ????int pop1() ????{ ????????if (top1 <= size / 2) { ????????????int x = arr[top1]; ????????????top1++; ????????????return x; ????????} ????????else { ????????????cout << "Stack UnderFlow"; ????????????exit(1); ????????} ????} ????// Method to pop an element ????// from second stack ????int pop2() ????{ ????????if (top2 >= size / 2 + 1) { ????????????int x = arr[top2]; ????????????top2--; ????????????return x; ????????} ????????else { ????????????cout << "Stack UnderFlow"; ????????????exit(1); ????????} ????} }; /* Driver program to test twStacks class */ int main() { ????twoStacks ts(5); ????ts.push1(5); ????ts.push2(10); ????ts.push2(15); ????ts.push1(11); ????ts.push2(7); ????cout << "Popped element from stack1 is " ?????????<< " : " << ts.pop1() ?????????<< endl; ????ts.push2(40); ????cout << "\nPopped element from stack2 is " ?????????<< ": " << ts.pop2() ?????????<< endl; ????return 0; } ``` **輸出**： ``` Stack Overflow By element :7 Popped element from stack1 is : 11 Stack Overflow By element :40 Popped element from stack2 is : 15 ``` **復雜度分析**： * **時間復雜度**： * **推動操作**：`O(1)` * **彈出操作**：`O(1)` * **輔助空間**：`O(n)`。 這樣使用數組來實現堆棧。 這不是如上所述的空間優化方法。 **方法 2（節省空間的實現）** 此方法有效地利用了可用空間。 如果 arr []中有可用空間，則不會導致溢出。 這個想法是從 arr []的兩個極端角開始兩個堆棧。 stack1 從最左邊的元素開始，stack1 中的第一個元素被推入索引 0。stack2 從最右邊的角開始，stack2 中的第一個元素被推入索引（n-1）。 兩個堆疊都沿相反的方向生長（或收縮）。 要檢查溢出，我們需要檢查的是兩個堆棧的頂部元素之間的空間。 此檢查在下面的代碼中突出顯示。 ## C++ ```cpp #include <iostream> #include <stdlib.h> using namespace std; class twoStacks { ????int* arr; ????int size; ????int top1, top2; public: ????twoStacks(int n) // constructor ????{ ????????size = n; ????????arr = new int[n]; ????????top1 = -1; ????????top2 = size; ????} ????// Method to push an element x to stack1 ????void push1(int x) ????{ ????????// There is at least one empty space for new element ????????if (top1 < top2 - 1) { ????????????top1++; ????????????arr[top1] = x; ????????} ????????else { ????????????cout << "Stack Overflow"; ????????????exit(1); ????????} ????} ????// Method to push an element x to stack2 ????void push2(int x) ????{ ????????// There is at least one empty ????????// space for new element ????????if (top1 < top2 - 1) { ????????????top2--; ????????????arr[top2] = x; ????????} ????????else { ????????????cout << "Stack Overflow"; ????????????exit(1); ????????} ????} ????// Method to pop an element from first stack ????int pop1() ????{ ????????if (top1 >= 0) { ????????????int x = arr[top1]; ????????????top1--; ????????????return x; ????????} ????????else { ????????????cout << "Stack UnderFlow"; ????????????exit(1); ????????} ????} ????// Method to pop an element from second stack ????int pop2() ????{ ????????if (top2 < size) { ????????????int x = arr[top2]; ????????????top2++; ????????????return x; ????????} ????????else { ????????????cout << "Stack UnderFlow"; ????????????exit(1); ????????} ????} }; /* Driver program to test twStacks class */ int main() { ????twoStacks ts(5); ????ts.push1(5); ????ts.push2(10); ????ts.push2(15); ????ts.push1(11); ????ts.push2(7); ????cout << "Popped element from stack1 is " ?????????<< ts.pop1(); ????ts.push2(40); ????cout << "\nPopped element from stack2 is " ?????????<< ts.pop2(); ????return 0; } ```