Java ArrayDeque 与 Stack：深入解析与实践
简介
在 Java 的集合框架中，ArrayDeque 和 Stack 是两个用于处理栈和队列相关操作的数据结构。Stack 类是 Java 早期版本中用于实现栈数据结构的类，而 ArrayDeque 是 Java 1.6 引入的，它既可以当作栈使用，也可以当作队列使用。理解它们的基础概念、使用方法以及最佳实践，对于编写高效且正确的代码至关重要。本文将详细探讨这两个数据结构，帮助读者更好地掌握它们在实际项目中的应用。
目录
- 基础概念
- ArrayDeque
- Stack
- 使用方法
- ArrayDeque 作为栈使用
- Stack 的使用
- 常见实践
- 表达式求值
- 深度优先搜索（DFS）
- 最佳实践
- 性能考量
- 选择合适的数据结构
- 小结
基础概念
ArrayDeque
ArrayDeque 是一个基于数组实现的双端队列（Deque，即 Double - ended Queue）。它允许在队列的两端进行插入和删除操作，既可以当作栈使用（后进先出，LIFO），也可以当作队列使用（先进先出，FIFO）。ArrayDeque 是非线程安全的，在单线程环境下性能较高。
Stack
Stack 类是一个较老的类，它继承自 Vector。它是一个典型的栈数据结构，遵循后进先出（LIFO）的原则。与 ArrayDeque 不同，Stack 是线程安全的，但由于其实现方式和线程安全机制，在单线程环境下性能相对较差。
使用方法
ArrayDeque 作为栈使用
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeAsStackExample {
public static void main(String[] args) {
// 创建一个 ArrayDeque 对象作为栈
Deque<Integer> stack = new ArrayDeque<>();
// 入栈操作
stack.push(1);
stack.push(2);
stack.push(3);
// 查看栈顶元素
System.out.println("栈顶元素: " + stack.peek());
// 出栈操作
while (!stack.isEmpty()) {
System.out.println("出栈元素: " + stack.pop());
}
}
}
在上述代码中：
1. 首先创建了一个 ArrayDeque 对象，并将其当作栈使用。
2. 使用 push 方法将元素压入栈中。
3. 使用 peek 方法查看栈顶元素，而不弹出元素。
4. 使用 pop 方法弹出栈顶元素，并在循环中依次将所有元素出栈。
Stack 的使用
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// 创建一个 Stack 对象
Stack<Integer> stack = new Stack<>();
// 入栈操作
stack.push(1);
stack.push(2);
stack.push(3);
// 查看栈顶元素
System.out.println("栈顶元素: " + stack.peek());
// 出栈操作
while (!stack.isEmpty()) {
System.out.println("出栈元素: " + stack.pop());
}
}
}
这段代码与 ArrayDeque 作为栈使用的代码结构类似，只是使用了 Stack 类。Stack 类也提供了 push、peek 和 pop 方法来进行栈的基本操作。
常见实践
表达式求值
表达式求值是栈的一个常见应用场景。以下是一个简单的中缀表达式求值的示例，使用 ArrayDeque 作为栈：
import java.util.ArrayDeque;
import java.util.Deque;
public class ExpressionEvaluation {
public static int evaluateExpression(String expression) {
Deque<Integer> values = new ArrayDeque<>();
Deque<Character> operators = new ArrayDeque<>();
for (int i = 0; i < expression.length(); i++) {
if (Character.isDigit(expression.charAt(i))) {
int val = 0;
while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
val = val * 10 + expression.charAt(i) - '0';
i++;
}
values.push(val);
} else if (expression.charAt(i) == '(') {
operators.push(expression.charAt(i));
} else if (expression.charAt(i) == ')') {
while (!operators.isEmpty() && operators.peek()!= '(') {
values.push(applyOperator(operators.pop(), values.pop(), values.pop()));
}
operators.pop(); // 弹出 '('
} else if (isOperator(expression.charAt(i))) {
while (!operators.isEmpty() && precedence(operators.peek()) >= precedence(expression.charAt(i))) {
values.push(applyOperator(operators.pop(), values.pop(), values.pop()));
}
operators.push(expression.charAt(i));
}
}
while (!operators.isEmpty()) {
values.push(applyOperator(operators.pop(), values.pop(), values.pop()));
}
return values.pop();
}
private static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
private static int precedence(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return -1;
}
}
private static int applyOperator(char operator, int b, int a) {
switch (operator) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default:
return 0;
}
}
public static void main(String[] args) {
String expression = "3 + 5 * 2 / ( 7 - 2 )";
System.out.println("表达式结果: " + evaluateExpression(expression));
}
}
在这个示例中，我们使用两个栈，一个用于存储操作数（values），另一个用于存储操作符（operators）。通过遍历表达式字符串，根据操作符的优先级和括号的匹配情况，逐步计算表达式的值。
深度优先搜索（DFS）
在图的遍历中，深度优先搜索可以使用栈来实现。以下是一个简单的图的 DFS 实现，使用 ArrayDeque 作为栈：
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
public class DFSExample {
private Map<Integer, boolean[]> visited;
private Map<Integer, int[]> adj;
public DFSExample(int vertices) {
visited = new HashMap<>();
adj = new HashMap<>();
for (int i = 0; i < vertices; i++) {
visited.put(i, new boolean[1]);
adj.put(i, new int[0]);
}
}
public void addEdge(int src, int dest) {
int[] oldAdj = adj.get(src);
int[] newAdj = new int[oldAdj.length + 1];
System.arraycopy(oldAdj, 0, newAdj, 0, oldAdj.length);
newAdj[oldAdj.length] = dest;
adj.put(src, newAdj);
}
public void dfs(int start) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int vertex = stack.pop();
if (!visited.get(vertex)[0]) {
System.out.print(vertex + " ");
visited.get(vertex)[0] = true;
int[] neighbors = adj.get(vertex);
for (int i = neighbors.length - 1; i >= 0; i--) {
int neighbor = neighbors[i];
if (!visited.get(neighbor)[0]) {
stack.push(neighbor);
}
}
}
}
}
public static void main(String[] args) {
DFSExample graph = new DFSExample(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
System.out.println("从顶点 2 开始的 DFS 遍历:");
graph.dfs(2);
}
}
在这个示例中，我们定义了一个简单的图，并使用 ArrayDeque 实现了深度优先搜索。通过将顶点入栈和出栈，我们可以遍历图中的节点，并标记已经访问过的节点，以避免重复访问。
最佳实践
性能考量
- ArrayDeque：在单线程环境下，
ArrayDeque的性能通常优于Stack。因为ArrayDeque是非线程安全的，它避免了线程同步带来的开销。此外，ArrayDeque的实现相对更紧凑和高效，适合大多数栈和队列的操作场景。 - Stack：由于
Stack是线程安全的，在多线程环境下，如果需要对栈进行并发访问，Stack是一个选择。但在单线程环境下，由于其线程安全机制带来的性能损耗，应优先考虑ArrayDeque。
选择合适的数据结构
- 如果只需要一个简单的栈结构，并且在单线程环境下，
ArrayDeque是首选。它提供了高效的栈操作方法，并且性能较好。 - 如果需要线程安全的栈，或者在代码中已经大量使用了
Vector相关的类（因为Stack继承自Vector），可以考虑使用Stack。但在多线程环境下，也可以考虑使用并发安全的栈实现，如ConcurrentLinkedDeque。
小结
本文详细介绍了 Java 中的 ArrayDeque 和 Stack 数据结构。我们了解了它们的基础概念、使用方法、常见实践以及最佳实践。ArrayDeque 作为一个功能强大且高效的数据结构，在大多数情况下，尤其是单线程环境下，是实现栈和队列操作的理想选择。而 Stack 虽然是一个较老的类，但在特定的多线程场景下仍有其应用价值。通过掌握这两个数据结构的特点和使用方法，开发者可以更加灵活地编写高效、健壮的代码。希望本文能帮助读者更好地理解和运用 ArrayDeque 和 Stack，在实际项目中发挥它们的优势。