题解 | 用两个栈实现队列

class Solution {
  public:
    void push(int node) {
        // 直接将元素压入stack1（输入栈）
        stack1.push(node);
    }

    int pop() {
        // 如果stack2（输出栈）为空，将stack1的所有元素转移到stack2
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }

        // 从stack2弹出栈顶元素（即队列头部元素）
        int result = stack2.top();
        stack2.pop();
        return result;
    }

  private:
    stack<int> stack1;  // 输入栈，用于入队操作
    stack<int> stack2;  // 输出栈，用于出队操作
};

思路分析
使用两个栈实现队列的核心思想是：
一个栈用于入队操作（输入栈）
另一个栈用于出队操作（输出栈）

当需要出队时：
如果输出栈为空，将输入栈的所有元素依次弹出并压入输出栈
然后从输出栈弹出栈顶元素

复杂度分析
空间复杂度: O(n)
两个栈总共存储n个元素，满足O(n)的空间复杂度要求
时间复杂度:
push操作: O(1) - 直接压入输入栈
pop操作: 均摊O(1) - 每个元素最多被压入和弹出两次（一次在输入栈，一次在输出栈）

关键点说明
入队操作：直接将元素压入输入栈，时间复杂度为O(1)
出队操作：
如果输出栈不为空，直接弹出栈顶元素，时间复杂度O(1)
如果输出栈为空，需要将输入栈的所有元素转移到输出栈，这个过程的时间复杂度为O(n)，但均摊到每个元素上仍然是O(1)
正确性保证：
输入栈按入队顺序存储元素（后进先出）
当需要出队时，将输入栈元素转移到输出栈，在输出栈中元素顺序正好与入队顺序相反，即变为先进先出