Java 中栈（Stack）的实现

简介

在 Java 编程中，栈（Stack）是一种重要的数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后进入栈的数据会最先被取出。栈在许多算法和应用场景中都有广泛的应用，例如表达式求值、深度优先搜索（DFS）等。本文将详细介绍 Java 中栈的基础概念、使用方法、常见实践以及最佳实践。

目录

1. 基础概念
2. Java 中栈的使用方法
   • 使用 java.util.Stack 类
   • 使用 java.util.Deque 接口和 ArrayDeque 类
3. 常见实践
   • 表达式求值
   • 深度优先搜索
4. 最佳实践
5. 小结
6. 参考资料

基础概念

栈是一种线性数据结构，它有以下几个关键特性： - 后进先出（LIFO）原则：如前面所述，最后进入栈的元素将最先被移除。 - 操作： - 入栈（Push）：将元素添加到栈的顶部。 - 出栈（Pop）：从栈顶移除并返回元素。 - 查看栈顶元素（Peek）：返回栈顶元素，但不移除它。 - 判断栈是否为空（Is Empty）：检查栈中是否没有元素。

Java 中栈的使用方法

使用 java.util.Stack 类

java.util.Stack 是 Java 中专门用于表示栈的数据结构类。它继承自 Vector 类，具有 Vector 类的所有属性和方法，同时也提供了一些栈特有的方法。

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

        // 出栈操作
        System.out.println("出栈元素: " + stack.pop());
        System.out.println("栈顶元素: " + stack.peek());

        // 判断栈是否为空
        System.out.println("栈是否为空: " + stack.isEmpty());
    }
}

使用 java.util.Deque 接口和 ArrayDeque 类

虽然 java.util.Stack 类可以满足基本的栈操作需求，但在现代 Java 编程中，推荐使用 java.util.Deque（双端队列）接口及其实现类 ArrayDeque 来实现栈。Deque 接口提供了更丰富的操作方法，并且性能更好。

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

public class DequeStackExample {
    public static void main(String[] args) {
        // 创建一个栈
        Deque<Integer> stack = new ArrayDeque<>();

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

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

        // 出栈操作
        System.out.println("出栈元素: " + stack.pop());
        System.out.println("栈顶元素: " + stack.peek());

        // 判断栈是否为空
        System.out.println("栈是否为空: " + stack.isEmpty());
    }
}

常见实践

表达式求值

栈在表达式求值中非常有用。例如，对于后缀表达式（逆波兰表达式），可以使用栈来计算表达式的值。

import java.util.Stack;

public class PostfixEvaluation {
    public static int evaluatePostfix(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*1+";
        System.out.println("后缀表达式的值: " + evaluatePostfix(postfix));
    }
}

深度优先搜索

在图的深度优先搜索（DFS）算法中，栈可以用来辅助遍历图的节点。

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (!visited[current]) {
                System.out.print(current + " ");
                visited[current] = true;
                List<Integer> neighbors = adjList.get(current);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int neighbor = neighbors.get(i);
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
}

public class DFSExample {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        System.out.println("深度优先搜索结果: ");
        graph.dfs(0);
    }
}

最佳实践

• 性能考虑：如前所述，推荐使用 ArrayDeque 实现栈，因为它在性能上优于 java.util.Stack。ArrayDeque 是基于数组实现的，并且没有 Stack 类的线程安全开销（如果不需要线程安全的话）。
• 边界检查：在进行入栈和出栈操作时，要注意检查栈的状态。例如，在出栈前确保栈不为空，避免抛出 EmptyStackException 异常。
• 代码可读性：在使用栈时，要确保代码的意图清晰。可以通过合理命名变量和方法，以及添加注释来提高代码的可读性。

小结

本文详细介绍了 Java 中栈的实现，包括基础概念、使用方法、常见实践以及最佳实践。通过 java.util.Stack 类和 java.util.Deque 接口及其实现类 ArrayDeque，我们可以方便地在 Java 程序中使用栈这种数据结构。栈在表达式求值、深度优先搜索等许多场景中都有重要应用。遵循最佳实践可以帮助我们写出高效、健壮且易读的代码。

参考资料

• Java 官方文档 - java.util.Stack
• Java 官方文档 - java.util.Deque
• Java 官方文档 - java.util.ArrayDeque