跳转至

Java 中 Stack 类方法解析

简介

在 Java 编程中，Stack 类是一个后进先出（LIFO）的容器，它继承自 Vector 类。Stack 类提供了一系列方法来操作栈中的元素，对于需要实现特定数据处理逻辑，如表达式求值、回溯算法等场景非常有用。本文将详细介绍 Stack 类的方法，帮助读者更好地理解和使用这个类。

目录

  1. 基础概念
  2. 使用方法
    • 构造函数
    • 核心方法
  3. 常见实践
    • 表达式求值
    • 深度优先搜索（DFS）中的回溯
  4. 最佳实践
  5. 小结
  6. 参考资料

基础概念

Stack 类遵循后进先出的原则，就像一叠盘子。最后放入的盘子在最上面，最先被取出。在 Java 中，Stack 类定义在 java.util 包下，它继承自 Vector 类，这意味着它拥有 Vector 类的所有特性和方法，同时还额外提供了一些用于栈操作的方法。

使用方法

构造函数

Stack 类只有一个无参构造函数：

Stack<E> stack = new Stack<>();

这个构造函数创建一个空的栈。

核心方法

  1. push(E item) 将元素压入栈顶。
Stack<String> stack = new Stack<>();
stack.push("Apple");
stack.push("Banana");
  1. pop() 移除并返回栈顶元素。如果栈为空，会抛出 EmptyStackException。
String topElement = stack.pop();
System.out.println(topElement); // 输出 Banana
  1. peek() 返回栈顶元素，但不移除它。如果栈为空，会抛出 EmptyStackException。
String peekElement = stack.peek();
System.out.println(peekElement); // 输出 Apple
  1. isEmpty() 检查栈是否为空，如果为空返回 true，否则返回 false。
boolean isEmpty = stack.isEmpty();
System.out.println(isEmpty); // 输出 false
  1. search(Object o) 在栈中搜索指定元素，返回从栈顶到该元素的距离。如果元素不存在，返回 -1。
int distance = stack.search("Apple");
System.out.println(distance); // 输出 1

常见实践

表达式求值

使用栈可以实现简单的表达式求值。例如，对于后缀表达式（逆波兰表达式）的求值：

import java.util.Stack;

public class PostfixEvaluator {
    public static int evaluate(String postfix) {
        Stack<Integer> stack = new Stack<>();
        for (char c : postfix.toCharArray()) {
            if (Character.isDigit(c)) {
                stack.push(c - '0');
            } else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                switch (c) {
                    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 = evaluate(postfix);
        System.out.println("结果: " + result); // 输出 14
    }
}

深度优先搜索（DFS）中的回溯

在深度优先搜索算法中，栈可以用来实现回溯。例如，在一个简单的迷宫搜索问题中：

import java.util.Stack;

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class MazeSolver {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static final int MAZE_SIZE = 5;
    private static int[][] maze = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 1, 0}
    };

    public static boolean solveMaze() {
        Stack<Point> stack = new Stack<>();
        stack.push(new Point(0, 0));
        maze[0][0] = -1;

        while (!stack.isEmpty()) {
            Point current = stack.peek();
            if (current.x == MAZE_SIZE - 1 && current.y == MAZE_SIZE - 1) {
                return true;
            }
            boolean foundNext = false;
            for (int[] dir : DIRECTIONS) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];
                if (newX >= 0 && newX < MAZE_SIZE && newY >= 0 && newY < MAZE_SIZE && maze[newX][newY] == 0) {
                    stack.push(new Point(newX, newY));
                    maze[newX][newY] = -1;
                    foundNext = true;
                    break;
                }
            }
            if (!foundNext) {
                stack.pop();
            }
        }
        return false;
    }

    public static void main(String[] args) {
        boolean result = solveMaze();
        System.out.println("是否找到路径: " + result);
    }
}

最佳实践

  1. 避免使用 Stack 类进行线程安全操作：由于 Stack 类继承自 Vector，它的方法是同步的，这在多线程环境下会带来性能开销。如果需要线程安全的栈，可以考虑使用 ConcurrentLinkedDeque 类。
  2. 使用泛型确保类型安全：在创建 Stack 对象时，始终使用泛型来指定栈中元素的类型，以避免运行时的类型转换错误。
  3. 合理控制栈的大小：在某些情况下，栈可能会不断增长，导致内存耗尽。可以在适当的时候检查栈的大小，并进行必要的清理操作。

小结

本文详细介绍了 Java 中 Stack 类的基础概念、使用方法、常见实践以及最佳实践。Stack 类在很多算法和数据处理场景中都非常有用，但在使用时需要注意其线程安全和性能问题。通过合理运用 Stack 类的方法，可以高效地解决各种实际问题。

参考资料

  1. Java 官方文档 - Stack 类
  2. 《Effective Java》 - Joshua Bloch
  3. 《算法导论》 - Thomas H. Cormen 等