以前，我们实现一个栈，轻轻松松，无需考虑太多因素，即可实现。

现在，要求在一个数组里实现两个栈，那么在数组里怎么实现栈呢？

无非就是下标索引，方法也不局限一种，例如：用奇数下标作为栈s1的结构，用偶数作为s2的结构；再者：一前一后的结构，栈s1从前往后，栈s2从后往前。



本人只想到了使用这两中方法实现，当然，这两种方法各有利弊。

第一种方法，倘若其中一个栈只入了一个元素，而另一个入了很多元素，那么会造成内存碎片，但是此方法有利于数组增容；

第二种方法，空间利用率很高，但是不有利于数组增容。

虽然各有利弊，但是实现的机制相同。


在这里，使用第一种方法实现：

#include<iostream>usingnamespacestd;template<classT>classarrayWithTwoStack{public:arrayWithTwoStack(intsize):top1(-1),top2(-1),_size(size){_array=newT[size+1];}~arrayWithTwoStack(){if(_array){delete[]_array;}}public:voidPush(intindex,Tdata){if(_size%2==0){if((top1>_size-2)||(top2>=_size-1)){cout<<"Stackisoverflow!"<<endl;return;}}else{if((top1>_size-1)||(top2>=_size-2)){cout<<"Stackisoverflow!"<<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;}}}TPop(intindex){intret;if(index==0){if(top1<0){return-1;cout<<"Stackisunderflow!"<<endl;}else{ret=_array[top1];top1-=2;}}if(index==1){if(top2<1)//top2从下标为1开始{return-1;cout<<"Satckisunderflow!"<<endl;}else{ret=_array[top2];top2-=2;}}returnret;}Ttop(intindex)//返回栈顶元素{if(index==0&&top1>=0){return_array[top1];}if(index==1&&top2>=1){return_array[top2];}cout<<"NoTop!"<<endl;exit(0);}boolisEmpty(intindex){if(index==0&&top1<0)returnfalse;if(index==1&&top2<1)returnfalse;returntrue;}voidShow(){if(top1<0&&top2<1){cout<<"Stackhasnodata!"<<endl;return;}else{for(inti=0;i<_size;i++)cout<<_array[i]<<"";}cout<<endl;}private:Ttop1;Ttop2;int_size;T*_array;};intmain(){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");return0;}

若有纰漏，欢迎指正。