0225. Implement Stack using Queues ================================== 题目信息 -------- :题号: 0225 :难度: Easy :主题: 设计、栈、队列、对象状态 :原题: `LeetCode 0225 `_ :重点: 用 FIFO 操作实现 LIFO、方法语义、跨调用状态、合法空栈操作 题目重述 -------- 设计 ``MyStack`` 类,用一个或两个队列实现后进先出的栈,并支持以下方法:``push(x)`` 把元素压入栈顶;``pop()`` 删除并返回栈顶元素;``top()`` 返回但不删除栈顶元素;``empty()`` 判断栈是否为空。 实现只能使用队列的标准操作,包括从队尾加入、读取或删除队首、查询长度以及判空。``x`` 位于 ``[1, 9]``,四种方法的调用总数最多为 ``100``;题目保证调用 ``pop`` 和 ``top`` 时栈非空。同一个对象必须在连续方法调用之间保存其内容和顺序。 自建示例 -------- 后压入的元素先返回: .. code-block:: text 输入:依次调用 push(3), push(8), top(), pop(), top(), empty() 输出:8, 8, 3, false 解释:8 比 3 后入栈,因此 top 和第一次 pop 都得到 8;删除 8 后,新的栈顶是 3,栈仍非空。 单队列旋转 ---------- 让队列的队首始终对应栈顶。压入新元素 ``x`` 时,先把 ``x`` 加到队尾, 再把原来位于 ``x`` 前面的元素依次从队首取出并重新放到队尾: .. code-block:: text 原队列: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++ 实现 -------- .. code-block:: cpp class MyStack { std::queue queue_; public: MyStack() = default; void push(int x) { queue_.push(x); const int old_size = static_cast(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``,所以实现不需要为非法空操作伪造返回值。