跳到主要内容

Java Stack

介绍​

在 Java 中，Stack 是一种遵循 后进先出（LIFO, Last In First Out） 原则的数据结构。这意味着最后添加到栈中的元素会最先被移除。栈通常用于需要回溯操作的场景，例如函数调用栈、表达式求值、括号匹配等。

Java 提供了 Stack 类，它是 Vector 的子类，因此支持动态增长。Stack 类提供了基本的栈操作，如 push、pop、peek 等。

基本操作​

1. 创建栈​

在 Java 中，可以使用 Stack 类来创建一个栈对象：

java
import java.util.Stack;

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

2. 添加元素（Push）​

使用 push 方法将元素添加到栈的顶部：

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

3. 移除元素（Pop）​

使用 pop 方法移除并返回栈顶的元素：

java
int topElement = stack.pop(); // 返回 30

4. 查看栈顶元素（Peek）​

使用 peek 方法查看栈顶的元素，但不移除它：

java
int topElement = stack.peek(); // 返回 20

5. 检查栈是否为空​

使用 isEmpty 方法检查栈是否为空：

java
boolean isEmpty = stack.isEmpty(); // 返回 false

6. 获取栈的大小​

使用 size 方法获取栈中元素的数量：

java
int size = stack.size(); // 返回 2

实际案例​

案例 1：括号匹配​

栈的一个常见应用是检查表达式中的括号是否匹配。例如，检查字符串 "(a + b) * (c - d)" 中的括号是否正确闭合。

java
import java.util.Stack;

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

    public static void main(String[] args) {
        String expression = "(a + b) * (c - d)";
        System.out.println(isBalanced(expression)); // 输出 true
    }
}

案例 2：逆波兰表达式求值​

逆波兰表达式（RPN）是一种不需要括号的数学表达式表示法。栈可以用于计算逆波兰表达式的值。

java
import java.util.Stack;

public class RPNCalculator {
    public static int evaluateRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int d = stack.pop();
                    int c = stack.pop();
                    stack.push(c / d);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] expression = {"2", "1", "+", "3", "*"};
        System.out.println(evaluateRPN(expression)); // 输出 9
    }
}

总结​

Stack 是一种简单但强大的数据结构，适用于许多需要回溯操作的场景。通过 push、pop、peek 等基本操作，我们可以轻松地管理栈中的元素。在实际应用中，栈常用于括号匹配、表达式求值、函数调用栈等场景。

附加资源​

练习​

  1. 实现一个栈，支持 push、pop、peek 和 isEmpty 操作。
  2. 编写一个程序，检查一个字符串中的括号是否匹配。
  3. 使用栈实现一个简单的计算器，支持加减乘除运算。
提示

在编写代码时，记得处理栈为空的情况，避免 EmptyStackException。