跳转至

Java 中栈（Stack）的添加操作

简介

在 Java 编程中，栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。理解如何在栈中添加元素（add in a stack）是使用栈这种数据结构的基础操作之一。掌握这一操作对于解决许多实际问题，如表达式求值、深度优先搜索算法等，都具有重要意义。本文将深入探讨在 Java 中如何在栈中添加元素，包括基础概念、使用方法、常见实践以及最佳实践。

目录

  1. 基础概念
  2. 使用方法
    • 使用 java.util.Stack 类
    • 使用 java.util.Deque 接口结合 ArrayDeque 实现
  3. 常见实践
    • 简单示例：逆序打印数字
    • 实际应用：括号匹配
  4. 最佳实践
    • 选择合适的栈实现
    • 性能优化
  5. 小结
  6. 参考资料

基础概念

栈是一种特殊的数据结构，它遵循后进先出的原则。想象一个堆叠的盘子，最后放上去的盘子会最先被拿走。在栈中，添加元素的操作通常被称为“压栈（push）”，移除元素的操作被称为“出栈（pop）”。Java 提供了多种方式来实现栈，其中最常用的是 java.util.Stack 类和 java.util.Deque 接口（特别是使用 ArrayDeque 实现）。

使用方法

使用 java.util.Stack 类

java.util.Stack 类是 Java 中专门用于表示栈数据结构的类。它继承自 Vector 类，并且提供了一系列操作栈的方法。要在 Stack 中添加元素，可以使用 push 方法。

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("栈中的元素: " + stack);
    }
}

在上述代码中： 1. 首先创建了一个 Stack 对象，指定存储的元素类型为 Integer。 2. 然后使用 push 方法将整数 1、2 和 3 依次压入栈中。 3. 最后打印栈中的元素，可以看到输出结果为 [1, 2, 3]，其中 3 是栈顶元素。

使用 java.util.Deque 接口结合 ArrayDeque 实现

java.util.Deque（双端队列，Double - ended Queue）接口提供了更灵活的操作方式，它既可以当作栈使用，也可以当作队列使用。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(1);
        stack.push(2);
        stack.push(3);

        System.out.println("栈中的元素: " + stack);
    }
}

在这段代码中： 1. 创建了一个 ArrayDeque 对象，并将其赋值给 Deque 类型的变量 stack。 2. 使用 push 方法向栈中添加元素，与 Stack 类的操作类似。 3. 打印栈中的元素，输出结果同样为 [1, 2, 3]。

常见实践

简单示例：逆序打印数字

假设有一组数字，需要逆序打印它们。可以利用栈的后进先出特性来实现。

import java.util.Stack;

public class ReversePrintExample {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        Stack<Integer> stack = new Stack<>();

        for (int number : numbers) {
            stack.push(number);
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}

在上述代码中： 1. 首先定义了一个整数数组 numbers。 2. 创建一个 Stack 对象 stack，并使用 for - each 循环将数组中的每个数字压入栈中。 3. 然后通过一个 while 循环，在栈不为空的情况下，不断弹出栈顶元素并打印，从而实现逆序打印数组中的数字。

实际应用：括号匹配

在编译器中，经常需要检查表达式中的括号是否匹配。可以使用栈来解决这个问题。

import java.util.Stack;

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

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

在这个示例中： 1. 定义了一个 isValid 方法，用于检查给定字符串中的括号是否匹配。 2. 创建一个 Stack 对象 stack，遍历字符串中的每个字符。 3. 如果字符是左括号（(, [, {），则将其压入栈中。 4. 如果字符是右括号（), ], }），则从栈中弹出一个字符进行匹配。如果栈为空或者匹配失败，则返回 false。 5. 遍历结束后，如果栈为空，说明所有括号都匹配，返回 true；否则返回 false。

最佳实践

选择合适的栈实现

  • java.util.Stack: 虽然 Stack 类是专门为栈设计的，但它继承自 Vector 类，而 Vector 是线程安全的，这会带来一定的性能开销。如果不需要线程安全，不推荐使用 Stack 类。
  • java.util.ArrayDeque: 对于大多数情况，ArrayDeque 是实现栈的更好选择。它具有高效的实现，并且不是线程安全的，因此在单线程环境下性能更好。

性能优化

  • 避免不必要的扩容: 如果知道栈中元素的大致数量，可以在创建 ArrayDeque 时指定初始容量，以避免在添加元素过程中频繁扩容带来的性能损耗。例如：Deque<Integer> stack = new ArrayDeque<>(100);
  • 减少装箱拆箱操作: 如果栈中存储的是基本数据类型，尽量使用对应的包装类数组版本的 ArrayDeque，以减少装箱拆箱的开销。例如，使用 ArrayDeque<Integer> 而不是 ArrayDeque<int[]>。

小结

在 Java 中，在栈中添加元素是一个基本且重要的操作。通过 java.util.Stack 类和 java.util.Deque 接口结合 ArrayDeque 实现，我们可以灵活地创建和操作栈。了解常见实践，如逆序打印和括号匹配，能帮助我们更好地应用栈解决实际问题。同时，遵循最佳实践，选择合适的栈实现和进行性能优化，可以提高程序的效率和可靠性。

参考资料