问题描述： 用一个数组实现两个栈 方法一： 将两个栈对应的元素在数组中按照奇偶排列，如：假设栈1按照奇数位排列，栈2按照偶数位排列 这种方法有一种缺陷就是当两个栈的元素相同时就无法按照奇偶进行排列； 方法二： 从中间向两边，栈1向数组的首部移动，栈2向数组的尾部移动，当有任何一个栈增加到首部或者是尾部时数组开始增容； 方法二似乎解决了两个栈元素相同的问题，如果一个栈先到达首部或者尾部，而另外一个还没有到达，但此时就必须增容，这样会造成内存的浪费； 方法三： 要解决内存浪费的问题：我们可以把数组的首部作为一个栈的栈底，数组的尾部可以作为一个另外一个栈的栈底，只有到相遇才会增容，这样会节省空间； 这里我们按照方法三来实现：
template<class T> class TwoStack { public: TwoStack() :_a(NULL) , _top1(0) ,_top2(0) , _capacity(0) { _CheckCapacity(); } void PushStack1(const T&x) { _CheckCapacity(); _a[_top1] = x; ++_top1; } void PushStack2(const T&x) { _CheckCapacity(); _a[_top2] = x; --_top2; } void PopStack1() { if (_top1 > 0) { --_top1; } } void PopStack2() { if (_top2 < _capacity - 1) { ++_top2; } } size_t SizeStack1() { return _top1; } size_t SizeStack2() { return _capacity-1-_top2; } bool EmptyStack1() { return _top1== 0; } bool EmptyStack2() { return _top2 == _capacity - 1; } T& TopStack1() { if (_top1 > 0) { return _a[_top1 - 1]; } } T& TopStack2() { if (_top2 < _capacity - 1) { return _a[_top2 + 1]; } } ~TwoStack() { if (_a != NULL) { delete[] _a; _a = NULL; _top1 = 0; _top2 = 0; _capacity = 0; } } protected: void _CheckCapacity() { if (_a == NULL) { _capacity += 3; _a = new T[_capacity]; _top2 = _capacity - 1; return; } if (_top1 ==_top2) { size_t _oldcapacity = _capacity; size_t _needcapacity = _capacity * 2 ; T*_tmp = new T[_needcapacity]; for (size_t i = 0; i < _top1; ++i) { _tmp[i] = _a[i]; } for (size_t j = _oldcapacity - 1, i = _needcapacity - 1; j> _top2; --j, --i) { _tmp[i] = _a[j]; } delete[]_a; _a = _tmp; _top2 += _needcapacity/2; _capacity = _needcapacity; } } protected: T*_a; size_t _top1;//栈1的栈顶元素 size_t _top2;//栈2的栈顶元素 size_t _capacity;//数组的容量 }; int main() { TwoStack<int> s; s.PushStack1(1); s.PushStack1(2); s.PushStack1(3); s.PushStack1(4); s.PushStack2(1); s.PushStack2(2); s.PushStack2(3); s.PushStack2(4); cout << "SizeStack1?" << s.SizeStack1() << endl; cout << "SizeStack2?" << s.SizeStack2() << endl; while (!s.EmptyStack1()) { cout << s.TopStack1() <<" "; s.PopStack1(); } cout << endl; while (!s.EmptyStack2()) { cout << s.TopStack2() << " "; s.PopStack2(); } cout << endl; system("pause"); return 0; }