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 提供的主要方法及其功能：

栈特有方法：

从 Vector 继承的方法：

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 的使用场景依然广泛，尤其在处理需要递归、逆序或模拟调用栈的问题中表现优异。