从 LIFO 到 JVM：堆栈的定义及其在 Java 中的应用 🌟

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 内存管理和程序执行机制。希望这篇原创且图文并茂的博文，能帮助初学者搭建扎实基础，踏出编程的第一步！