使用两个栈实现一个队列

思路一：

我们设定s1是入栈的，s2是出栈的。

入队列，直接压到s1即可

出队列，先把s1中的元素倒入到s2中，弹出s2中的栈顶元素；再把s2的剩余元素全部倒回s1中。

缺点：

每次只要出栈一个元素就要将元素倒来倒去，麻烦！！！

思路2：

入队列时：
如果s1为空，把s2中所有的元素倒出压到s1中。否则直接压入s1

出队列时：
如果s2不为空，把s2中的栈顶元素直接弹出。否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素

思路1无条件地每次都要将元素倒来倒去，思路2出队时较思路1简单

思路3：

我们设定s1是入栈的，s2是出栈的

入队列：直接压入元素至s1即可

出队列：如果s2不为空，把s2中的栈顶元素直接弹出。否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素

相比于方法2，入队直接压入即可~

那么，我们可以看出，思路三最简单，我们下面看下代码。

代码实现：

1）我们直接调用库里的stack来实现。（一般调用库里的就行了）

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;//两个栈实现一个队列#include<stack>template<classT>classQueue{public:voidappendTail(constT&x){s1.push(x);}voiddeleteHead(){if(s2.empty()){while(!s1.empty()){s2.push(s1.top());s1.pop();}cout<<s2.top()<<"";s2.pop();}else{cout<<s2.top()<<"";s2.pop();}}private:stack<T>s1;stack<T>s2;};voidTest(){Queue<int>q;q.appendTail(1);q.appendTail(2);q.appendTail(3);q.appendTail(4);q.deleteHead();q.deleteHead();q.deleteHead();q.deleteHead();}intmain(){Test();system("pause");return0;}

2）自己实现栈实现。

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#include<assert.h>//直接实现Stack，也可以用适配器实现栈，或者用库。//将Stack基本功能实现如下：template<classT>classStack{public:Stack():_array(NULL),_size(0),_capacity(0){}Stack<T>(constStack<T>&s):_array(newT[s._capacity]){swap(_array,s._array);swap(_size,s._size);swap(_capacity,s._capacity);}Stack<T>&operator=(constStack<T>&s){if(&s!=this){swap(_array,s._array);swap(_size,s._size);swap(_capacity,s._capacity);}return*this;}~Stack(){if(_array){delete[]_array;_array=NULL;}}void_CheckCapacity(){if(_size==0){_capacity=3;_array=newT[_capacity];}if(_size>=_capacity){_capacity*=2;T*tmp=newT[_capacity];for(intindex=0;index<_size;index++){tmp[index]=_array[index];}delete[]_array;_array=tmp;}}voidPush(constT&x){_CheckCapacity();_array[_size++]=x;}voidPop(){if(_size==0){return;}--_size;}size_tSize(){return_size;}boolEmpty(){returnSize()==0;}T&Top(){assert(_size>0);return_array[_size-1];}private:T*_array;size_t_size;size_t_capacity;};template<classT>classQueue{public:voidInQueue(constT&x){s1.Push(x);}voidOutQueue(){//栈s2为空，则将栈s1的元素全部倒入s2中，再弹出最上面的那个元素if(s2.Empty()){while(!s1.Empty()){s2.Push(s1.Top());s1.Pop();}s2.Pop();}//栈s2不为空，直接弹出元素else{s2.Pop();}}voidPrint()//打印队列元素，分四种情况。{if(s1.Empty()&&s2.Empty()){cout<<"TheQueueisEmpty!";}elseif(!s1.Empty()&&s2.Empty()){while(!s1.Empty()){s2.Push(s1.Top());s1.Pop();}while(!s2.Empty()){cout<<s2.Top()<<"";s2.Pop();}}elseif(s1.Empty()&&!s2.Empty()){while(!s2.Empty()){cout<<s2.Top()<<"";s2.Pop();}}else{while(!s2.Empty()){cout<<s2.Top()<<"";s2.Pop();}while(!s1.Empty()){s2.Push(s1.Top());s1.Pop();}while(!s2.Empty()){cout<<s2.Top()<<"";s2.Pop();}}cout<<endl;}private:Stack<T>s1;//入队Stack<T>s2;//出队};//测试两个栈实现一个队列voidTest1(){Queue<int>q1;q1.InQueue(1);q1.InQueue(2);q1.InQueue(3);q1.InQueue(4);/*q1.Print();*/q1.OutQueue();/*q1.Print();*/q1.InQueue(5);q1.InQueue(6);q1.InQueue(7);q1.Print();}intmain(){Test1();system("pause");return0;}

(1个细节)：

注意再将元素倒入另一个栈时，代码并不是先pop,再push。因为这样push后元素就找不到了。因此要先访问到栈顶元素top,再push,而后pop。