Java 中的栈（Stacks in Java）

简介

在 Java 编程中，栈（Stack）是一种非常重要的数据结构，它遵循后进先出（LIFO，Last-In-First-Out）的原则。栈在很多场景下都有广泛的应用，例如表达式求值、回溯算法、方法调用等。本文将详细介绍 Java 中栈的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并高效使用栈。

基础概念

栈的定义

栈是一种线性数据结构，它限制了元素的插入和删除操作只能在栈的一端进行，这一端被称为栈顶（Top）。新元素被添加到栈顶（入栈操作，push），而删除操作也只能从栈顶进行（出栈操作，pop）。

后进先出原则

后进先出原则意味着最后进入栈的元素会最先被移除。例如，如果依次将元素 A、B、C 入栈，那么出栈的顺序将是 C、B、A。

Java 中的栈实现

在 Java 中，java.util.Stack 类是栈的一个具体实现，它继承自 Vector 类。不过，从 Java 1.6 开始，更推荐使用 Deque 接口的实现类 ArrayDeque 来模拟栈，因为 ArrayDeque 比 Stack 类更高效，并且线程不安全的情况下性能更好。

使用方法

使用 `java.util.Stack` 类

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.peek());

        // 出栈操作
        int poppedElement = stack.pop();
        System.out.println("出栈元素: " + poppedElement);

        // 检查栈是否为空
        System.out.println("栈是否为空: " + stack.isEmpty());

        // 查看栈的大小
        System.out.println("栈的大小: " + stack.size());
    }
}

使用 `ArrayDeque` 模拟栈

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeStackExample {
    public static void main(String[] args) {
        // 创建一个 Deque 对象来模拟栈
        Deque<Integer> stack = new ArrayDeque<>();

        // 入栈操作
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // 查看栈顶元素
        System.out.println("栈顶元素: " + stack.peek());

        // 出栈操作
        int poppedElement = stack.pop();
        System.out.println("出栈元素: " + poppedElement);

        // 检查栈是否为空
        System.out.println("栈是否为空: " + stack.isEmpty());

        // 查看栈的大小
        System.out.println("栈的大小: " + stack.size());
    }
}

常见实践

表达式求值

栈可以用于计算中缀表达式的值。例如，计算 3 + 4 * 2 的值：

import java.util.Stack;

public class ExpressionEvaluation {
    public static int evaluate(String expression) {
        Stack<Integer> numbers = new Stack<>();
        Stack<Character> operators = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            if (Character.isDigit(ch)) {
                numbers.push(ch - '0');
            } else if (ch == '+' || ch == '-') {
                while (!operators.isEmpty() && (operators.peek() == '+' || operators.peek() == '-')) {
                    int num2 = numbers.pop();
                    int num1 = numbers.pop();
                    char op = operators.pop();
                    numbers.push(applyOperation(num1, num2, op));
                }
                operators.push(ch);
            } else if (ch == '*' || ch == '/') {
                while (!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '/')) {
                    int num2 = numbers.pop();
                    int num1 = numbers.pop();
                    char op = operators.pop();
                    numbers.push(applyOperation(num1, num2, op));
                }
                operators.push(ch);
            }
        }

        while (!operators.isEmpty()) {
            int num2 = numbers.pop();
            int num1 = numbers.pop();
            char op = operators.pop();
            numbers.push(applyOperation(num1, num2, op));
        }

        return numbers.pop();
    }

    public static int applyOperation(int num1, int num2, char op) {
        switch (op) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            case '/':
                if (num2 == 0) {
                    throw new UnsupportedOperationException("Cannot divide by zero");
                }
                return num1 / num2;
        }
        return 0;
    }

    public static void main(String[] args) {
        String expression = "3+4*2";
        int result = evaluate(expression);
        System.out.println("表达式结果: " + result);
    }
}

回溯算法

栈可以用于实现回溯算法，例如解决迷宫问题。在回溯过程中，我们可以使用栈来记录路径。

最佳实践

优先使用 `ArrayDeque` 代替 `Stack`

如前面所述，ArrayDeque 比 Stack 类更高效，特别是在单线程环境下。因此，建议优先使用 ArrayDeque 来模拟栈。

异常处理

在使用栈时，需要注意异常处理。例如，当栈为空时调用 pop() 或 peek() 方法会抛出 EmptyStackException 异常，因此在调用这些方法之前最好先检查栈是否为空。

内存管理

栈中的元素如果是对象，要注意对象的生命周期。当栈中的元素不再使用时，要及时将其从栈中移除，避免内存泄漏。

小结

本文详细介绍了 Java 中栈的基础概念、使用方法、常见实践以及最佳实践。栈是一种遵循后进先出原则的数据结构，在 Java 中可以使用 java.util.Stack 类或 ArrayDeque 来实现。常见实践包括表达式求值和回溯算法等。在使用栈时，建议优先使用 ArrayDeque，并注意异常处理和内存管理。

参考资料

《数据结构与算法分析——Java 语言描述》