利用一个数组实现两个栈是数据结构中的一道经典面试题，那么如何来求解呢？

大多数人为了方便都采取了静态实现方式，但是这种方式不能进行扩容，不够完美。博主利用C++尝试了一下动态实现。

首先，通过了解栈的特点（后进先出），可以想到如下几个方案：

First>>将数组的下标为奇数的位置都插入栈1的元素，数组的下标为偶数的位置都插入栈2的元素。这种方式插入删除时需要利用数组的下标来控制对栈1操作还是栈2操作，这点虽然简单易行。但是，在进行扩容时却需要将两个栈同步扩容，这样下来，就会浪费许多不必要的空间。

Second>>将数组的中间两个位置作为两个栈的栈顶，向数组两边进行插入删除。这种做法虽然可以节省空间，但是试想这样一个场景，如果向后插入的那个栈插入满了，而前面的那个栈没有满，那么我们就要绕到数组的开始去进行插入，这样写起来代码的可读性就不高，而且拷贝构造函数也不好实现，还容易引发一系列不必要的问题。

Third>>最后考虑到的是将数组的开始位置和结束位置作为两个栈的栈底，两个栈均向中间插入删除，当两个栈的栈顶相遇时，进行扩容。拷贝构造时，为了节省空间，将两个栈进行分开拷贝。这样就避免了出现前面提到的问题。

代码实现：

template
     
      class TwoStack{public:	    TwoStack()			:_a(0)			,_top1(0)			,_top2(0)			,_capacity(0)		{		}		~TwoStack()		{			if(_a != NULL)			{				delete [] _a;						}		}		/*TwoStack(const TwoStack
      
       & ts)			:_a(new T[ts._capacity])			,_top1(ts._top1)			,_top2(ts._top2)			,_capacity(ts._capacity)	      {		  	for(size_t i = 0; i< _capacity-1; i++)			{				_a[i] = ts._a[i];			}		}*/		TwoStack( const TwoStack
       
        & ts)			:_a(new T[ ts._capacity -ts._top2 +ts._top1])//size+1			,_top1(ts._top1)			,_top2(_top1)			,_capacity( ts._capacity -ts._top2 +ts._top1)		{			size_t j = ts._capacity - 1;			for(size_t i = 0; i<=_top1; i++)			{				_a[i] = ts._a[i];			}			for(size_t i = _capacity-1; i >_top2; i--,j--)			{				_a[i] = ts._a[j];			}		}		TwoStack
        
         & operator= (TwoStack
         
           ts)		{			_top1 = ts._top1;			_top2 = ts._top2;			_capacity = ts._capacity;			swap(_a,ts._a);			return *this;		}				void Push(const T& x,int choice)		{			_CheckCapacity();			if(choice == 0)			{								_a[_top1++] = x;			}			if(choice ==1)			{				_a[_top2--] = x;			}		}		void Pop(int choice)		{			if(choice == 0)			{				assert(_top1 > 0);							_top1--;			}			if(choice == 1)			{				assert(_top2 <_capacity-1);				_top2++;			}		}		T& Top(int choice)		{			if(choice == 0)			{				assert(_top1 > 0);								return _a[_top1-1];			}			if(choice == 1)			{				assert(_top2 <_capacity-1);				return _a[_top2+1];			}		}		bool Empty(int choice)		{			if(choice == 0)			{				return _top1 == 0;			}			if(choice == 1)			{				return _top2 ==_capacity-1;			}		}		size_t Size(int choice)		{			if(choice == 0)			{				return _top1;			}			if(choice == 1)			{				return _capacity-1-_top2;			}		}		void Print()		{			cout << "栈0为：";			for(size_t i = 0; i<_top1; i++)			{				cout << _a[i] <<" ";			}			cout<
          
           _top2; --j) { cout << _a[j] << " "; } cout <
           
            <
            
             _top2; i--, j--)//反向拷贝 { tmp[i] = _a[j]; } delete [] _a; _a = tmp; _top2 = (_capacity-1) - (oldCapacity-1-_top2);// 最后一个下标-元素个数 } }protected: T* _a; size_t _top1; size_t _top2; size_t _capacity;};
            
           
          
         
        
       
      
     

程序虽然实现了，但是还是存在许多小瑕疵，希望大家指正~~~~~~~~~~