Java 实例 – 栈的实现（千字长文）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

在编程世界中，数据结构是解决问题的基础工具。栈（Stack）作为一种经典的数据结构，因其“后进先出”（LIFO, Last In First Out）的特性，在算法设计和实际开发中扮演着重要角色。无论是括号匹配、表达式求值，还是函数调用的实现，栈都能提供简洁高效的解决方案。本文将以 “Java 实例 – 栈的实现” 为主题，从概念解析、手动实现、代码示例到实际应用，逐步引导读者掌握栈的原理与实践方法。

栈的基本概念与特性

栈的定义与比喻

栈是一种线性数据结构，其核心特性是 “后进先出”。想象一个叠放的盘子：新盘子总是放在最顶端，取盘子时也只能从顶端开始拿。栈的这种特性决定了它天然适合处理需要“回退”或“临时存储”的场景。

栈的常见操作

栈的典型操作包括：

• Push（入栈）：将元素添加到栈顶。
• Pop（出栈）：移除并返回栈顶元素。
• Peek（查看栈顶元素）：返回栈顶元素但不移除。
• IsEmpty（判断栈是否为空）：返回布尔值。
• Size（获取栈的大小）：返回当前元素数量。

栈的抽象数据类型（ADT）

栈的抽象模型可以简化为以下结构：
| 操作 | 描述 | 时间复杂度 |
|------------|--------------------------------|------------|
| push() | 将元素添加到栈顶 | O(1) |
| pop() | 移除并返回栈顶元素 | O(1) |
| peek() | 查看栈顶元素而不移除 | O(1) |
| isEmpty()| 检查栈是否为空 | O(1) |
| size() | 获取栈中元素的数量 | O(1) |

手动实现栈：从零开始

选择数据结构：数组 vs. 链表

栈可以通过数组或链表实现。数组的优势在于随机访问元素快，但容量固定；链表的容量动态扩展，但需要额外的指针空间。本实例以 数组 为基础，演示手动实现栈的步骤。

步骤 1：定义栈的类结构

创建一个 MyStack 类，包含以下成员变量：

public class MyStack<T> {
    private T[] elements;
    private int top; // 栈顶指针，初始为 -1
    private static final int DEFAULT_CAPACITY = 10;

    public MyStack() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        top = -1;
    }
    // 其他方法待补充
}

关键点解释：

• elements 数组用于存储元素，类型通过泛型 <T> 实现。
• top 初始化为 -1，表示栈为空时无有效元素。
• 默认容量设为 10，避免初始化时空指针异常。

步骤 2：实现 push() 方法

public void push(T element) {
    // 检查栈是否已满（假设容量固定）
    if (top >= elements.length - 1) {
        throw new StackOverflowError("栈已满，无法入栈");
    }
    elements[++top] = element; // 先递增 top，再赋值
}

比喻：将新元素“压”到栈顶，如同将盘子叠在最上层。

步骤 3：实现 pop() 方法

public T pop() {
    if (isEmpty()) {
        throw new NoSuchElementException("栈为空，无法出栈");
    }
    T element = elements[top];
    elements[top--] = null; // 移除引用，帮助垃圾回收
    return element;
}

注意：top 先取值，再递减，确保返回的是当前栈顶元素。

步骤 4：实现辅助方法

public T peek() {
    if (isEmpty()) {
        throw new NoSuchElementException();
    }
    return elements[top];
}

public boolean isEmpty() {
    return top == -1;
}

public int size() {
    return top + 1; // 因为 top 从 0 开始计数
}

扩展：动态扩容（可选）

若希望栈容量动态扩展，可在 push() 方法中添加扩容逻辑：

private void ensureCapacity() {
    if (top < elements.length - 1) return;
    int newCapacity = elements.length * 2;
    T[] newElements = (T[]) new Object[newCapacity];
    System.arraycopy(elements, 0, newElements, 0, elements.length);
    elements = newElements;
}

调用方式：在 push() 方法中先调用 ensureCapacity()，再执行入栈操作。

使用 Java 内置的 Stack 类

Java 提供了 java.util.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()); // 输出 30
        System.out.println("弹出元素：" + stack.pop()); // 输出 30
        System.out.println("栈是否为空：" + stack.isEmpty()); // 输出 false
    }
}

对比分析：
| 特性 | 手动实现的 MyStack | Java 内置 Stack 类 |
|--------------------|-----------------------------|-----------------------------|
| 动态扩容 | 需手动实现 | 默认支持 |
| 泛型支持 | 通过 <T> 实现 | 内置泛型 |
| 线程安全性 | 非线程安全（可自行扩展） | 非线程安全 |

栈的典型应用场景

案例 1：括号匹配

检查字符串中的括号是否合法（如 ()[]{}）。

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

原理：每次遇到左括号入栈，右括号时弹出栈顶元素匹配。最终栈为空表示匹配成功。

案例 2：后缀表达式求值

将中缀表达式（如 3 + 5 * 2）转换为后缀表达式（如 3 5 2 * +），再通过栈计算结果。

// 示例代码片段（简化版）
public int evaluatePostfix(String expression) {
    Stack<Integer> stack = new Stack<>();
    for (char c : expression.toCharArray()) {
        if (Character.isDigit(c)) {
            stack.push(c - '0');
        } else {
            int b = stack.pop();
            int a = stack.pop();
            switch(c) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                // 其他运算符类似
            }
        }
    }
    return stack.pop();
}

常见问题与调试技巧

问题 1：栈溢出（Stack Overflow）

当栈的容量固定且元素超过上限时，push() 方法会抛出 StackOverflowError。
解决方法：

• 使用动态扩容策略（如数组扩容）。
• 在入栈前检查栈是否已满。

问题 2：空栈操作（Empty Stack）

调用 pop() 或 peek() 时若栈为空，会抛出 NoSuchElementException。
解决方法：

• 在操作前调用 isEmpty() 判断。
• 使用 try-catch 捕获异常（非推荐，可能掩盖逻辑错误）。

调试技巧

• 在代码中添加日志，打印 top 值和元素数组，观察操作前后变化。
• 单元测试：编写测试用例覆盖所有操作路径（如连续入栈、出栈、空栈操作）。

结论

通过本文的讲解，读者应已掌握栈的核心概念、手动实现方法及实际应用场景。无论是使用内置的 Stack 类，还是基于数组或链表的自定义实现，关键在于理解“后进先出”这一特性，并能在具体问题中灵活运用。

栈不仅是数据结构学习的基础，更是算法优化的利器。例如，递归函数的本质是隐式地使用栈来保存调用状态，而通过栈实现的迭代算法（如二叉树的前序遍历）也能避免递归导致的栈溢出风险。

建议读者通过以下方式巩固知识：

1. 用链表重新实现栈，并对比与数组实现的差异。
2. 尝试用栈解决其他问题，如“最近最少使用（LRU）缓存”或“退格字符串比较”。
3. 阅读 JDK 源码中 Stack 类的实现细节，理解其线程安全的改进方法（如 Vector 的使用）。

掌握栈的实现与应用，将为后续学习队列、树、图等数据结构打下坚实基础，也将在实际开发中提升问题解决效率。