跳转至

Java中栈（Stack）的创建与使用

简介

在Java编程中，栈（Stack）是一种重要的数据结构，它遵循后进先出（LIFO，Last In First Out）的原则。这意味着最后进入栈的数据会最先被取出。栈在许多算法和实际应用场景中都扮演着关键角色，例如表达式求值、深度优先搜索（DFS）算法等。本文将详细介绍在Java中创建和使用栈的相关知识。

目录

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

基础概念

栈是一种线性数据结构，它有两个主要操作：入栈（push）和出栈（pop）。入栈操作将元素添加到栈的顶部，而出栈操作则从栈顶移除并返回元素。此外，还有一些辅助操作，如查看栈顶元素（peek）、判断栈是否为空（isEmpty）以及获取栈的大小（size）。

使用方法

使用java.util.Stack类

java.util.Stack类是Java标准库中专门用于实现栈的数据结构。它继承自Vector类，因此具有Vector类的一些特性，如线程安全。

以下是使用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());

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

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

        // 获取栈的大小
        System.out.println("栈的大小: " + stack.size());
    }
}

使用java.util.Deque接口实现栈

java.util.Deque（双端队列，Double - ended Queue）接口也可以用来实现栈。Deque接口提供了更丰富的操作方法，并且在性能上可能比Stack类更好，因为Stack类是一个较老的类。

以下是使用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.isEmpty());

        // 获取栈的大小
        System.out.println("栈的大小: " + stack.size());
    }
}

常见实践

表达式求值

栈在表达式求值中非常有用，特别是对于后缀表达式（逆波兰表达式）。后缀表达式的优点是不需要括号来确定运算顺序。

以下是一个简单的后缀表达式求值示例：

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）算法可以使用栈来实现。通过将节点依次入栈和出栈，我们可以遍历图或树的所有节点。

以下是一个简单的使用栈实现DFS的示例（以二叉树为例）：

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class DFSWithStack {
    public static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println("DFS遍历结果:");
        dfs(root);
    }
}

最佳实践

  1. 性能考虑：如果性能是关键因素，优先选择Deque接口及其实现类（如ArrayDeque）来实现栈，而不是使用Stack类。因为Stack类是线程安全的，这在单线程环境下会带来一些性能开销。
  2. 类型安全：使用泛型来确保栈中元素的类型安全。在Java 7及以上版本，可以使用菱形语法（<>）来简化泛型声明。
  3. 异常处理：在进行出栈和查看栈顶元素操作时，要注意处理可能的异常。例如，pop和peek方法在栈为空时会抛出EmptyStackException异常，应该进行适当的异常处理。

小结

在Java中，我们可以通过java.util.Stack类或java.util.Deque接口来创建和使用栈。Stack类是Java标准库中专门的栈实现，而Deque接口提供了更灵活和高效的方式来实现栈。栈在许多实际应用场景中都有广泛的应用，如表达式求值和深度优先搜索。在使用栈时，要注意性能、类型安全和异常处理等方面的最佳实践，以确保程序的高效和稳定运行。

参考资料

  1. Oracle Java Documentation - Stack
  2. Oracle Java Documentation - Deque
  3. 《Effective Java》 - Joshua Bloch