232. 用栈实现队列（Implement Queue using Stacks）
难度：简单 | 主题：栈、队列、设计
题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作：push、peek、pop 和 empty。
示例：
输入：["MyQueue","push","push","peek","pop","empty"] [[],[1],[2],[],[],[]]
输出：[null,null,null,1,1,false]
思路
先讲个故事：两摞盘子，一个洗碗机
食堂后厨有两个操作台。一边是脏盘子摞（输入栈），一边是干净盘子摞（输出栈）。
脏盘子摞：盘子一个一个往上叠，叠在最上面的最晚来。
洗碗机：把整个脏盘子摞一次性倒到干净盘子那边——顺序就反了。
原来最下面的盘子（最早来的）现在到了干净盘子摞的最上面。拿出来用的时候，最早来的最先被拿走——先进先出，完美队列。
引导式推导：负负得正
核心洞察：两次反转 = 原顺序。
-
栈是 LIFO：1, 2, 3 入栈，弹出是 3, 2, 1
-
如果再把 3, 2, 1 压入另一个栈，弹出是 1, 2, 3
数据流示意：
push 1, 2, 3:
输入栈（脏盘子）: [1, 2, 3] ← 栈顶是 3
pop():
输入栈全部倒入输出栈 → 输出栈: [3, 2, 1] ← 栈顶是 1
弹出 1 → 输出栈: [3, 2] ← 栈顶是 2
graph LR subgraph SGpv8c6["输入栈（脏盘子）"] A["底部"] --> B["1"] B --> C["2"] C --> D["3（顶部）"] end subgraph 翻转 D --> E["弹出3<br/>压入输出栈"] C --> F["弹出2<br/>压入输出栈"] B --> G["弹出1<br/>压入输出栈"] end subgraph SG4cc93["输出栈（干净盘子）"] G --> H["1（顶部）"] F --> I["2"] E --> J["3"] end
均摊 O(1) 的关键：不是每次 pop 都转移，而是输出栈为空时才转移。
每个元素最多经历：入输入栈一次 → 出输入栈一次 → 入输出栈一次 → 出输出栈一次 = 4 次操作。n 次操作总时间 O(n)，平均每次 O(1)。
推荐写法
class MyQueue:
def __init__(self):
self.in_stack = [] # 输入栈：接收 push 操作
self.out_stack = [] # 输出栈：提供 pop/peek 操作
def push(self, x):
self.in_stack.append(x) # 直接压入输入栈
def pop(self):
self._transfer() # 输出栈空时才转移
return self.out_stack.pop() # 输出栈顶即队首
def peek(self):
self._transfer() # 同样需要确保输出栈有数据
return self.out_stack[-1] # 输出栈顶即队首（不弹出）
def empty(self):
return not self.in_stack and not self.out_stack # 两个栈都空才空
def _transfer(self):
if not self.out_stack: # 关键：只在输出栈空时转移
while self.in_stack: # 倒空整个输入栈
self.out_stack.append(self.in_stack.pop())
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| push | O(1) | 直接入栈 |
| pop/peek | 均摊 O(1) | 每个元素最多转移一次 |
| empty | O(1) | 检查两个栈 |
| 空间 | O(n) | 两个栈合计存 n 个元素 |
实战考量
频率分析
出现在：字节/微软/亚麻 OA 高频，设计轮热身题。约 20% 的设计面会从”实现数据结构”开始，重点考察均摊分析思维。
延伸思考
Q：每个操作的最坏时间复杂度是多少？
A：pop 最坏 O(n)（需要转移时）。但均摊下来是 O(1)——因为一个元素被转移后不会再次转移。
Q：用一个栈能实现队列吗？
A：不能。一个栈无法反转元素顺序。两个栈是最少需要。
Q：三个栈能做得更好吗？
A：不能提升均摊复杂度。两个栈已经是最优。
Q：_transfer 为什么要 while self.in_stack 而不是 if？
A：输入栈可能有多个元素需要转移。一次转移必须倒空整个输入栈，否则弹出顺序不对。
Q：用 list 模拟栈的 pop 性能如何？
A：Python list 的 pop 是 O(1)，尾部操作。这里完美适配。
易错点
-
_transfer只在out_stack为空时调用，不能每次都转移 -
转移必须要倒空
in_stack的全部元素 -
peek不弹出元素，但也要调用_transfer -
empty需要检查两个栈都为空
生活类比
用栈实现队列 → 两摞盘子
脏盘子一股脑摞上去（输入栈），要洗的时候整摞倒到干净水池那边（输出栈）。
倒一次，顺序就反了两次 → 最早进来的最早出去。
洗碗阿姨很聪明：干净水池里还有盘子就不倒——不够了再倒新的。
这就是”输出栈非空不移转”的精髓。
数据结构的本质就是管理顺序——LIFO 转 FIFO，就差一次反转。
相关题目
| 题目 | 关系 |
|---|---|
| 225用队列实现栈 | 对偶题目 |
| 155最小栈 | 同为设计题 |
→ 返回题单：LeetCode学习路线图 > 三、栈与队列
速记卡（面试闪卡）
Q1：一句话讲清「232. 用栈实现队列（Implement Queue using Stacks）」到底是什么？
A：两个栈实现 FIFO 队列：一个输入栈收 push，弹出时整摞倒进输出栈顺序即反转，输出栈空才转移，均摊 O(1)。
Q2：为什么两个栈能变队列？ —— 怎么理解？
A：像食堂两摞盘子：脏盘子往上叠（输入栈），整摞倒到干净那边（输出栈），顺序反了两次=原顺序，最早来的最先被拿走。核心洞察：两次反转=原顺序。
Q3：均摊 O(1) 怎么来的？ —— 怎么理解？
A：不是每次 pop 都倒，而是输出栈空了才倒一整摞。每个盘子最多经历入栈→出栈→入另一栈→出另一栈四次操作，n 次总 O(n)，平均每次 O(1)。像洗碗阿姨”不够了再倒新的”。
Q4：易错点有哪些？ —— 怎么理解？
A：_transfer 只在 out_stack 空时调用且必须用 while 倒空整个 in_stack；peek 也要调 _transfer 但不弹出；empty 要看两个栈都空。一个栈无法反转顺序，两个是最少。
Q5：相关扩展？ —— 怎么理解？
A：对偶题 225 用队列实现栈；155 最小栈同为设计题。重点考均摊分析思维：pop 最坏 O(n) 但均摊 O(1)，因为一个元素转移后不会再转移。
Q6：核心速记主线有哪些？
-
思路：输入栈收、输出栈取，倒一次反转顺序
-
关键：输出栈空才转移，均摊 O(1)
-
操作：push 入 in、pop/peek 触发转移取 out 顶、empty 查双栈
-
易错：while 倒空 in_stack、peek 也要转移
口诀
A：两摞盘子倒一遭，
反转两次序就好；
干净那边有就取，
没了再倒不瞎跑。