9.用两个栈实现队列

题目：用两个栈实现队列，实现先入先出的特点。
简化问题：使用两个栈先进后出的特点来实现一个队列先进先出的特点，很简单，只需要把数据先放入第一个栈，然后再从第一个栈放入第二个栈，此时第二个栈中的元素顺序就是队列中的顺序。

因此我们需要一个栈拷贝（转移）函数。

#将栈a的内容转移到栈b中，此时栈b中的元素顺序就是队列中的顺序
void copy(stack<int>& a,stack<int>& b)
{
        while(a.size())
        {   
            b.push(a.top());
            a.pop();
        }
}

算法代码：

class MyQueue {
public:
    stack<int> s1;
    stack<int> s2;
    MyQueue() {
    }
    
    #入栈的时候只需要将元素依次放入第一个栈中
    void push(int x) {
        s1.push(x);
        
    }
    void copy(stack<int>& a,stack<int>& b){
        while(a.size())
        {   
            b.push(a.top());
            a.pop();
        }
    }
    #从第二个栈中弹出元素，再将剩下的内容复制到原始的栈当中（原始栈内容此时是空的）
    int pop() {
        copy(s1,s2);
        int res = s2.top();
        s2.pop();
        copy(s2,s1);
        return res;
    }
    
    #返回第一个元素
    int peek() {
        copy(s1,s2);
        int res = s2.top();
        copy(s2,s1);
        return res;
        
    }
    
    #判断是否为空
    bool empty() {
        if (s1.empty())
            return true;
    }
};

需要注意的是，再将第一个栈的内容拷贝到第二个栈中的时候，根据我们栈拷贝函数的写法，此时第一个栈中元素已经全部弹出，所以在操作完后，要将第二个栈中剩余的元素再拷贝到原始栈中，这样才能继续操作剩余的元素。