java Stack详解
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()); // 30
System.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 的使用场景依然广泛，尤其在处理需要递归、逆序或模拟调用栈的问题中表现优异。
原文地址：https://blog.csdn.net/T_Y_F_/article/details/143808128
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！