从 LIFO 到 JVM：堆栈的定义及其在 Java 中的应用 🌟
温馨提示：
本文最后更新于 2025年07月22日，已超过 4 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
1. 什么是堆栈（Stack）？
- 定义：一种后进先出（LIFO）的线性数据结构，最新入栈的元素最先出栈 (GeeksforGeeks)。
- 比喻：如同餐盘叠放，始终操作顶部盘子，即“只能从顶部进出”(知乎专栏)。
基本操作：
push()：将元素压入栈顶pop()：弹出并返回栈顶元素peek()/top()：查看栈顶但不移除isEmpty()：判断是否为空
时间复杂度均为 O(1)，空间复杂度 O(n) (CSDN博客)。
2. Java 中的堆栈实现方式
2.1 传统方式：java.util.Stack
- 继承自
Vector<E>（线程安全但较慢）(CSDN博客)。 - 常用方法：
push(),pop(),peek(),empty(),search()(GeeksforGeeks)。
Stack<Integer> stack = new Stack<>();
stack.push(10);
int top = stack.pop();
boolean empty = stack.empty();
2.2 推荐方式：Deque + ArrayDeque
- 推荐使用
Deque<Integer> stack = new ArrayDeque<>();性能更优，非线程安全(CSDN博客)。 - 常用操作：
push(),pop(),peek(),isEmpty(),size()。
3. Java 中 Stack 的典型应用场景
3.1 括号匹配验证
常见算法题，用栈实现：
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
// 左括号入栈，右括号比对并出栈
}
return stack.isEmpty();
应用场景包括编译器语法检查、HTML/XML 标签验证(CSDN博客)。
3.2 逆波兰表达式（后缀）求值
适用于表达式求值问题：
Deque<Integer> stack = new ArrayDeque<>();
for (String tok : tokens) {
if (isOperator(tok)) {
int b = stack.pop(), a = stack.pop();
stack.push(calc(a, b, tok));
} else {
stack.push(Integer.parseInt(tok));
}
}
return stack.pop();
例如 "2 1 + 3 *" → (2+1)*3 = 9(CSDN博客)。
3.3 函数调用与 JVM 栈帧
- JVM 为每个线程维护 调用栈（Call Stack）。
- 方法调用创建栈帧，包含局部变量、操作数栈、返回地址等信息；方法返回后对应栈帧自动出栈(阿里云开发者社区)。
- 自增长/收缩，自动管理，使得 Java 内存安全、高效。
3.4 非递归实现深度优先搜索（DFS）
以二叉树遍历为例：
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode n = stack.pop();
System.out.print(n.val + " ");
if (n.right != null) stack.push(n.right);
if (n.left != null) stack.push(n.left);
}
输出先访问根结点，然后左子树再右子树(阿里云开发者社区)。
4. 注意事项 & 最佳实践
- 数组实现（如
ArrayDeque）容量自动扩张，但需关心扩容机制； - 多线程环境下需线程安全栈，可使用
ConcurrentLinkedDeque； - 使用
pop()和peek()前务必判断isEmpty()避免EmptyStackException或NoSuchElementException； - 某些递归场景可替代为显式栈实现，提高灵活性与可控性。
5. 小结
本文从定义、Java 实现、核心操作，到实战应用如括号匹配、表达式求值、函数调用与 DFS 遍历，系统讲解了堆栈在 Java 中的职责与使用场景。
掌握这一基础数据结构，不仅能编写高效算法，还能更深入理解 JVM 内存管理和程序执行机制。希望这篇原创且图文并茂的博文，能帮助初学者搭建扎实基础，踏出编程的第一步！
正文到此结束
- 本文标签： 堆栈 栈 Java数据结构
- 本文链接： https://code.itptg.com/article/81
- 版权声明： 本文由老魏原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
