跳到主要内容

LeetCode 225. 用队列实现栈

本节目标

用单队列的轮转不变量把最新元素放到队首，模拟后进先出。

只使用队列的标准操作实现栈的 push、pop、top 和 empty。队列只能从队首取元素，栈却要取最近压入的元素；可以在压入时重排队列，让队首始终充当栈顶。这道题是栈与队列中“单队列轮转不变量”的母题。

查看原题

轮转不变量​

维护一个不变量：每次操作结束后，队首就是当前栈顶。压入新元素前，队列从队首到队尾按栈顶到栈底排列；将新元素加入队尾后，把此前的所有元素依次从队首移到队尾，新元素便被轮转到队首。

因此 pop 直接删除队首，top 直接读取队首。它们都不需要额外搬运，代价集中在 push。

谁承担时间代价​

若使用一个队列，就必须在某个时刻改变队列的先后顺序。本题选择在 push 时轮转旧元素，使之后的 pop 与 top 都是 O(1)。第 n 次压入要移动此前 n - 1 个元素，故 push 为 O(n)。

另一种设计可以让 push 很快、在取栈顶时再轮转，但本题的单队列方案选择了更直接的栈顶不变量。

代码实现​

C++ 使用 queue<int>，Python 使用 collections.deque。题目保证不会对空栈调用 pop 或 top，所以代码只实现题目接口，不扩展额外的空结构协议。

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

class MyStack {
public:
    void push(int x) {
        values.push(x);
        // 轮转旧元素后，新元素始终位于队首
        for (size_t count = values.size() - 1; count > 0; count--) {
            values.push(values.front());
            values.pop();
        }
    }

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

    int top() {
        return values.front();
    }

    bool empty() {
        return values.empty();
    }

private:
    queue<int> values;
};

复杂度分析​

push 需要轮转已有元素，时间复杂度为 O(n)；pop、top 和 empty 均为 O(1)。队列存储全部压入元素，空间复杂度为 O(n)。

易错点​

  • 新元素入队后不轮转，队首仍是最早入队元素，结构退化为普通队列。
  • 轮转次数写成当前队列长度，导致把新元素也移动走；只应轮转此前已有的元素。
  • 在 top 中删除队首，破坏“查看而不弹出”的接口语义。

模式迁移​

当一个受限结构需要模拟另一种访问顺序时，可以先决定哪一个操作承担重排成本，再写出操作后的不变量。循环队列旋转、窗口维护和多容器模拟都可用同样的方法验证顺序是否正确。