Java 中的 Stack 类详解
Stack 是 Java 提供的一种**后进先出（LIFO）**的栈数据结构，继承自 Vector 类，是 java.util 包的一部分。它适合处理具有递归特性或需要逆序操作的问题。
1. Stack 类的声明
Stack 是一个泛型类，允许存储任何类型的对象：
public class Stack<E> extends Vector<E>
由于 Stack 继承自 Vector，它拥有 Vector 的所有方法，同时也增加了一些专门为栈设计的方法。
2. Stack 的基本操作方法
以下是 Stack 提供的主要方法及其功能：
栈特有方法：
| 方法名 | 描述 |
|---|---|
push(E item) | 将元素压入栈顶。 |
pop() | 移除并返回栈顶元素。如果栈为空，则抛出 EmptyStackException。 |
peek() | 返回栈顶元素，但不移除。如果栈为空，则抛出 EmptyStackException。 |
isEmpty() | 检查栈是否为空。 |
search(Object o) | 返回对象在栈中的位置（基于1的索引）。如果对象不存在，返回 -1。 |
从 Vector 继承的方法：
| 方法名 | 描述 |
|---|---|
size() | 返回栈的大小（元素数量）。 |
clear() | 清空栈中的所有元素。 |
contains(Object o) | 检查栈中是否包含指定元素。 |
3. 代码示例
以下是一些常见的 Stack 操作示例：
(1) 基本操作
import java.util.Stack;public class StackExample {public static void main(String[] args) {// 创建一个栈Stack<Integer> stack = new Stack<>();// 入栈stack.push(10);stack.push(20);stack.push(30);System.out.println("Stack after pushes: " + stack); // [10, 20, 30]// 查看栈顶元素System.out.println("Top element: " + stack.peek()); // 30// 出栈System.out.println("Popped element: " + stack.pop()); // 30System.out.println("Stack after pop: " + stack); // [10, 20]// 检查是否为空System.out.println("Is stack empty? " + stack.isEmpty()); // false// 查找元素System.out.println("Position of 10: " + stack.search(10)); // 2}
}
(2) 栈的应用：括号匹配
判断字符串中的括号是否匹配。
import java.util.Stack;public class BracketMatching {public static boolean isValid(String str) {Stack<Character> stack = new Stack<>();for (char ch : str.toCharArray()) {if (ch == '(' || ch == '{' || ch == '[') {stack.push(ch); // 左括号入栈} else if (ch == ')' && !stack.isEmpty() && stack.peek() == '(') {stack.pop(); // 匹配的右括号出栈} else if (ch == '}' && !stack.isEmpty() && stack.peek() == '{') {stack.pop();} else if (ch == ']' && !stack.isEmpty() && stack.peek() == '[') {stack.pop();} else {return false; // 不匹配}}return stack.isEmpty(); // 栈为空说明匹配成功}public static void main(String[] args) {String str = "{[()]}";System.out.println("Is valid: " + isValid(str)); // true}
}
(3) 深度优先搜索（DFS）
用栈实现递归的非递归版。
import java.util.*;public class DFSWithStack {public static void main(String[] args) {Map<Integer, List<Integer>> graph = new HashMap<>();graph.put(1, Arrays.asList(2, 3));graph.put(2, Arrays.asList(4, 5));graph.put(3, Collections.singletonList(6));graph.put(4, Collections.emptyList());graph.put(5, Collections.emptyList());graph.put(6, Collections.emptyList());Stack<Integer> stack = new Stack<>();Set<Integer> visited = new HashSet<>();stack.push(1); // 起点while (!stack.isEmpty()) {int node = stack.pop();if (!visited.contains(node)) {System.out.println("Visited: " + node);visited.add(node);// 将邻居节点压栈for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {stack.push(neighbor);}}}}
}
输出：
Visited: 1
Visited: 3
Visited: 6
Visited: 2
Visited: 5
Visited: 4
4. 注意事项
(1) 线程安全
Stack是线程安全的，因为它继承自Vector，并且Vector的方法都被同步（synchronized）保护。- 如果不需要线程安全，推荐使用
Deque（如ArrayDeque）代替Stack，性能更高。
(2) 栈溢出
如果栈使用不当，可能会导致内存溢出问题（特别是在递归实现中）。
(3) 替代数据结构
推荐使用 Deque 替代 Stack，它是 Java Collections Framework 的一部分，效率和功能更优。
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.pop();
5. Stack 的使用场景
- 递归模拟：将函数调用展开为栈操作。
- 括号匹配：验证表达式中的括号是否匹配。
- 表达式求值：中缀表达式转后缀表达式或直接求值。
- 深度优先搜索（DFS）：实现图的遍历。
- 撤销操作：例如文本编辑器的撤销功能。
6. 优缺点
优点：
- 简单易用，方法直观。
- 线程安全（适用于多线程环境）。
缺点：
- 继承自
Vector，导致性能不如Deque。 - 多线程环境使用可能导致不必要的开销。
总结
Stack 是 Java 中经典的 LIFO 数据结构，功能简单且方便使用。但在现代开发中，推荐更多地使用 Deque 作为栈的实现方式。Stack 的使用场景依然广泛，尤其在处理需要递归、逆序或模拟调用栈的问题中表现优异。
