Java 中的 Stack 类：深入解析与实践

简介

在 Java 编程世界里，Stack 类是一个用于实现栈数据结构的类。栈是一种遵循后进先出（LIFO，Last In First Out）原则的数据结构，就像一叠盘子，最后放上去的盘子会最先被拿走。Stack 类提供了一系列方法来操作栈中的元素，在很多算法和实际应用场景中都有广泛的使用。本文将详细介绍 Stack 类的基础概念、使用方法、常见实践以及最佳实践，帮助你更好地掌握和运用它。

基础概念

栈（Stack）是一种抽象数据类型，它具有特定的操作规则。栈有两个主要操作：压入（push）和弹出（pop）。当一个元素被压入栈时，它被添加到栈的顶部；当一个元素被弹出时，位于栈顶部的元素被移除并返回。此外，栈还有一个查看顶部元素（peek）的操作，它返回栈顶元素但不将其从栈中移除。

在 Java 中，Stack 类继承自 Vector 类，它是线程安全的。这意味着在多线程环境下，多个线程可以安全地访问和操作 Stack 对象，而不会出现数据不一致的问题。

使用方法

创建 Stack 对象

要使用 Stack 类，首先需要创建一个 Stack 对象。可以使用以下方式创建：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
    }
}

在上述代码中，创建了一个存储 Integer 类型元素的 Stack 对象。

常用方法介绍

push(E item)：将元素压入栈顶。

stack.push(10);
stack.push(20);
stack.push(30);

在这段代码中，依次将 10、20 和 30 压入栈中。

pop()：移除并返回栈顶元素。如果栈为空，调用此方法会抛出 EmptyStackException 异常。

int topElement = stack.pop();
System.out.println("弹出的元素: " + topElement);

上述代码弹出栈顶元素 30 并打印。

peek()：返回栈顶元素，但不移除它。如果栈为空，调用此方法会抛出 EmptyStackException 异常。

int peekElement = stack.peek();
System.out.println("栈顶元素: " + peekElement);

这段代码返回栈顶元素 20 并打印。

isEmpty()：判断栈是否为空。如果栈中没有元素，返回 true，否则返回 false。

boolean isEmpty = stack.isEmpty();
System.out.println("栈是否为空: " + isEmpty);

search(Object o)：在栈中搜索指定元素，并返回从栈顶到该元素的距离。如果元素不存在，返回 -1。

int searchResult = stack.search(10);
System.out.println("元素 10 的位置: " + searchResult);

常见实践

表达式求值

栈在表达式求值中非常有用，特别是对于后缀表达式（逆波兰表达式）。以下是一个简单的后缀表达式求值示例：

import java.util.Stack;

public class PostfixEvaluation {
    public static int evaluatePostfix(String postfix) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < postfix.length(); i++) {
            char ch = postfix.charAt(i);
            if (Character.isDigit(ch)) {
                stack.push(ch - '0');
            } else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                switch (ch) {
                    case '+':
                        stack.push(operand1 + operand2);
                        break;
                    case '-':
                        stack.push(operand1 - operand2);
                        break;
                    case '*':
                        stack.push(operand1 * operand2);
                        break;
                    case '/':
                        stack.push(operand1 / operand2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String postfix = "34+2*";
        int result = evaluatePostfix(postfix);
        System.out.println("后缀表达式结果: " + result); 
    }
}

在这个示例中，遍历后缀表达式的每个字符，遇到数字就压入栈，遇到操作符就从栈中弹出两个操作数进行计算，并将结果压回栈中。最后栈顶元素就是表达式的结果。

括号匹配

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

import java.util.Stack;

public class BracketMatcher {
    public static boolean checkBrackets(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

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

在这个示例中，遍历表达式的每个字符，遇到左括号就压入栈，遇到右括号就从栈中弹出一个左括号进行匹配。如果匹配失败或栈为空时遇到右括号，返回 false。最后检查栈是否为空，如果为空则括号匹配，否则不匹配。

最佳实践

性能优化

由于 Stack 类继承自 Vector 类，它是线程安全的，但在单线程环境下，这会带来一定的性能开销。如果在单线程环境中使用栈，可以考虑使用 Deque 接口的实现类，如 ArrayDeque。ArrayDeque 性能更好，并且提供了与 Stack 类似的方法来操作栈。

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        int topElement = stack.pop();
        System.out.println("弹出的元素: " + topElement); 

        int peekElement = stack.peek();
        System.out.println("栈顶元素: " + peekElement); 
    }
}

替代方案选择

在某些情况下，Stack 类可能不是最佳选择。例如，当需要频繁地在栈的两端进行操作时，Deque 接口提供了更丰富的操作方法。如果需要一个线程安全的栈，可以考虑使用 ConcurrentLinkedDeque，它在多线程环境下性能更好。

小结

Stack 类是 Java 中实现栈数据结构的一个重要类，它提供了方便的方法来操作栈中的元素。通过了解 Stack 类的基础概念、使用方法、常见实践以及最佳实践，你可以在不同的编程场景中灵活运用栈数据结构。在实际应用中，要根据具体需求选择合适的数据结构和实现类，以确保程序的性能和正确性。

参考资料

Oracle Java Documentation - Stack
《Effective Java》 - Joshua Bloch
《数据结构与算法分析（Java 语言描述）》 - Mark Allen Weiss

希望这篇博客能帮助你深入理解并高效使用 Java 中的 Stack 类。如果你有任何问题或建议，欢迎在评论区留言。