题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。
队列中的元素为int类型。

 

输入：

每个输入文件包含一个测试样例。
对于每个测试样例，第一行输入一个n(1<=n<=100000)，代表队列操作的个数。
接下来的n行，每行输入一个队列操作：
1. PUSH X 向队列中push一个整数x(x>=0)
2. POP 从队列中pop一个数。

 

输出：

对应每个测试案例，打印所有pop操作中从队列pop中的数字。如果执行pop操作时，队列为空，则打印-1。

 

样例输入：

3PUSH 10POPPOP

样例输出：

10-1

思想：假设有两个栈S1和S2
　　1. 如果要进队列，那么就将元素压入S1；
　　2. 如果要出队列，如果S2为空且S1非空，那么就将S1的元素逐个压入S2，再弹出S2的栈顶元素(优化：其实在S1进入S2的时候，
  　　 直接将S1的栈底元素直接输出即可，不用进入S2)；如果S2非空，直接出栈。

Code:

#include <iostream>#include <stack> using namespace std; int main(){    stack<int> S1;    stack<int> S2;    string str;    int n;    while(cin>>n){        for(int i=1;i<=n;i++){            cin>>str;            if(str=="PUSH"){                int x;                cin>>x;                S1.push(x);            }            if(str=="POP"){                if(S2.empty()==true){                    if(S1.empty()==false){                        while(S1.empty()==false){                            int tmp=S1.top();                            S1.pop();                            if(S1.empty()==true){  //此时轮到栈底元素，直接输出                                cout<<tmp<<endl;                                continue;                            }                            S2.push(tmp);                        }                    }                    else{                        cout<<-1<<endl;                    }                }                else{                    if(S2.empty()==false){                        int ans=S2.top();                        S2.pop();                        cout<<ans<<endl;                    }                }            }        }    }    return 0;} /**************************************************************    Problem: 1512    User: lcyvino    Language: C++    Result: Accepted    Time:650 ms    Memory:1656 kb****************************************************************/

 

剑指OFFER之用两个栈实现队列