Java 栈（Stack）全面解析

简介

在 Java 编程中，栈（Stack）是一种非常重要的数据结构，它遵循后进先出（LIFO - Last In First Out）的原则。就像一摞盘子，最后放上去的盘子总是最先被拿走。Java 提供了 java.util.Stack 类来实现栈的基本操作，同时在实际应用中也可以使用 Deque 接口的实现类（如 ArrayDeque）来替代 Stack 类，以获得更好的性能。本文将详细介绍 Java 栈的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并高效使用 Java 栈。

基础概念

栈的定义

栈是一种线性数据结构，它只允许在栈顶进行插入（入栈，push）和删除（出栈，pop）操作。栈的底部是固定的，新元素总是添加到栈顶，并且只能从栈顶移除元素。这种特性使得栈非常适合处理需要后进先出顺序的任务。

Java 中的栈实现

Java 提供了 java.util.Stack 类来实现栈的功能，它继承自 Vector 类，因此是线程安全的。不过，由于 Vector 类的同步机制会带来一定的性能开销，在非线程安全的场景下，更推荐使用 Deque 接口的实现类（如 ArrayDeque）来替代 Stack 类。

使用方法

`java.util.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());
    }
}

使用 `Deque` 接口替代 `Stack` 类

在非线程安全的场景下，可以使用 ArrayDeque 类来实现栈的功能，示例代码如下：

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

public class DequeAsStackExample {
    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());
    }
}

常见实践

表达式求值

栈可以用于计算表达式的值，例如后缀表达式（逆波兰表达式）的求值。以下是一个简单的后缀表达式求值的示例代码：

import java.util.Stack;

public class PostfixExpressionEvaluation {
    public static int evaluatePostfix(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                int result = applyOperation(token, operand1, operand2);
                stack.push(result);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    private static boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    private static int applyOperation(String operator, int operand1, int operand2) {
        switch (operator) {
            case "+":
                return operand1 + operand2;
            case "-":
                return operand1 - operand2;
            case "*":
                return operand1 * operand2;
            case "/":
                return operand1 / operand2;
            default:
                throw new IllegalArgumentException("无效的运算符: " + operator);
        }
    }

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

括号匹配检查

栈可以用于检查表达式中的括号是否匹配。以下是一个简单的括号匹配检查的示例代码：

import java.util.Stack;

public class ParenthesesMatching {
    public static boolean isMatching(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char c : expression.toCharArray()) {
            if (isOpeningBracket(c)) {
                stack.push(c);
            } else if (isClosingBracket(c)) {
                if (stack.isEmpty() || !isMatchingPair(stack.pop(), c)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    private static boolean isOpeningBracket(char c) {
        return c == '(' || c == '[' || c == '{';
    }

    private static boolean isClosingBracket(char c) {
        return c == ')' || c == ']' || c == '}';
    }

    private static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') || (opening == '[' && closing == ']') || (opening == '{' && closing == '}');
    }

    public static void main(String[] args) {
        String expression = "{[()]}";
        boolean result = isMatching(expression);
        System.out.println("括号是否匹配: " + result);
    }
}

最佳实践

选择合适的实现类

在非线程安全的场景下，优先使用 Deque 接口的实现类（如 ArrayDeque）来替代 java.util.Stack 类，因为 ArrayDeque 没有同步机制，性能更好。

异常处理

在进行栈操作时，要注意处理可能出现的异常，例如 EmptyStackException。在调用 pop() 或 peek() 方法之前，最好先检查栈是否为空。

避免栈溢出

在使用递归算法时，要注意避免栈溢出。可以考虑使用迭代算法来替代递归算法，或者调整递归的终止条件。

小结

本文详细介绍了 Java 栈的基础概念、使用方法、常见实践以及最佳实践。栈是一种非常重要的数据结构，遵循后进先出的原则，在 Java 中可以使用 java.util.Stack 类或 Deque 接口的实现类来实现栈的功能。栈在表达式求值、括号匹配检查等场景中有广泛的应用。在使用栈时，要选择合适的实现类，注意异常处理，避免栈溢出。

参考资料

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