【Java基础】栈与队列的妙用——从 JDK 源码到接雨水，那些面试官不会告诉你的真相

第7期：栈与队列的妙用——从 JDK 源码到接雨水，那些面试官不会告诉你的真相

目录

• 一、面试真题引入
• 二、底层的时空解构与源码透视
  • 2.1 Stack 源码分析——继承 Vector 为什么是设计灾难
  • 2.2 Deque 双端队列接口体系
  • 2.3 Queue/Deque 常用 API 对比
  • 2.4 单调栈基础原理
• 三、"纯手工、零依赖"原创案例实战
  • 3.1 IDE 撤销重做——用两个栈实现
  • 3.2 打印店排队模拟——用 Queue 管理任务队列
• 四、源码避坑指南与 Debug 日记
• 五、面试连环炮 Mock Interview
  • 5.1 为什么阿里巴巴规范和 JDK 官方都严禁使用 Stack 类
  • 5.2 单调栈解"接雨水"——三种思路递进
• 六、通俗类比小结

一、面试真题引入

大二下学期我开始刷 LeetCode，很快就撞上了几道"看着简单、一写就废"的题。最典型的三道：

• 用队列实现栈（LeetCode 225）：给你两个队列，让你模拟栈的 push/pop/top/empty。第一次写的时候，我在 pop 那里卡了半小时——两个队列倒来倒去，脑子直接宕机。
• 用栈实现队列（LeetCode 232）：反过来的套路，用两个栈模拟队列。看起来对称，实际坑位完全不同。
• 接雨水（LeetCode 42）：Hard 题。给你一个数组表示柱子高度，问下完雨能接多少水。暴力能写，但时间复杂度 O(n²)；优化到 O(n) 就得掏出单调栈。

这三道题不是孤立的。它们的背后藏着同一个东西：栈与队列——Java 集合框架里最"古老"也最"拧巴"的一对数据结构。Stack 类是 JDK 1.0 就有的"骨灰级"API，但它被官方自己判了死刑；Queue 接口体系设计精良，可很多人都没用对。

今天就沿着这三道面试题的线索，把栈和队列的源码、设计缺陷、工程实战、以及单调栈在接雨水里的威力一次讲透。

二、底层的时空解构与源码透视

2.1 Stack 源码分析——继承 Vector 为什么是设计灾难

先看 Stack 类的声明（JDK 17）：

public class Stack<E> extends Vector<E> {
public E push(E item) { addElement(item); return item; }
public synchronized E pop() { ... }
public synchronized E peek() { ... }
public boolean empty() { return size() == 0; }
public synchronized int search(Object o) { ... }
}

三行代码就能看出问题。Stack 继承了 Vector，而 Vector 是什么？是一个所有方法都加了 synchronized 的线程安全动态数组。Stack 的 pop、peek、search 也都带着 synchronized。

这意味着什么？即使你在单线程环境里用一个局部栈变量，每次 push/pop 都要走一遍锁竞争的逻辑。 这不是"线程安全"，这是"为不需要的东西买单"。

继承还带来了 API 污染。因为 Stack extends Vector，所以你可以对一个"栈"做这些事：

Stack<String> stack = new Stack<>();
stack.add(1, "插队"); // Vector 的按索引插入——栈的 LIFO 语义被彻底破坏
stack.removeElementAt(0); // 删除任意位置元素
stack.removeRange(0, 2); // 删除一个范围——这方法还是 protected 的，但子类能调用
stack.capacity(); // 查看底层数组容量——栈需要关心容量吗？

一个栈，被硬塞进了数组列表的全部操作。 这直接违反了面向对象设计的核心原则：组合优于继承（Composition over Inheritance）。Stack 不应该"是一个"Vector，它应该"持有一个"Vector（或者更好的选择：持有 ArrayDeque）。

Joshua Bloch 在《Effective Java》里明确指出：Stack 类是一个"兼容性遗物"，应该用 Deque 替代。

2.2 Deque 双端队列接口体系

JDK 6 引入的 Deque（Double Ended Queue）接口彻底改变了局面。来看继承关系：

Iterable → Collection → Queue → Deque → ArrayDeque / LinkedList

Deque 既可以用作栈（一端进出），也可以用作队列（一端进另一端出）。用 Deque 当栈的写法：

Deque<String> stack = new ArrayDeque<>();
stack.push("a"); // 等价于 addFirst
stack.pop(); // 等价于 removeFirst
stack.peek(); // 等价于 peekFirst

为什么 ArrayDeque 比 Stack 快？两个原因：

JDK 文档里 ArrayDeque 的注释写得很直白：“This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.”

2.3 Queue/Deque 常用 API 对比

Queue 和 Deque 的 API 有两套——一套抛异常，一套返回特殊值。很多新手栽在这上面：

记住：如果你不确定队列是否为空，用 offer/poll/peek。add/remove/element 在空队列或容量满时会抛异常，线上事故往往就是这么来的。

Deque 还额外提供两套方向 API：

一套接口，两种语义——栈和队列都能用 Deque 来搞定。

2.4 单调栈基础原理

单调栈（Monotonic Stack）指的是栈内元素始终保持单调递增或单调递减。它不是新的数据结构，而是栈的一种使用策略。

经典模板题——Next Greater Element（下一个更大元素）：

给定数组 nums，对每个元素，找出它右边第一个比它大的元素。

public int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // 存下标，单调递减栈
for (int i = 0; i < n; i++) {
// 当前元素破坏了栈的单调递减性 → 找到了前面元素的"下一个更大值"
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
// 栈里剩下的没有下一个更大元素
while (!stack.isEmpty()) {
result[stack.pop()] = –1;
}
return result;
}

时间复杂度 O(n)，因为每个元素最多入栈一次、出栈一次。把暴力解法的 O(n²) 压到 O(n)，单调栈的核心思想就一句话：我入栈之前，先清理掉所有比我小的元素，它们等的"下一个更大"就是我。

这个模板稍加变形，就能解接雨水、柱状图最大矩形、每日温度等十几道经典题。

三、"纯手工、零依赖"原创案例实战

3.1 IDE 撤销重做——用两个栈实现

IDE 里的 Ctrl+Z（撤销）和 Ctrl+Y（重做）是每个程序员每天都要按几十次的快捷键。背后的数据结构就是两个栈。

设计思路：一个 undoStack 存已执行的操作，一个 redoStack 存已撤销的操作。执行新操作 → 压入 undoStack 并清空 redoStack；撤销 → 从 undoStack 弹出压入 redoStack；重做 → 从 redoStack 弹出压回 undoStack。

完整实现（JDK 17）：

import java.util.ArrayDeque;
import java.util.Deque;

/**
* 模拟 IDE 的撤销/重做机制。
* 每次编辑操作记录为一条文本快照，撤销=回到上一个快照，重做=前进到下一个快照。
*/
public class UndoManager {
private final Deque<String> undoStack = new ArrayDeque<>();
private final Deque<String> redoStack = new ArrayDeque<>();

/** 执行一次编辑操作 */
public void edit(String newState) {
undoStack.push(newState);
redoStack.clear(); // 新操作清空重做历史
System.out.println("编辑: " + newState);
}

/** 撤销：回到上一个状态 */
public String undo() {
if (undoStack.size() <= 1) {
System.out.println("没有更多可撤销的操作");
return undoStack.isEmpty() ? "" : undoStack.peek();
}
redoStack.push(undoStack.pop());
System.out.println("撤销 -> " + undoStack.peek());
return undoStack.peek();
}

/** 重做：前进到下一个状态 */
public String redo() {
if (redoStack.isEmpty()) {
System.out.println("没有更多可重做的操作");
return undoStack.peek();
}
String restored = redoStack.pop();
undoStack.push(restored);
System.out.println("重做 -> " + restored);
return restored;
}

/** 当前状态 */
public String current() {
return undoStack.isEmpty() ? "" : undoStack.peek();
}

// 运行演示
public static void main(String[] args) {
UndoManager manager = new UndoManager();
manager.edit("Hello"); // 编辑: Hello
manager.edit("Hello World"); // 编辑: Hello World
manager.edit("Hello World!"); // 编辑: Hello World!
manager.undo(); // 撤销 -> Hello World
manager.undo(); // 撤销 -> Hello
manager.redo(); // 重做 -> Hello World
manager.edit("Hello Java"); // 编辑: Hello Java (重做历史被清空)
manager.redo(); // 没有更多可重做的操作
}
}

运行输出：

编辑: Hello
编辑: Hello World
编辑: Hello World!
撤销 -> Hello World
撤销 -> Hello
重做 -> Hello World
编辑: Hello Java
没有更多可重做的操作

关键点：第三步撤销了两次回到 “Hello”，然后又重做到 “Hello World”。此时如果执行新的编辑 “Hello Java”，redoStack.clear() 会把之前那条 “Hello World!” 的重做分支彻底丢弃——这正是 IDE 的标准行为：新操作刷新了历史树。

3.2 打印店排队模拟——用 Queue 管理打印任务队列

学校打印店高峰期，一堆 U 盘插着排队。店主的处理逻辑就是最经典的队列模型：先来先印（FIFO）。

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Random;

/**
* 模拟打印店的任务排队与处理。
* 每个打印任务有文件名和页数，处理器按 FIFO 顺序依次打印。
*/
public class PrintQueue {
// 打印任务
record PrintJob(String fileName, int pages) {}

private final Queue<PrintJob> queue = new ArrayDeque<>();
private final Random random = new Random();

/** 提交打印任务 */
public void submit(String fileName, int pages) {
PrintJob job = new PrintJob(fileName, pages);
boolean added = queue.offer(job); // 用 offer 而非 add，避免抛异常
if (added) {
System.out.println("提交任务: 《" + fileName + "》 " + pages + "页, 当前队列长度=" + queue.size());
}
}

/** 处理队列中所有任务 */
public void processAll() {
while (!queue.isEmpty()) {
PrintJob job = queue.poll(); // 用 poll 而非 remove
if (job == null) break;
// 模拟打印耗时
int time = job.pages * (random.nextInt(200) + 100); // 每页100~300ms
System.out.printf("打印中: 《%s》 %d页, 预计%dm%ds\\n",
job.fileName(), job.pages(), time / 60000, (time % 60000) / 1000);
try { Thread.sleep(time % 5000); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
System.out.println("完成: 《" + job.fileName() + "》");
}
System.out.println("所有任务打印完毕，队列为空。");
}

public static void main(String[] args) {
PrintQueue printQueue = new PrintQueue();
printQueue.submit("实验报告", 3);
printQueue.submit("毕业论文第一章", 12);
printQueue.submit("个人简历", 1);
printQueue.submit("课程论文", 8);
System.out.println("===== 开始处理队列 =====");
printQueue.processAll();
}
}

运行输出：

提交任务: 《实验报告》 3页, 当前队列长度=1
提交任务: 《毕业论文第一章》 12页, 当前队列长度=2
提交任务: 《个人简历》 1页, 当前队列长度=3
提交任务: 《课程论文》 8页, 当前队列长度=4
===== 开始处理队列 =====
打印中: 《实验报告》 3页, 预计0m1s
完成: 《实验报告》
打印中: 《毕业论文第一章》 12页, 预计0m2s
完成: 《毕业论文第一章》
打印中: 《个人简历》 1页, 预计0m0s
完成: 《个人简历》
打印中: 《课程论文》 8页, 预计0m1s
完成: 《课程论文》
所有任务打印完毕，队列为空。

这两个例子合在一起，恰好对应了 LeetCode 225 和 232 的本质——栈和队列不复杂，复杂的是怎么在工程约束（撤销需要保留历史、打印需要保证顺序）下把它们用对。

四、源码避坑指南与 Debug 日记

坑 ①：Stack 泄露了不该有的方法

前面已经提过，但实际操作中的后果比想象中严重。IDEA 补全时 Stack 对象点出来的方法列表里混着 add(int, E)、removeElement、capacity()、removeRange。团队里如果有人不了解背景，真的会这样写：

Stack<Task> taskStack = new Stack<>();
taskStack.add(2, urgentTask); // 把紧急任务插到第 2 位——stack 的 LIFO 被破坏了

Code Review 的时候很难发现，因为代码编译不过都不会报错，运行时逻辑悄悄就走偏了。

坑 ②：ArrayDeque 不支持 null 元素

这是文档里写了但很多人没注意到的一点。ArrayDeque 的 offer、push 等方法遇到 null 会直接抛 NullPointerException。而 LinkedList 做 Queue 时允许 null。如果你从 LinkedList 切到 ArrayDeque 提升性能，所有插入 null 的逻辑会原地爆炸。

坑 ③：LinkedList 做 Queue 时的内存踩坑

LinkedList 每个元素是一个 Node 对象（包含 item、prev、next 三个引用），比 ArrayDeque 的循环数组多了两倍的引用开销。如果队列里常年挂着几千条任务，LinkedList 的 GC 压力会明显高于 ArrayDeque。实测在 10 万元素的 push/pop 循环中，ArrayDeque 比 LinkedList 快约 30%~50%。

坑 ④：两个栈实现队列的性能陷阱

LeetCode 232 的经典解法：stackIn 负责 push，stackOut 负责 pop。关键优化是摊还分析——不要把 stackIn 全倒进 stackOut 然后立刻倒回来，而是只在 stackOut 为空时才一次性把 stackIn 倒过去。如果没有这个优化，每次 push 和 pop 都来回倒腾，时间复杂度会退化到 O(n) 而非摊还 O(1)。

五、面试连环炮 Mock Interview

5.1 为什么阿里巴巴规范和 JDK 官方都严禁使用 Stack 类？

面试官：你平时写 Java 用栈，一般怎么声明？

理性回答不是 Stack<String> s = new Stack<>()，而是：

Deque<String> stack = new ArrayDeque<>();

理由有三层。

第一层：继承泄露。 Stack 继承 Vector，导致 Vector 的二十几个方法全部暴露在栈的接口上。add(index, element)、removeElement、capacity、removeRange——这些方法有的能绕过 LIFO 约束，有的是 protected 但在子类里变成了可用。组合优于继承不是一句口号，Stack 就是反面教材。

第二层：synchronized 锁粒度粗。 Vector 的每个方法都加了 synchronized，Stack 继承过来之后 pop、peek、search 也都带着锁。单线程场景下这些锁是纯开销。即使多线程场景，这种"每个方法都加锁"的粗粒度同步也远不如 ConcurrentLinkedDeque 这类现代并发容器。

第三层：JDK 官方自己都放弃了它。 Stack 的 Javadoc 从 JDK 1.6 起就明确写了：

“A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.”

翻译成人话：我们当年犯了个错，现在有更好的东西了，别用这个。

阿里巴巴Java开发手册（泰山版）第11条：【强制】使用 Deque 代替 Stack 完成栈操作。

5.2 单调栈解"接雨水"——三种思路递进

面试官：接雨水这道题，你能给出几种解法？

解法一：暴力 O(n²)——按列求

对每一列，向左找最高柱子 leftMax，向右找最高柱子 rightMax。当前列能接的水 = min(leftMax, rightMax) – height[i]。每个列找左右最高都是 O(n)，总 O(n²)。

面试官听到这儿通常会点头但皱眉，因为暴力解写过太多遍了。

解法二：动态规划 O(n)——预计算左右最高

用两个数组 leftMax[i] 和 rightMax[i] 预存每个位置左右的最大高度。遍历三趟：一趟算 leftMax、一趟算 rightMax、一趟算雨水。时间 O(n)，空间 O(n)。

解法三：单调栈 O(n)——按行求

关键转变思路：不是按列计算，而是按行——找到每个"洼地"能接多少水。维护一个单调递减栈存下标。当前柱子比栈顶高时，说明栈顶位置形成了一个洼地：栈顶是"底"，弹出后的新栈顶是"左墙"，当前柱子是"右墙"。

public int trap(int[] height) {
Deque<Integer> stack = new ArrayDeque<>();
int water = 0;
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
int bottom = stack.pop(); // 洼地的底
if (stack.isEmpty()) break; // 没有左墙
int left = stack.peek(); // 左墙
int width = i – left – 1;
int depth = Math.min(height[left], height[i]) – height[bottom];
water += width * depth;
}
stack.push(i);
}
return water;
}

工业应用：单调栈不只用于接雨水。柱状图最大矩形（LeetCode 84）、每日温度（LeetCode 739）、股票跨度（LeetCode 901）背后都是同一套模板。在真实系统中，它能用于分析 CPU 负载曲线的峰值区间、内存占用的"波峰"持续时间——数据就是柱子，找"谷"和"峰"就是单调栈的活。

三种解法的递进，也是算法面试的标准路径：暴力→空间换时间→精巧的线性结构。面试官想看的不是一次给出最优解，而是这个递进过程。

六、通俗类比小结

最后用三个生活中的例子帮你把栈、队列、双端队列记住：

• 叠衣服：洗完叠好摞一摞，后叠的衣服在最上面，先穿的也是它——这就是栈（LIFO）。
• 打印店取号：小票上写着 042 号，前面还有 5 个人。先来的先印，后来的排队——这就是队列（FIFO）。
• 校门口的双向车道：车可以从东头进来从西头出去，也可以从西头进来从东头出去——这就是双端队列 Deque，两头都能进出。

用这三个例子去套今天讲的一切：Stack 别用了用 Deque → 就好像你叠衣服不需要关心衣架上第 3 件是什么材质（继承泄露的方法你没资格用）。offer/poll 代替 add/remove → 就好像取号机打出"请稍候"比直接黑屏要好（返回特殊值比抛异常更稳健）。