思路:

入队:

只将栈s1作为入队。


出队:

将栈s2作为出队,如果栈s1不为空,s2为空,出队时将s1的元素倒入s2中,再pop();

否则s2不为空,出队时直接在栈s2中pop();

#include<iostream>#include<stack>#include<assert.h>usingnamespacestd;template<classT>classQueue{public:Queue():_size(0){}voidappendTail(Tnum){s1.push(num);_size++;}voiddeleteHead(){assert(_size>0);if(s2.empty()){while(s1.size()!=1){s2.push(s1.top());s1.pop();}s1.pop();}else{s2.pop();}_size--;}T&top(){assert(_size>0);if(s2.empty()){while(s1.size()!=1){s2.push(s1.top());}returns1.top();}else{returns2.top();}}private:stack<T>s1;stack<T>s2;int_size;};intmain(){Queue<int>q;q.appendTail(1);q.appendTail(2);q.appendTail(3);q.appendTail(4);q.deleteHead();q.deleteHead();q.deleteHead();q.deleteHead();q.appendTail(5);cout<<q.top()<<endl;system("pause");return0;}