首先呢，偶们先来回顾一下栈和队列的特征：

栈呢，只能在末端上进行操作，具有先进后出的特点。

队列呢，只能在队头删除，队尾插入，具有先进先出的特点。

偶们应该利用栈和队列的特征来解决一下几个问题：

1.使用两个栈实现一个队列

2.使用两个队列实现一个栈

3.元素出栈、入栈顺序的合法性。如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）

4.一个数组实现两个栈

5.实现一个栈，要求实现Push（出栈）、Pop（入栈）、Min（返回最小值的操作）的时间复杂度为O(1)

先来看第一个问题：

使用两个栈实现一个队列

思路：栈（先进后出） 队列（先进先出）

假设有两个栈为是s1，s2。将s1作为基础栈，而s2只是暂时维护数据栈。

若压入1,2,3。则输出的也应该是1，2,3。

“入队”：栈只能从栈顶出。所以现将s1中的数据压入s2中（如图）。

“出队”：从s2中弹出即可。

代码实现：

#include<stack>template<classT>classStackToQueue//栈s1为基本栈，s2维护栈{public:StackToQueue():_size(0){}public:voidStackToQueuePush(constT&d)//s1入队{s1.push(d);++_size;}voidStackToQueuePop()//s2出队{if(s2.empty()){while(!s1.empty())//将栈s1--->s2{s2.push(s1.top());s1.pop();}}s2.pop();--_size;}voidPrint(){while(!s1.empty()){cout<<s1.top()<<"";s1.pop();}while(!s2.empty()){cout<<s2.top()<<"";s2.pop();}}size_tSize(){return_size;}T&Back(){if(s2.empty()){returns1.top();}else{returns2.end();}}T&Front(){if(s1.empty()){returns2.top();}else{returns1.end();}}boolEmpty(){return_size==0;}T&Top(){if(!s1.empty()){returns1.top();}else{returns2.top();}}voidPop(){s1.pop();--_size;}protected:stack<int>s1;//使用库函数stackstack<int>s2;size_t_size;//栈中元素个数};

2.使用两个队列实现一个栈

思路：队列（先进先出），栈（后进先出）

队列和栈插入数据时都是在末端操作。删除数据不同，栈还是在末端操作而队列在队头操作。

假设有队列q1，q2。

“出栈”：假如现有个n数据，将数据压入q1，然后将n-1个数据弹入q2，将第n个数据弹出，此时 s1队列为空，将q2中的前n-1个数据弹入q1，将第n个弹出。此时q2队列为空，以此类推，知道弹出所有 数据。

代码实现：

template<classT>classQueueToStack{public:QueueToStack():_size(0){}public:voidQueueStackPush(constT&d)//q1入栈{q1.push(d);++_size;}voidQueueStackPop()//出栈{size_tsz=0;if(_size){if(q2.empty()){sz=_size-1;while(sz--){q2.push(q1.front());q1.pop();}q1.pop();--_size;}else//(q1.empty()){sz=_size-1;while(sz--){q1.push(q2.front());q2.pop();}q2.pop();--_size;}}}size_tSize(){return_size;}T&Top()//栈顶元素{returnq1.back();}protected:queue<int>q1;queue<int>q2;size_t_size;//队列中元素的个数};

3.元素出栈、入栈顺序的合法性。如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）

看到此题，首先想到栈的特征是后进先出。这就使得栈的出栈顺序有多种。

举一个简单的例子：

假如有一个入栈序列为1,2,3。出栈序列就有1,2,3、2,1,3、3,2,1、2,3,1、1,3,2共5种。

解题思路：

若要验证出入栈的合法性。首先呢，我们应该有两个数组将入栈序列和出栈序列保存起来。假设Push数组存入栈，Pop数组存出栈。从头开始判断数据是否相同，若相同，Push和Pop数组下标加加。若不同，应将数据保存起来，以便下一次比较。这就有一个问题。如何将数据保存起来呢，还要便于取出呢？这就需要一个栈将其保存。若不相同，将其压栈。比较下一个数据，如不相同，还要将栈中的数据弹出比较，相同弹出，不同继续压栈。

代码实现：

//借助两个数组以及一个栈#include<stack>#include<assert.h>boolIsVail(int*Push,int*Pop,intn){assert(Push);//数组元素不为NULLassert(Pop);stack<int>s;inti=0;intj=0;for(j=0;j<n;)//出栈序列下标{for(i=0;i<n;i++)//入栈序列下标{if(Push[i]!=Pop[j])//不相同{if(s.empty())//栈空{s.push(Push[i]);//入栈continue;//跳出本次循环}else{if(Pop[i]==s.top())//栈不为空，不同需和栈中数据比较{s.pop();//相同弹出j++;}else{s.push(Push[i]);//不同继续压栈}}}else{j++;}}}if(i==j)//出栈合法条件{returntrue;}else{returnfalse;}}intmain(){intarr1[5]={1,2,3,4,5};intarr2[5]={4,3,5,2,1};boolret=IsVail(arr1,arr2,5);if(ret){cout<<"出栈顺序合法"<<endl;}else{cout<<"出栈顺序不合法"<<endl;}return0;}

4.一个数组实现两个栈

解题思路：

（1）可将数组以奇数为下标的当为栈1，以偶数为下标的当为栈2。

（2）将数组一分为二，左边为栈1，右边为栈2。

（3）数组从左边开始为栈1，从右边开始为栈2。

分析：

思路（1），（2）虽然能解决问题，但是会浪费空间。若栈1存满，需要扩容。而栈2可能空无元素。

思路（3）可解决此缺憾。当栈1，栈2的栈顶相遇时，需要扩容。

以下用静态和动态分别实现：

（1）静态

代码实现

#defineSIZE10template<classT>classArrayToStack{public:ArrayToStack():_top1(0)//栈1从头开始,_top2(SIZE-1)//栈2从尾开始{}public://voidPush2(constT&d)//从头压栈//{//_a[_top1++]=d;//}//voidPush3(constT&d)//从尾部压栈//{//_a[_top2--]=d;//}voidPush(constT&d,intchoice)//给标志，若choice为0，压入栈1，若为1，压入栈2{if(choice==0){_a[_top1++]=d;}if(choice==1){_a[_top2--]=d;}}voidPop(intchoice)//choice为0，弹出栈1，choice为1，弹出栈2{if(choice==0){if(_top1==0)return;else_top1--;}if(choice==1){if(_top2==0)return;else_top2++;}}size_tsize(intchoice){if(choice==0){return_top1;}if(choice==1){return_top2;}}T&Top(intchoice){if(choice==0){return_a[_top1];}if(choice==1){return_a[_top2];}}protected:T_a[SIZE];//数组int_top1;//栈1的栈顶int_top2;//栈2的栈顶};

（2）动态

代码实现

classArrayToStack{public:ArrayToStack():_a(NULL),_top1(0),_top2(0),_capacity(0){}~ArrayToStack(){if(_a){delete[]_a;}}public:void_CheckCapacity()//扩容{if(_a==NULL){_capacity=3;_a=newT[_capacity];_top1=0;_top2=_capacity-1;}else{if(_top1==_top2){intcapacity=_capacity;//保存之前的容量，在下面复制时方便找到最后一个元素_capacity=2*_capacity;inti=0;intj=0;T*tmp=newT[_capacity];for(i=0;i<_top1;i++)//将原来的复制到新开辟的空间上{tmp[i]=_a[i];}intk=_capacity-1;//扩容后的最后一位for(j=capacity-1;j>_top2;j--){tmp[k--]=_a[j];}_top2=k;//将_top2更新delete[]_a;_a=tmp;}}}voidPrint(){inti=0;intj=0;for(i=_top1-1;i>=0;i--){cout<<_a[i]<<"";}cout<<endl;for(j=_top2+1;j<_capacity;j++){cout<<_a[j]<<"";}}public:voidPush(constT&d,intchoice){_CheckCapacity();if(choice==0)//压入栈1{_a[_top1++]=d;}if(choice==1)//压入栈2{_a[_top2--]=d;}}voidPop(){if(choice==0)//弹出栈1{if(_top1==0)return;else_top1--;}if(choice==1)//弹出栈2{if(_top2==0)return;else_top2++;}}protected:T*_a;//数组int_top1;//栈1的栈顶int_top2;//栈2的栈顶int_capacity;//容量};

5.实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)

看到此题，我们都知道Push（入栈）、Pop（出栈）的时间复杂度为O（1）。而解决此题的难点在于Min（返回最小值的操作）的时间复杂度为O(1)。我们不可能从头开始遍历，这样复杂度不可能为O（1）

解决此题的方法有如下两种：

（1）使用一个栈

每一次入栈都压两次，第一次压入原始数据，第二次压入当前栈中最小的。在第二压栈之前，需和上一次的比较，若小于则压栈，否则将上一次的再次压栈。出栈时，每次都弹出两次。

（2）使用两个栈

第一个栈用来保存原始数据，第二栈用保存当前栈中最小值。第一次两个栈中都压入，若再次压入栈，需要和当前栈2中的元素比较，若小于等于则入栈，否则只压入栈1。

分析：

若要是数据量庞大，可见第一种方法使用的空间很大。

此处实现的是第二种方法：

栈的简单实现：

template<classT>classStack{public:Stack()//构造函数:_a(NULL),_top(0),_capacity(0){}~Stack(){if(_a){delete[]_a;_a=NULL;}}Stack(Stack<T>&s){size_ti=0;_top=s._top;_capacity=s._top;_a=newT[_top];for(i=0;i<_top;i++){_a[i]=s._a[i];}}Stack<T>&operator=(Stack<T>&s){if(this!=&s){size_ti=0;delete[]_a;_top=s._top;_capacity=s._capacity;_a=newT[_top];for(i=0;i<_top;i++){_a[i]=s._a[i];}}return*this;}public:voidCheckCapacity()//检容{if(_top==_capacity){_capacity=_capacity*2+3;T*tmp=newT[_capacity];size_ti=0;for(i=0;i<_top;i++){tmp[i]=_a[i];}delete[]_a;_a=tmp;}}public:voidPush(constT&x)//插入{CheckCapacity();_a[_top++]=x;}voidPop()//栈顶删除{_top--;}T&Top()//返回栈顶元素{return_a[_top-1];}boolEmpty()//栈是否为空{return_top==0;}size_tSize()//元素个数{return_top;}private:T*_a;size_t_top;size_t_capacity;};

返回最小值操作：

template<classT>classStackMin{public:StackMin():_size(0){}public:voidM_Push(constT&d){if(s1.Empty()&&s2.Empty()){s1.Push(d);s2.Push(d);}else{if(s2.Top()<d){s1.Push(d);}else{s1.Push(d);s2.Push(d);}}++_size;}voidM_Pop(){if(s1.Top()==s2.Top()){s1.Pop();s2.Pop();}else{s1.Pop();}--_size;}T&MinMem(){returns2.Top();}size_tM_Size(){return_size;}protected:Stack<T>s1;//栈1Stack<T>s2;//栈2size_t_size;//栈中元素的个数};