【數(shù)據(jù)結(jié)構(gòu)】 一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧【面試】

以前，我們實(shí)現(xiàn)一個(gè)棧，輕輕松松，無需考慮太多因素，即可實(shí)現(xiàn)。

現(xiàn)在，要求在一個(gè)數(shù)組里實(shí)現(xiàn)兩個(gè)棧，那么在數(shù)組里怎么實(shí)現(xiàn)棧呢？

無非就是下標(biāo)索引，方法也不局限一種，例如：用奇數(shù)下標(biāo)作為棧s1的結(jié)構(gòu)，用偶數(shù)作為s2的結(jié)構(gòu)；再者：一前一后的結(jié)構(gòu)，棧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是一號(hào)棧， 1是二號(hào)棧         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從下標(biāo)為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; }

若有紕漏，歡迎指正。