方法一：

入队时，将元素压入s1。

出队时，将s1的元素逐个“倒入”（弹出并压入）s2，将s2的顶元素弹出作为出队元素，之后再将s2剩下的元素逐个“倒回”s1。


方法二：

入队时，先判断s1是否为空，如不为空，说明所有元素都在s1，此时将入队元素直接压入s1；如为空，要将s2的元素逐个“倒回”s1，再压入入队元素。

出队时，先判断s2是否为空，如不为空，直接弹出s2的顶元素并出队；如为空，将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。


最优解：

入队时，将元素压入s1。

出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。


注意：考虑没有元素可供出队时的处理（2个栈都为空的时候，出队操作一定会引起异常）

代码实现

//test1.h#include<iostream>#include<stack>usingnamespacestd;template<classT>classqueueWithTwoStack{public:queueWithTwoStack();~queueWithTwoStack();voidaddTail(constT&data);TdeleteHead();private:stack<T>s1;stack<T>s2;};//test1.cpp#include"test1.h"usingnamespacestd;template<classT>queueWithTwoStack<T>::queueWithTwoStack(){}template<classT>queueWithTwoStack<T>::~queueWithTwoStack(){}//加只加在S1中template<classT>voidqueueWithTwoStack<T>::addTail(constT&data){s1.push(data);}//删只删S2中的template<classT>TqueueWithTwoStack<T>::deleteHead(){if((s2.empty())&&(s1.empty())){printf("isempty!\n");return-1;}//s2为空，把S1全倒在S2中后删if(s2.empty()){while(!s1.empty()){Ttop=s1.top();s1.pop();s2.push(top);}}//s2不为空直接删Thead=s2.top();s2.pop();returnhead;}voidtest1(){queueWithTwoStack<int>qw;qw.addTail(1);qw.addTail(2);qw.addTail(3);cout<<qw.deleteHead()<<endl;cout<<qw.deleteHead()<<endl;cout<<qw.deleteHead()<<endl;//cout<<qw.deleteHead()<<endl;}voidtest2(){queueWithTwoStack<int>qw;qw.addTail(1);qw.addTail(2);qw.addTail(3);cout<<qw.deleteHead()<<endl;qw.addTail(4);cout<<qw.deleteHead()<<endl;cout<<qw.deleteHead()<<endl;cout<<qw.deleteHead()<<endl;}intmain(){//test1();test2();system("pause");return0;}


参考：《剑指offer》面试题7

http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html