您好,登錄后才能下訂單哦!
以前,我們實現一個棧,輕輕松松,無需考慮太多因素,即可實現。
現在,要求在一個數組里實現兩個棧,那么在數組里怎么實現棧呢?
無非就是下標索引,方法也不局限一種,例如:用奇數下標作為棧s1的結構,用偶數作為s2的結構;再者:一前一后的結構,棧s1從前往后,棧s2從后往前。
本人只想到了使用這兩中方法實現,當然,這兩種方法各有利弊。
第一種方法,倘若其中一個棧只入了一個元素,而另一個入了很多元素,那么會造成內存碎片,但是此方法有利于數組增容;
第二種方法,空間利用率很高,但是不有利于數組增容。
雖然各有利弊,但是實現的機制相同。
在這里,使用第一種方法實現:
#include <iostream> using namespace std; template <class T> class arrayWithTwoStack { public: arrayWithTwoStack(int size) : top1(-1) , top2(-1) , _size(size) { _array = new T[size + 1]; } ~arrayWithTwoStack() { if (_array) { delete[] _array; } } public: void Push(int index, T data) { if (_size % 2 == 0) { if ((top1 > _size - 2) || (top2 >= _size - 1)) { cout << "Stack is overflow!" << endl; return; } } else { if ((top1 > _size - 1) || (top2 >= _size - 2)) { cout << "Stack is overflow!" << endl; return; } } 0是一號棧, 1是二號棧 if (index == 0) { if (top1 == -1) { top1 = 0; _array[top1] = data; } else { top1 += 2; _array[top1] = data; } } if (index == 1) { if (top2 == -1) { top2 = 1; _array[top2] = data; } else { top2 += 2; _array[top2] = data; } } } T Pop(int index) { int ret; if (index == 0) { if (top1 < 0) { return -1; cout << "Stack is underflow!" << endl; } else { ret = _array[top1]; top1 -= 2; } } if (index == 1) { if (top2 < 1) // top2從下標為1開始 { return -1; cout << "Satck is underflow!" << endl; } else { ret = _array[top2]; top2 -= 2; } } return ret; } T top(int index) // 返回棧頂元素 { if (index == 0 && top1 >= 0) { return _array[top1]; } if (index == 1 && top2 >= 1) { return _array[top2]; } cout << "No Top!" << endl; exit(0); } bool isEmpty(int index) { if (index == 0 && top1 < 0) return false; if (index == 1 && top2 < 1) return false; return true; } void Show() { if (top1 < 0 && top2 < 1) { cout << "Stack has no data!" << endl; return; } else { for (int i = 0; i < _size; i++) cout << _array[i] << " "; } cout << endl; } private: T top1; T top2; int _size; T* _array; }; int main() { arrayWithTwoStack<int> s(10); s.Push(0, 0); s.Push(0, 2); s.Push(0, 4); s.Push(1, 1); s.Push(1, 3); s.Push(1, 5); s.Push(1, 7); s.Push(0, 6); s.Push(0, 8); s.Push(1, 9); s.Push(0, 10); s.Show(); cout << s.Pop(0) << " "; cout << s.Pop(0) << " "; cout << s.Pop(0) << " "; cout << s.Pop(0) << endl; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << endl; cout << s.top(0) << endl; cout << s.top(1) << endl; s.Pop(0); cout << (s.isEmpty(0) ? "Yes" : "No") << endl; cout << (s.isEmpty(1) ? "Yes" : "No") << endl; system("pause"); return 0; }
若有紕漏,歡迎指正。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。