CS-Notes 剑指 Offer 题解：用两个栈实现队列——Push/Pop 模拟与均摊 O(1) 复杂度解析

本篇基于 CS-Notes 仓库中《剑指 Offer 题解》的第 9 题 用两个栈实现队列 展开，讲解如何用两个后进先出（LIFO）的栈组合出一个先进先出（FIFO）的队列：in 栈负责入队，out 栈负责出队，通过两次"反转"抵消顺序变化。读完后你能完整复现题目要求的 push 与 pop 操作，理解"仅在 out 栈为空时才整体搬运"这一关键设计，并掌握均摊时间复杂度 O(1) 的推导过程，同时了解空队列异常等边界处理。

题目描述

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

• 原始笔记见 notes/9. 用两个栈实现队列.md；
• 该题在 剑指 Offer 题解 - 目录 中被归类在"栈队列堆"专题下，同专题还有包含 min 函数的栈、栈的压入弹出序列等题目，可对照阅读；
• 题目在牛客网、LeetCode 的"剑指 Offer"题集中均有对应入口（LeetCode 中文题号为 LCOF 09），可作为在线判题的练手环境。

解题思路：两次反转抵消顺序

栈是 LIFO 结构，队列是 FIFO 结构，两者顺序天然相反。核心思想是利用两次反转等于不反转：

1. in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作；
2. 一个元素进入 in 栈之后，出栈的顺序被第一次反转；
3. 当元素要出队时，需要先进入 out 栈，此时元素出栈顺序再一次被反转；
4. 两次反转后，出栈顺序就和最开始入栈顺序相同——先进入的元素先退出，正好满足队列的先进先出语义。

仓库原文档配有一张两个栈协作过程的动画示意图（下图），可以看到元素先在 in 栈中倒序堆放，再整体搬运到 out 栈后恢复正序弹出：

原始笔记的 Java 实现

原文档给出的完整实现如下，两个成员栈 in 和 out 分别在 push 与 pop 中承担不同职责：

Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();

public void push(int node) {
    in.push(node);
}

public int pop() throws Exception {
    if (out.isEmpty())
        while (!in.isEmpty())
            out.push(in.pop());

    if (out.isEmpty())
        throw new Exception("queue is empty");

    return out.pop();
}

源码级逐段解析

push 路径：只做一件事

push 的实现极其简单：新元素无条件压入 in 栈，从不触碰 out 栈。这一步保证了"最新入队的元素一定在 in 栈栈顶"这一不变量，同时把可能昂贵的搬运操作推迟到真正需要出队的时候。

pop 路径：分三步走

pop 方法包含三个逻辑块，顺序不可调换：

1. 按需搬运：if (out.isEmpty()) 成立时，用 while 循环把 in 栈元素全部依次弹出、压入 out 栈。注意是"全部搬空"而不是"搬一个"——只有整体搬完，out 栈顶才是队列头部的最老元素；
2. 空队列保护：搬运完成后若 out 仍为空，说明 in 也为空，即队列为空，此时抛出 Exception("queue is empty")，避免在空结构上执行 out.pop() 得到错误结果或越界行为；
3. 正常出队：返回 out.pop()，即当前队首元素。

为什么只在 out 为空时才搬运

这是整个设计的精髓。out 栈中已存放的元素之间相对顺序是正确的（最老的在栈顶），如果每次 pop 都重新搬运，不仅浪费，还会破坏既有顺序。因此搬运的前置条件严格限定为"out 栈空"：

• 当 out 非空时，pop 直接弹栈顶，成本 O(1)；
• 当 out 为空时，触发一次搬运，成本 O(k)（k 为 in 栈当前元素个数），但搬运完后这些元素后续每一次弹出都只需 O(1)。

复杂度分析

• 空间复杂度：O(n)，两个栈合计存储全部 n 个元素，不引入额外结构；
• 时间复杂度：push 恒为 O(1)。对 pop 做均摊分析——把 in 栈的每个元素记一次"进 in 栈、搬出 in 栈、进 out 栈、出 out 栈"共 4 次栈操作，无论操作序列如何交织，每个元素的生命周期内这 4 次操作只发生一次。因此任意一段由 m 次 push 加 m 次 pop 组成的完整操作序列总成本不超过 O(m)，每次操作的均摊时间复杂度为 O(1)。

需要说明的前提：该均摊结论针对"合法操作序列"（不在空队列上 pop）成立；若判题平台要求返回特定错误值而非抛异常，只需把 throw 换成题目规定的返回值，逻辑不变。

一个完整推演示例

依次执行 push(1) → push(2) → push(3) → pop() → pop() → push(4) → pop()：

步骤	操作	in 栈（左为栈底）	out 栈（左为栈底）	返回值
1	push(1)	[1]	[]	-
2	push(2)	[1, 2]	[]	-
3	push(3)	[1, 2, 3]	[]	-
4	pop()	[]	[3, 2, 1]	1
5	pop()	[]	[3, 2]	2
6	push(4)	[4]	[3, 2]	-
7	pop()	[4]	[3, 2]（out 非空，不搬运）	3

第 7 步体现了关键设计：out 栈非空时直接弹出，in 栈中较新的元素 4 不会插到 3 前面，先进先出顺序保持不变。

常见的两种扩展

若题目还要求实现 peek（查看队首）与 isEmpty 判断，可在同一不变量下补充：

public int peek() throws Exception {
    if (out.isEmpty())
        while (!in.isEmpty())
            out.push(in.pop());

    if (out.isEmpty())
        throw new Exception("queue is empty");

    return out.peek();
}

public boolean isEmpty() {
    return in.isEmpty() && out.isEmpty();
}

peek 的搬运逻辑与 pop 完全一致，只是最后用 peek 替代 pop；isEmpty 则必须同时检查两个栈——元素可能分散存放在任意一个（或两个）栈中。

同仓库相关题解

这道题的"双栈思想"在仓库的其他题解中反复出现，适合作为栈队列专题的延伸阅读（以下链接均相对仓库根目录）：

• 30. 包含 min 函数的栈：用主栈加辅助 minStack 同步维护栈内最小值，体现"辅助栈镜像同步"的技巧；
• 31. 栈的压入、弹出序列：用一个栈模拟压入弹出过程，判断给定弹出序列的合法性，是栈行为的经典模拟题；
• 59. 滑动窗口的最大值：借助单调队列维护窗口最大值，与本节的"用栈模拟队列"同属"结构改造"类问题；
• 完整题目索引见 剑指 Offer 题解 - 目录。

小结

用两个栈实现队列的本质是把一次"顺序反转"分摊到入队与出队两端：push 只进 in 栈，pop 在 out 栈为空时整体搬运后直接弹栈。原文档给出的 Java 代码已完整覆盖题目要求，本文在此基础上补充了逐步推演表、复杂度证明、边界条件说明与 peek/isEmpty 扩展写法。掌握这一模式后，遇到"用 LIFO 结构模拟 FIFO 行为"的变体（如两个队列实现一个栈）时，只需将搬运方向对调，思路完全同构。