跳到主要内容

LeetCode 232. 用栈实现队列

本节目标

通过输入栈与输出栈的延迟搬运，在均摊常数时间内实现先进先出。

只使用栈的标准操作实现队列的 push、pop、peek 和 empty。栈是后进先出，队列是先进先出；两次反转可以抵消顺序差异。这道题是栈与队列中“延迟搬运与均摊分析”的母题。

查看原题

两个栈的职责​

输入栈只负责接收新元素，因此 push 直接压栈。输出栈只负责提供队首；当它非空时，栈顶就是当前队首。

需要 pop 或 peek 而输出栈为空时，把输入栈逐个弹出并压入输出栈。一次反转让最后压入输入栈的元素先进入输出栈底，而最早压入的元素最终到达输出栈顶，正好成为队首。

为什么不应每次来回搬运​

若每次操作都把所有元素在两个栈之间搬来搬去，单次操作可能线性，且会重复搬运同一元素。正确做法是只在输出栈为空时搬运：元素进入输出栈后，直到被弹出都不再移动。

所以每个元素最多从输入栈转移到输出栈一次，再从输出栈弹出一次。虽然某一次 pop 可能触发多次搬运，但把成本摊到这些元素上后，每个操作的均摊时间是 O(1)。

代码实现​

pop 与 peek 共用“必要时搬运”的私有步骤。题目保证不会对空队列调用它们，因而无需为题目约束外的空操作另设公开行为。

C++17
#include <stack>
using namespace std;

class MyQueue {
public:
    void push(int x) {
        input.push(x);
    }

    int pop() {
        moveIfNeeded();
        int front = output.top();
        output.pop();
        return front;
    }

    int peek() {
        moveIfNeeded();
        return output.top();
    }

    bool empty() {
        return input.empty() && output.empty();
    }

private:
    void moveIfNeeded() {
        if (!output.empty()) {
            return;
        }
        // 只在输出栈为空时搬运，每个元素最多搬一次
        while (!input.empty()) {
            output.push(input.top());
            input.pop();
        }
    }

    stack<int> input;
    stack<int> output;
};

复杂度分析​

push 为 O(1)；pop 和 peek 的单次最坏时间为 O(n)，但均摊时间为 O(1)。两个栈合计保存全部元素，空间复杂度为 O(n)。

易错点​

  • 每次 peek 或 pop 后把元素搬回输入栈，导致重复搬运。
  • 输出栈非空时仍继续搬运，破坏已有的队首顺序。
  • 把输入栈顶误当作队首；输入栈保存的是刚到达的元素，顺序尚未反转。

模式迁移​

延迟操作适用于“昂贵转换不必立刻发生”的结构。以后遇到双端队列、懒删除或分批处理时，都可检查某次转换是否能推迟到真正需要结果的时刻，并用总搬运次数分析均摊复杂度。