面试题：用两个栈（Stack）实现一个队列（Queue）

思路：

1、入队时，将元素压入s1。

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

这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次。

具体实现如下：

#include<iostream>usingnamespacestd;#include<stack>#include<string>#include<assert.h>//assert必须为.h库文件template<classT>classQueue{public:voidPush(constT&x);voidPop();voidPrintQueue();boolEmpty();size_tSize();T&Front();T&Back();public:stack<T>s1;//栈s1进行入队stack<T>s2;//栈s2进行出队};template<classT>voidQueue<T>::Push(constT&x){s1.push(x);//s1栈入队}template<classT>voidQueue<T>::Pop(){if(s1.empty()&&s2.empty())//两个队列为空{return;}if(!s2.empty())//s2栈非空元素出栈{s2.pop();}else{while(!s1.empty())//s2栈为空，s1中所有元素导入s2中进行s2的出栈，s1进行pop(){s2.push(s1.top());s1.pop();}s2.pop();//pop掉s2的栈顶元素}}template<classT>voidQueue<T>::PrintQueue(){stack<T>sk1=s1;stack<T>sk2=s2;if(s1.empty()&&s2.empty()){cout<<"queueisempty!"<<endl;return;}while(!sk2.empty())//先输出sk2中的元素，进行sk2的出栈{cout<<sk2.top()<<"";sk2.pop();}while(!sk1.empty())//再进行sk1中元素导入到sk2中，进行sk1的出栈{sk2.push(sk1.top());sk1.pop();}while(!sk2.empty())//最后在sk2中输出sk1中元素，达到队列出队的效果{cout<<sk2.top()<<"";sk2.pop();}cout<<endl;}template<classT>boolQueue<T>::Empty()//判空{returns1.size()==0&&s2.size()==0;}template<classT>size_tQueue<T>::Size()//队列元素个数{returns1.size()+s2.size();}template<classT>T&Queue<T>::Front()//队头{assert(s1.empty()&&s2.empty());//断言队列是否为空if(!s2.empty())//s2不为空，则s2栈顶为队头{returns2.top();}else//s2为空，则将s1中所有元素导入s2中，新s2栈顶为队头{while(!s1.empty()){s2.push(s1.top());s1.pop();}returns2.top();}}template<classT>T&Queue<T>::Back()//队尾{assert(!s1.empty()||!s2.empty());//s1和s2中至少有一个不为空if(!s1.empty())//s1不为空，则s1栈顶为队尾{returns1.top();}else//s1为空，则将s2中所有元素导入s1中，新s1栈顶为队尾{while(!s2.empty()){s1.push(s2.top());s2.pop();}returns1.top();}}

测试用例如下：

voidTest2(){//Queue<int>q1;//q1.s1.push(3);//q1.s2.push(4);//q1.s2.push(5);//q1.Push(2);//q1.Push(1);//q1.PrintQueue();////q1.Pop();////q1.Pop();////q1.Pop();////q1.Pop();////q1.Pop();////q1.Pop();////q1.PrintQueue();Queue<string>q1;q1.s1.push("lllll");q1.s2.push("yyyyy");q1.s2.push("fffff");q1.Push("xxxxx");q1.Push("yyyyy");q1.PrintQueue();cout<<"empty:"<<q1.Empty()<<endl;cout<<"size:"<<q1.Size()<<endl;cout<<"front:"<<q1.Front()<<endl;cout<<"back:"<<q1.Back()<<endl;}