0225. Implement Stack using Queues

题目信息

题号:

0225

难度:

Easy

主题:

设计、栈、队列、对象状态

原题:

LeetCode 0225

重点:

用 FIFO 操作实现 LIFO、方法语义、跨调用状态、合法空栈操作

题目重述

设计 MyStack 类,用一个或两个队列实现后进先出的栈,并支持以下方法:push(x) 把元素压入栈顶;pop() 删除并返回栈顶元素;top() 返回但不删除栈顶元素;empty() 判断栈是否为空。

实现只能使用队列的标准操作,包括从队尾加入、读取或删除队首、查询长度以及判空。x 位于 [1, 9],四种方法的调用总数最多为 100;题目保证调用 pop 和 top 时栈非空。同一个对象必须在连续方法调用之间保存其内容和顺序。

自建示例

后压入的元素先返回:

输入:依次调用 push(3), push(8), top(), pop(), top(), empty()
输出:8, 8, 3, false
解释:8 比 3 后入栈,因此 top 和第一次 pop 都得到 8;删除 8 后,新的栈顶是 3,栈仍非空。

单队列旋转

让队列的队首始终对应栈顶。压入新元素 x 时,先把 x 加到队尾, 再把原来位于 x 前面的元素依次从队首取出并重新放到队尾:

原队列:a, b                 栈顶为 a
push(c):a, b, c
旋转两次:b, c, a -> c, a, b
目标队列:c, a, b             栈顶为 c

一般地,加入前队列有 m 个元素时,旋转原来的 m 个元素,就得到“新元素在队首、旧元素按原栈顶到栈底排列”的状态。 之后 pop 和 top 只需操作队首,empty 直接查询队列状态。

状态不变量与正确性

每次公开方法返回后,队列从队首到队尾恰好等于栈从栈顶到栈底的顺序。 初始两者都为空。push 通过旋转把新元素放到队首,并保持旧元素顺序; pop 删除队首,正好删除栈顶;top 读取队首而不改变状态;empty 的真假也与栈一致。 按调用顺序归纳,四个操作始终满足栈的合同。

C++ 实现

class MyStack {
    std::queue<int> queue_;

public:
    MyStack() = default;

    void push(int x) {
        queue_.push(x);
        const int old_size = static_cast<int>(queue_.size()) - 1;
        for (int i = 0; i < old_size; ++i) {
            queue_.push(queue_.front());
            queue_.pop();
        }
    }

    int pop() {
        const int value = queue_.front();
        queue_.pop();
        return value;
    }

    int top() const {
        return queue_.front();
    }

    bool empty() const {
        return queue_.empty();
    }
};

代码分析

push 需要旋转当前已有的 m 个元素,时间为 O(m);pop、top 和 empty 均为 O(1)。 队列最多保存栈中的全部元素,额外空间为 O(n)。题目保证对非空栈调用 pop/top,所以实现不需要为非法空操作伪造返回值。