题解 | #用两个栈实现队列#

方法1：模拟
我们假设只有一个栈的时候，然后当我们依次推入1、2、3这些元素，这个栈就变成了这样

那么当我们这个时候要将队头，也就是栈底弹出的时候，我们发现有很多挡在他前面，所以我们需要另外一个“中转栈”来存储这些元素，就像这样

于是我们发现，此时第二个栈的栈顶就是我们要弹出的元素，弹出即可。然后把之后的元素都放回到原栈中即可


时间复杂度：push操作为O(1)，pop操作由于需要讲全部元素弹出，为O(n)
空间复杂度：需要用栈来存，O(n)

class Solution
{
public:
    void push(int node) {//这里直接push即可
        stack1.push(node);
    }

    int pop() {
        while (!stack1.empty()) {//这是把全部元素放到“中转栈”这里的过程
            stack2.push(stack1.top());
            stack1.pop();
        }
        int val = stack2.top();//中转栈的栈顶就是我们要pop的元素
        stack2.pop();
        while (!stack2.empty()) {//别忘了把中转栈的元素放回原栈
            stack1.push(stack2.top());
            stack2.pop();
        }
        return val;
    }

private:
    stack<int> stack1;//原栈
    stack<int> stack2;//中转栈
};

方法2：模拟
但是这个模拟和第一个方法有点不太一样，是一个优化
我们发现，对于第一个方法的pop操作中，找到要pop的元素后好像不需要将所有元素放回原栈，因为“先进后出”，只要栈2不空，我们就可以一直pop
也就是，当pop的时候，我们对栈2进行pop即可，当push的时候，我们直接push进栈1。当栈2为空的时候，我们将栈1的元素放进栈2即可。具体看代码
时间复杂度：push操作为O(1),pop操作中，由于我们没有把元素放回去，于是是O(1)
空间复杂度：用栈来储存，为O(n)

class Solution
{
public:
    void push(int node) {//这里还是一样
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()) {//检查，当栈2为空的时候，我们才把元素放进去
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int val = stack2.top();//然后我们pop出栈顶即可
        stack2.pop();
        return val;
    }

private:
    stack<int> stack1;//push用
    stack<int> stack2;//pop用
};