题目：

一个数组A[1..n]来实现两个栈，使得两个栈中的元素总和不到n时，两个都不会发生上溯。

思路（1）：

创建一个数组，分别从两边开始，依次往中间走。

思路（2）：

创建一个数组，一个走奇数位，一个走偶数位。

//奇偶方式#define_CRT_SECURE_NO_WARNINGS#include<iostream>usingnamespacestd;template<classT>classTwoStack{public:TwoStack(intsize):_top1(-1),_top2(-1),_len(size){_arr=newT[size];}~TwoStack(){if(_arr){delete[]_arr;}}voidPush(intindex,intdata);TPop(intindex);boolIsEmpty(intindex);voidDisp();TTop(intindex);private:int_top1;int_top2;int_len;T*_arr;};template<classT>voidTwoStack<T>::Push(intindex,intdata){//if(_len%2==0)//{//if(_top1>_len-2||_top2>=_len-1)//{//cout<<"overflow"<<endl;//return;//}//}//else//{//if(_top1>_len||_top2>=_len-2)//{//cout<<"overflow"<<endl;//return;//}//}intflag=_len%2;if(index==0){if(flag==0){if(_top1>=_len-2){cout<<"Stack1overflow"<<endl;return;}}if(flag==1){if(_top1>=_len-1){cout<<"overflow"<<endl;return;}}////////////////////////////if(_top1==-1){_top1=0;_arr[_top1]=data;}else{_top1+=2;_arr[_top1]=data;}}/////////////////////////////////////////////////////////else{if(flag==0){if(_top2>=_len-2){cout<<"Stack2overflow"<<endl;return;}}if(flag==1){if(_top2>=_len-1){cout<<"overflow"<<endl;return;}}///////////////if(_top2==-1){_top2=1;_arr[_top2]=data;}else{_top2+=2;_arr[_top2]=data;}}}template<classT>TTwoStack<T>::Pop(intindex){intret;if(index==0){if(_top1<0){cout<<"Stack1isnull"<<endl;return-1;}else{ret=_arr[_top1];_top1-=2;}}else{if(_top2<1){cout<<"Stack2isnull"<<endl;return-1;}else{ret=_arr[_top2];_top2-=2;}}returnret;}template<classT>boolTwoStack<T>::IsEmpty(intindex){if(index==0&&_top1<0)returntrue;if(index==1&&_top2<0)returntrue;returnfalse;}template<classT>voidTwoStack<T>::Disp(){{for(inti=0;i<_len;i++){cout<<_arr[i]<<"";}}}template<classT>TTwoStack<T>::Top(intindex){if(0==index&&_top1>=0){return_arr[_top1];}if(1==index&&_top2>=1){return_arr[_top2];}cout<<"NOTOP"<<endl;exit(0);}voidtest1(){TwoStack<int>s(10);s.Push(0,1);s.Push(0,2);s.Push(0,3);s.Push(0,4);s.Push(0,5);//s.Push(0,5);s.Push(1,6);s.Push(1,7);s.Push(1,8);s.Push(1,9);s.Push(1,10);//s.Push(1,10);//cout<<s.Top(1);//cout<<s.IsEmpty(0);s.Disp();}voidtest2(){TwoStack<int>s(10);s.Push(0,1);s.Push(0,2);s.Push(0,3);s.Push(0,4);s.Push(0,5);s.Push(1,6);s.Push(1,7);s.Push(1,8);s.Push(1,9);s.Push(1,10);cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";//cout<<s.Top(1);}intmain(){test1();test2();system("pause");return0;}

一前一后向中间走：

#define_CRT_SECURE_NO_WARNINGS#include<iostream>usingnamespacestd;template<classT>classTwoStack{public:TwoStack(intsize):_top1(-1),_top2(size),_len(size){_arr=newT[size];}~TwoStack(){if(_arr){delete[]_arr;}}voidPush(intindex,intdata);TPop(intindex);boolIsEmpty(intindex);voidDisp();TTop(intindex);private:int_top1;int_top2;int_len;T*_arr;};template<classT>voidTwoStack<T>::Push(intindex,intdata){if(_top1>=_top2-1){cout<<"Stackisoverflow"<<endl;return;}if(index==0){_top1++;_arr[_top1]=data;}else{_top2--;_arr[_top2]=data;}}template<classT>TTwoStack<T>::Pop(intindex){intret;if(index==0){if(_top1<0){cout<<"Stack1isnull"<<endl;return-1;}else{ret=_arr[_top1];_top1--;}}else{if(_top2>_len){cout<<"Stack2isnull"<<endl;return-1;}else{ret=_arr[_top2];_top2++;}}returnret;}template<classT>boolTwoStack<T>::IsEmpty(intindex){if(index==0&&_top1<0)returntrue;if(index==1&&_top2>=_len)returntrue;returnfalse;}template<classT>voidTwoStack<T>::Disp(){{for(inti=0;i<_len;i++){cout<<_arr[i]<<"";}}}template<classT>TTwoStack<T>::Top(intindex){if(0==index&&_top1>=0){return_arr[_top1];}if(1==index&&_top2<_len){return_arr[_top2];}cout<<"NOTOP"<<endl;exit(0);}voidtest1(){TwoStack<int>s(10);s.Push(0,1);s.Push(0,2);s.Push(0,3);s.Push(0,4);s.Push(0,5);//s.Push(0,5);s.Push(1,6);s.Push(1,7);s.Push(1,8);s.Push(1,9);s.Push(1,10);//s.Push(1,10);s.Disp();//cout<<s.IsEmpty(1);}voidtest2(){TwoStack<int>s(10);s.Push(0,1);s.Push(0,2);s.Push(0,3);s.Push(0,4);s.Push(0,5);s.Push(1,6);s.Push(1,7);s.Push(1,8);s.Push(1,9);s.Push(1,10);//cout<<s.Top(1);cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";//cout<<s.IsEmpty(0);}intmain(){test1();//test2();system("pause");return0;}动态实现增长：#define_CRT_SECURE_NO_WARNINGS#include<iostream>usingnamespacestd;template<classT>classTwoStack{public:TwoStack():_top1(-1),_top2(-1),_len(0),_arr(NULL),_capacity(0){}~TwoStack(){if(_arr){delete[]_arr;}}voidPush(intindex,intdata);TPop(intindex);boolIsEmpty(intindex);voidDisp();TTop(intindex);voidIncreaseCapcity();private:int_top1;int_top2;int_len;T*_arr;int_capacity;};template<classT>voidTwoStack<T>::IncreaseCapcity(){inttop1=_top1;inttop2=_top2;intsize=_capacity;_capacity=_len*2+3;intcapacity=_len*2+3;intnewlen=capacity;T*tmp=newT[_capacity];if(_arr!=NULL){for(inti=0;i<=top1;i++){tmp[i]=_arr[i];}for(intj=top1+1;j<size;j++){tmp[--capacity]=_arr[--_len];--newlen;}}if(_arr!=NULL){delete[]_arr;}_arr=tmp;_len=newlen;_top2=_len;}template<classT>voidTwoStack<T>::Push(intindex,intdata){if(_top1>=_top2-1){IncreaseCapcity();}if(index==0){_top1++;_arr[_top1]=data;}else{_top2--;_arr[_top2]=data;}}template<classT>TTwoStack<T>::Pop(intindex){intret;if(index==0){if(_top1<0){cout<<"Stack1isnull"<<endl;return-1;}else{ret=_arr[_top1];_top1--;}}else{if(_top2>_len){cout<<"Stack2isnull"<<endl;return-1;}else{ret=_arr[_top2];_top2++;}}returnret;}template<classT>boolTwoStack<T>::IsEmpty(intindex){if(index==0&&_top1<0)returntrue;if(index==1&&_top2>=_len)returntrue;returnfalse;}template<classT>voidTwoStack<T>::Disp(){{for(inti=0;i<_capacity;i++){cout<<_arr[i]<<"";}}}template<classT>TTwoStack<T>::Top(intindex){if(0==index&&_top1>=0){return_arr[_top1];}if(1==index&&_top2<_len){return_arr[_top2];}cout<<"NOTOP"<<endl;exit(0);}voidtest1(){TwoStack<int>s;s.Push(0,1);s.Push(0,2);s.Push(0,3);s.Push(0,4);s.Push(0,5);//s.Push(0,5);//cout<<s.Pop(0)<<"";//cout<<s.Pop(0)<<"";//cout<<s.Pop(0)<<"";//cout<<s.Pop(0)<<"";//cout<<s.Pop(0)<<"";s.Push(1,6);s.Push(1,7);s.Push(1,8);s.Push(1,9);s.Push(1,10);//s.Push(1,10);s.Disp();//cout<<s.IsEmpty(1);}voidtest2(){TwoStack<int>s;s.Push(0,1);s.Push(0,2);s.Push(0,3);s.Push(0,4);s.Push(0,5);s.Push(1,6);s.Push(1,7);s.Push(1,8);s.Push(1,9);s.Push(1,10);//cout<<s.Top(1);cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(0)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";cout<<s.Pop(1)<<"";//cout<<s.IsEmpty(0);}intmain(){test1();//test2();system("pause");return0;}