第3章｜栈与队列

Unit 05 · 两次顺序反转恢复 FIFO

← Unit 04 最小栈
U05
Queue via Two StacksInput · Output · Lazy Transfer

两个后进先出的栈，
为什么能恢复先进先出？

第一次反转发生在元素进入输入栈时；第二次反转发生在从输入栈整体搬入输出栈时。真正困难的不是“倒一次”，而是确定什么时候不该再倒。

LeetCode #232 题目模型仅使用标准栈操作实现 FIFO 队列

题目要求

仅使用两个栈实现一个先进先出队列。实现 MyQueue，支持在队尾加入元素、移除并返回队首、读取队首以及判断队列是否为空。

class MyQueue: def __init__(self): ... def push(self, x: int) -> None: ... def pop(self) -> int: ... def peek(self) -> int: ... def empty(self) -> bool: ...

约束与进阶

  • 1 <= x <= 9；
  • 最多调用 100 次四类接口；
  • 所有 pop / peek 调用均有效；
  • 进阶要求每个操作均摊时间复杂度为 O(1)。

示例

输入： ["MyQueue","push","push","peek","pop","empty"] [[],[1],[2],[],[],[]] 输出： [null,null,null,1,1,false]

本页主模型

input_stack 接收新元素；output_stack 提供队首。只有当输出栈为空且需要读取队首时，才将输入栈整体搬入输出栈。

队列顺序 = reverse(output_stack) + input_stack （两个数组都按“栈底 → 栈顶”表示）
Input Stack

保存尚未转移的较新元素。新元素只需在数组尾部 append，保持 O(1)。

Output Stack

保存已经反转的较旧元素。其栈顶恰好是当前队首。

Lazy Transfer

只有输出栈为空时才转移。未空时保留旧元素的服务优先级。

Amortized O(1)

单次转移可能是 O(n)，但每个元素一生只会从输入栈搬到输出栈一次。

从 Unit 04 到 Unit 05：从“同步摘要”走向“分区状态”

上一单元用主栈与辅助栈同步维护同一容器的极值；本单元则把同一个逻辑队列拆成“较新批次”和“较旧批次”。两者共同要求：先定义每个容器代表什么，再证明每次修改后整体语义仍成立。

Unit 04 · Min Stackdata_stack 保存真实元素，min_stack 保存查询摘要。两个结构需要同步修改。
→
Unit 05 · Queue via Stacksinput_stack 保存较新元素，output_stack 保存已反转的较旧元素。两个结构共同组成一个逻辑队列。
认知任务 1
先不写代码：队列中谁必须最先离开？
观察当前两个栈和下方逻辑队列，回答依赖当前动画状态的问题。
双栈执行实验官方样例扩展

input_stack 新元素入口

⇢
只在 output 为空时等待转移

output_stack 栈顶 = 队首

逻辑队列：队首 → 队尾length = 0
FRONT
REAR
reverse([]) + [] = []
读取操作
检查 output
必要时转移
执行栈操作
产生返回值
保持契约
push 只进入 input_stack；读取队首时再判断是否需要转移。
当前操作—
本步转移0
累计转移0
返回值—

当前状态下，哪个元素应该最先离开？

回答当前问题后继续
补全可直接提交的 Python 代码关键是惰性转移与双栈判空
class MyQueue:
def __init__(self):
self.input_stack =
self.output_stack =
def push(self, x: int) -> None:
def _move_if_needed(self) -> None:
if :
while self.input_stack:
def pop(self) -> int:
self._move_if_needed()
return
def peek(self) -> int:
self._move_if_needed()
return
def empty(self) -> bool:
return
class MyQueue: def __init__(self): self.input_stack = [] self.output_stack = [] def push(self, x: int) -> None: self.input_stack.append(x) def _move_if_needed(self) -> None: if not self.output_stack: while self.input_stack: self.output_stack.append(self.input_stack.pop()) def pop(self) -> int: self._move_if_needed() return self.output_stack.pop() def peek(self) -> int: self._move_if_needed() return self.output_stack[-1] def empty(self) -> bool: return not self.input_stack and not self.output_stack
代码—双栈—逻辑队列逐行联动点击任意代码行可跳转
1class MyQueue:
2 def __init__(self):
3 self.input_stack = []
4 self.output_stack = []
6 def push(self, x: int) -> None:
7 self.input_stack.append(x)
9 def _move_if_needed(self) -> None:
10 if not self.output_stack:
11 while self.input_stack:
12 self.output_stack.append(
self.input_stack.pop())
14 def pop(self) -> int:
15 self._move_if_needed()
16 return self.output_stack.pop()
18 def peek(self) -> int:
19 self._move_if_needed()
20 return self.output_stack[-1]
22 def empty(self) -> bool:
23 return not self.input_stack and
not self.output_stack
当前调用MyQueue()
input_stack[]
output_stack[]
逻辑队列[]
本步判断 / 动作进入类定义
返回值 / 累计转移— / 0
轨迹将展示第一次批量转移、输出栈未空时跳过转移，以及第二次批量转移。
完成代码联动后进入 Unit 06 的反向迁移代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。

迁移题：LeetCode #225 用队列实现栈

先读完整原题，再判断 #232 的哪些思想能够保留。目标从 FIFO 变为 LIFO，底层限制也从栈变为队列；单队列方案通过在每次 push 后轮转旧元素，让队首始终代表栈顶。

1. 认识 #225 原题
2. 对照两种顺序转换
3. 映射四个语义槽位
4. 拼装并运行官方样例

LeetCode #225｜用队列实现栈

Easy · Stack · Design · Queue
题目要求

只使用队列实现一个后进先出（LIFO）栈，并支持普通栈的四种操作：压入栈顶、移除并返回栈顶、读取栈顶，以及判断是否为空。

from collections import deque class MyStack: def __init__(self): ... def push(self, x: int) -> None: ... def pop(self) -> int: ... def top(self) -> int: ... def empty(self) -> bool: ...
允许的底层操作
  • 只能使用队列的标准操作：从队尾加入、从队首查看或删除、读取长度、判断为空。
  • Python 可以使用 deque 模拟，但不能借助右端弹出绕过 FIFO 限制。
官方示例
输入： ["MyStack","push","push","top","pop","empty"] [[],[1],[2],[],[],[]] 输出： [null,null,null,2,2,false]
约束与进阶
  • 1 ≤ x ≤ 9
  • 最多调用 100 次四类接口。
  • pop 与 top 调用时保证栈非空。
  • 进阶：仅使用一个队列实现。
题面依据：LeetCode 官方 #225 页面。
读题检查 1：top() 与 pop() 应访问哪一个元素？
尚未作答。
读题检查 2：官方示例连续压入 1、2 后，为什么 top() 返回 2？
尚未作答。
完成两道读题检查后解锁算法对照。

#232｜用栈实现队列

  • 底层：LIFO 栈；目标：FIFO 队列。
  • 新元素先进入 input_stack。
  • 第一次需要队首且 output_stack 为空时，整体转移。
  • 重排成本放在部分 pop/peek 上，均摊 O(1)。

#225｜用队列实现栈（单队列）

  • 底层：FIFO 队列；目标：LIFO 栈。
  • 新元素先从队尾入队。
  • 立即把此前元素从队首依次移到队尾。
  • 重排成本放在 push 上，使 pop/top 可直接访问队首。

哪一句最准确描述这次迁移？

选择正确的结构变化后继续。

槽位 1｜状态表示

用什么保存当前逻辑栈？

未完成。

槽位 2｜接收新元素

push(x) 的第一步是什么？

未完成。

槽位 3｜恢复 LIFO 顺序

新元素入队后如何让它成为队首？

未完成。

槽位 4｜公开接口

轮转完成后，pop/top/empty 如何实现？

未完成。
完成 0 / 4 个槽位。

由四个语义槽位拼装出的单队列版本


          
          
#232：push 只追加；output 为空且需要队首时才整体转移。
#225：push 追加后立即轮转旧元素；此后 queue[0] 始终是逻辑栈顶。

复杂度变化：
#232：push O(1)，pop/peek 均摊 O(1)。
#225 单队列：push O(n)，pop/top O(1)。

保留的设计思想：底层容器状态必须提前排列成上层接口可以直接读取的顺序。

        

        

          
运行官方样例

          

          
FRONT / TOP
REAR

          
点击下一步，从 MyStack() 开始运行官方操作序列。

          
当前调用—
返回值—
累计输出[]

          

        

      


      

        
可选挑战：不看完整答案独立重写

        
只使用 append、popleft、队首读取、长度和判空。检查器会验证四个接口及 push 后轮转。

        
        

        
        
迁移完成：你不仅记住了单队列写法，还解释了为什么 #232 把成本延迟到查询，而 #225 把成本前移到 push。

      

    

  



  

    
Unit 05 Skill 卡

    
看到“只能使用栈却要实现先进先出”时，不要每次查询都恢复完整队列。将新旧元素分区：新元素进入 input，旧元素在 output 中按服务顺序离开。

    
题号 / 题型#232 · 数据结构设计
触发信号两种相反的离开顺序需要转换
核心表示input_stack + output_stack
关键不变量output 栈顶始终是当前队首
核心操作output 为空时整体转移
复杂度均摊 O(1)，空间 O(n)
常见错误每次读取都倒栈；只检查一个栈是否为空
迁移方向用队列实现栈、双栈撤销系统
推荐下一题#225 用队列实现栈