Java数组实现栈的详细教程

各位小伙伴们，大家好呀！看看今天我又给各位带来了什么文章？本文标题是《Java数组实现顺序栈详解》，很明显是关于文章的文章哈哈哈，其中内容主要会涉及到等等，如果能帮到你，觉得很不错的话，欢迎各位多多点评和分享！

数组实现顺序栈的核心原因是其访问效率高、内存连续、实现简单，适合数据规模可预估且对性能要求高的场景；1. 数组通过索引直接访问栈顶元素，时间复杂度为O(1)，具备良好的缓存局部性；2. 其固定容量的局限性可通过动态扩容、预分配、错误处理或改用链表等策略应对；3. 实际应用包括函数调用模拟、括号匹配、表达式求值、浏览器前进后退、文本编辑器撤销重做及深度优先搜索等，均依赖栈的后进先出特性；4. 动态扩容虽常用但非唯一方案，需根据性能、内存和业务需求权衡选择最适合的实现方式。

通过Java代码使用数组实现顺序栈，核心思路是利用一个固定大小的数组来存储栈元素，并用一个整数变量来追踪栈顶的位置。当元素入栈时，栈顶指针上移；出栈时，栈顶指针下移。这种实现方式简洁直观，但在容量管理上需要额外考虑。

解决方案

import java.util.EmptyStackException; // Java标准库中的空栈异常，用于增强代码可读性

/**
 * 一个基于数组实现的顺序栈。
 * 泛型设计，使其可以存储任何类型的对象。
 */
public class SeqStack<E> {
    private Object[] data; // 存储栈元素的数组
    private int top;       // 栈顶指针，指向栈顶元素的位置（如果栈为空，通常为-1）
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量

    /**
     * 构造一个具有默认容量的顺序栈。
     */
    public SeqStack() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 构造一个具有指定容量的顺序栈。
     * @param capacity 栈的初始容量
     * @throws IllegalArgumentException 如果容量小于等于0
     */
    public SeqStack(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("栈的容量必须大于0");
        }
        this.data = new Object[capacity];
        this.top = -1; // 初始时栈为空，top指向-1
    }

    /**
     * 将元素压入栈顶。
     * @param element 要压入的元素
     * @throws IllegalStateException 如果栈已满
     */
    public void push(E element) {
        if (isFull()) {
            // 实际应用中，这里可能会选择扩容而不是直接抛异常
            throw new IllegalStateException("栈已满，无法压入新元素。");
        }
        data[++top] = element; // 栈顶指针先加1，再存入元素
    }

    /**
     * 弹出栈顶元素并返回。
     * @return 弹出的栈顶元素
     * @throws EmptyStackException 如果栈为空
     */
    @SuppressWarnings("unchecked") // 忽略类型转换警告
    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException(); // 栈为空，无法弹出
        }
        E element = (E) data[top]; // 获取栈顶元素
        data[top--] = null;       // 将原栈顶位置置为null，帮助GC，然后栈顶指针减1
        return element;
    }

    /**
     * 查看栈顶元素，但不将其弹出。
     * @return 栈顶元素
     * @throws EmptyStackException 如果栈为空
     */
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (E) data[top]; // 直接返回栈顶元素
    }

    /**
     * 检查栈是否为空。
     * @return 如果栈为空则返回true，否则返回false
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 检查栈是否已满。
     * @return 如果栈已满则返回true，否则返回false
     */
    public boolean isFull() {
        return top == data.length - 1;
    }

    /**
     * 返回栈中元素的数量。
     * @return 栈中元素的数量
     */
    public int size() {
        return top + 1;
    }

    /**
     * 返回栈的容量。
     * @return 栈的容量
     */
    public int capacity() {
        return data.length;
    }

    // 简单测试
    public static void main(String[] args) {
        SeqStack<String> stringStack = new SeqStack<>(3);
        System.out.println("栈是否为空？ " + stringStack.isEmpty()); // true

        stringStack.push("A");
        stringStack.push("B");
        stringStack.push("C");
        System.out.println("当前栈大小: " + stringStack.size()); // 3
        System.out.println("栈顶元素: " + stringStack.peek()); // C
        System.out.println("栈是否已满？ " + stringStack.isFull()); // true

        try {
            stringStack.push("D"); // 尝试压入第四个元素，会抛异常
        } catch (IllegalStateException e) {
            System.out.println("尝试压入D时捕获到异常: " + e.getMessage());
        }

        System.out.println("弹出: " + stringStack.pop()); // C
        System.out.println("弹出: " + stringStack.pop()); // B
        System.out.println("当前栈大小: " + stringStack.size()); // 1

        System.out.println("弹出: " + stringStack.pop()); // A
        System.out.println("栈是否为空？ " + stringStack.isEmpty()); // true

        try {
            stringStack.pop(); // 尝试从空栈弹出，会抛异常
        } catch (EmptyStackException e) {
            System.out.println("尝试从空栈弹出时捕获到异常: 栈为空");
        }
    }
}

为什么选择数组实现顺序栈？它有哪些实际考量？

在我看来，选择数组来实现顺序栈，最直接的原因就是它的简单性和内存效率。数组在内存中是连续存储的，这意味着访问栈中的任何元素（尤其是栈顶元素）都非常快，是O(1)的时间复杂度。这种直接的索引访问，加上良好的CPU缓存局部性，使得顺序栈在处理大量数据且对性能有较高要求的场景下表现出色。比如，如果你需要一个临时的、快速存取且大小相对固定的数据集合，数组实现的栈无疑是一个非常好的选择。

然而，凡事都有两面性。数组实现的最大局限性在于其固定容量。一旦初始化，它的存储空间就确定了。这意味着如果你预估的容量过小，栈很快就会“满”，导致无法再压入新元素，这在编程中通常表现为 StackOverflowError（当然，我们这里是自定义抛出 IllegalStateException）。反之，如果容量设置得过大，又会造成内存的浪费。所以，在决定使用数组实现顺序栈时，一个关键的实际考量就是你对数据规模的预估能力。如果你能比较准确地知道栈的最大可能大小，或者它是一个短期、局部使用的辅助结构，那么数组实现会非常高效。但如果数据量波动大、难以预测，或者需要长时间运行且可能无限增长，那么固定大小的数组就显得力不从心了。

顺序栈在实际项目中能解决哪些问题？

顺序栈虽然看似基础，但在许多实际编程场景中都扮演着重要的角色。我个人觉得它最典型的应用，就是对函数调用堆栈的模拟。虽然JVM本身有其复杂的调用栈机制，但在某些特定场景下，比如实现自己的解释器、编译器中的语法分析，或者需要手动管理函数调用的上下文时，顺序栈就能派上用场。

除了这个，它在解决一些算法问题时也特别顺手：

1. 括号匹配与表达式求值：这是栈的经典应用。无论是检查代码中的括号是否正确闭合 ([])，还是将中缀表达式转换为后缀表达式，再进行求值，栈都提供了非常优雅的解决方案。每次遇到左括号就入栈，遇到右括号就检查栈顶是否为对应的左括号，如果不是或栈为空，则说明不匹配。
2. 浏览器前进/后退功能：这其实是两个栈的组合应用。一个栈存储“后退”的历史页面，另一个栈存储“前进”的历史页面。当你点击“后退”时，当前页面从“前进”栈弹出，压入“后退”栈；点击“前进”时，操作反之。
3. 文本编辑器的撤销(Undo)/重做(Redo)功能：每次用户执行一个可撤销的操作（如输入文字、删除行），就把该操作及其相关数据压入一个“撤销栈”。当用户点击“撤销”时，从撤销栈弹出一个操作并执行其逆操作，同时将该操作压入“重做栈”。
4. 深度优先搜索 (DFS)：在图或树的遍历中，非递归的DFS算法通常会使用一个栈来保存待访问的节点。每次从栈顶取出一个节点访问，然后将其未访问的邻居节点压入栈中。

这些例子都体现了栈“后进先出”的特性，它能很好地帮助我们管理操作的顺序或状态的上下文。

如何处理顺序栈的容量限制？动态扩容是唯一选择吗？

处理顺序栈的容量限制，这确实是数组实现栈时一个绕不开的话题。最常见的，也是Java标准库中 ArrayList 和 Vector（java.util.Stack 内部用的就是 Vector）所采用的策略，就是动态扩容。当 push 操作发现栈已满时，它会创建一个更大的新数组（通常是原容量的1.5倍或2倍），然后将旧数组中的所有元素复制到新数组中，最后将 data 引用指向新数组。这样做的好处是，从摊还分析的角度来看，每次 push 操作的平均时间复杂度仍然是O(1)，虽然偶尔会遇到O(n)的复制操作，但长期来看效率很高。

然而，动态扩容并非总是唯一或最佳选择。在某些特定场景下，我们可能需要考虑其他策略：

1. 预估与固定容量：如果你的应用场景中，栈的最大容量是已知或可以合理预估的，那么最简单直接的方式就是在初始化时就分配足够大的容量。例如，如果你确定某个算法最多只需要处理100个层级的递归，那么直接创建一个容量为100的栈就足够了。这样可以避免扩容带来的额外开销和内存碎片化问题。
2. 错误处理与拒绝服务：在一些对资源消耗极其敏感，或者对“满栈”有明确业务边界的系统中，当栈满时，我们可能选择直接抛出异常（就像我们示例代码中那样 IllegalStateException），或者返回一个表示失败的状态码。这是一种“拒绝服务”的策略，它将容量管理的问题抛给调用者，由调用者来决定如何应对。这在某些嵌入式系统或资源受限环境中尤为常见。
3. 基于链表的栈：如果容量问题是一个持续的痛点，并且你对内存连续性或缓存局部性没有那么极致的要求，那么使用链表来实现栈（比如 java.util.LinkedList 可以作为 Deque 来实现栈的功能）是一个非常好的替代方案。链表实现的栈理论上没有容量限制（只受限于系统内存），每次 push 或 pop 都只是创建或销毁一个节点并调整指针，时间复杂度稳定在O(1)，且不会有复制整个数组的开销。缺点是内存开销相对略大，因为每个节点都需要额外的指针存储空间，并且由于内存不连续，缓存命中率可能不如数组。

所以，选择哪种策略，很大程度上取决于你对性能、内存、以及对“栈满”情况的业务容忍度的具体权衡。没有银弹，只有最适合你当前场景的方案。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。