Java 实例 – 栈的实现（一文讲透）

Java 实例 – 栈的实现：从零开始理解数据结构

在编程世界里，数据结构是构建高效程序的基石。而栈，作为最基础又最实用的数据结构之一，几乎贯穿了所有高级应用的底层逻辑。无论是浏览器的前进后退功能，还是表达式求值、括号匹配，背后都有栈的身影。今天，我们就来手把手实现一个完整的 Java 栈，通过实际代码，彻底搞懂它的原理与用法。

这不仅仅是一次代码练习，更是一次对“后进先出”这一核心思想的深度体验。相信我，当你真正写完这个栈，你会对程序运行时的调用机制有全新的理解。

什么是栈？生活中的类比

想象你站在一个餐厅的洗碗区，员工把用过的碗碟堆在水槽里。新洗好的碗会放在最上面，而取碗时只能从最上面拿。这就是典型的“后进先出”（LIFO, Last In First Out）原则。

在计算机中，栈就是这样一个“容器”：数据只能从一端（称为栈顶）进入和离开。这种结构在函数调用、内存管理、表达式解析中扮演着关键角色。

提示：Java 中的 Stack 类虽然存在，但它是遗留类，不推荐在新项目中使用。我们今天要做的，是实现一个更现代、更灵活的栈，理解其底层逻辑。

设计栈的接口与核心方法

在实现之前，先明确我们栈需要支持哪些操作。一个标准栈至少包含以下方法：

• push(E item)：将元素压入栈顶
• pop()：移除并返回栈顶元素
• peek()：查看栈顶元素但不移除
• isEmpty()：判断栈是否为空
• size()：返回栈中元素数量

这些方法共同构成了栈的“行为契约”。我们用接口来定义它们，让实现类更清晰。

public interface Stack<E> {
    // 将元素压入栈顶
    void push(E item);
    
    // 移除并返回栈顶元素
    E pop();
    
    // 查看栈顶元素但不移除
    E peek();
    
    // 判断栈是否为空
    boolean isEmpty();
    
    // 返回栈中元素数量
    int size();
}

说明：这里的 E 是泛型类型，表示栈可以存储任意类型的对象，比如 Integer、String，甚至自定义类。这是 Java 泛型的典型用法。

创建数组与初始化

栈的底层实现方式有两种：基于数组和基于链表。今天，我们选择基于数组的方式，因为它简单、高效，适合初学者理解。

我们先创建一个私有数组来存储元素，再用一个 top 变量记录栈顶位置。

public class ArrayStack<E> implements Stack<E> {
    // 存储栈中元素的数组
    private E[] elements;
    
    // 栈顶索引，-1 表示栈为空
    private int top;
    
    // 初始容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 构造函数：初始化数组和栈顶
    public ArrayStack() {
        // 注意：Java 不允许直接创建泛型数组，所以使用 Object 数组再强制转换
        elements = (E[]) new Object[DEFAULT_CAPACITY];
        top = -1; // 栈为空时，栈顶为 -1
    }
}

重要提示：E[] elements = (E[]) new Object[DEFAULT_CAPACITY]; 这行代码虽然编译通过，但会触发泛型擦除警告。在实际项目中，建议使用 ArrayList 代替。但为了教学目的，我们保留这种实现方式。

实现核心方法：push、pop 和 peek

接下来，我们实现栈的核心操作。每一步都配有详细注释，帮助你理解逻辑。

push 方法：压入元素

@Override
public void push(E item) {
    // 检查栈是否已满，如果满了需要扩容
    if (top + 1 >= elements.length) {
        // 扩容为原来的两倍
        resize(elements.length * 2);
    }
    
    // 将元素放入栈顶位置
    elements[++top] = item;
}

解析：++top 是先自增再赋值，确保新元素放在 top 指向的位置。如果数组满了，我们调用 resize 扩容。

pop 方法：弹出栈顶元素

@Override
public E pop() {
    // 如果栈为空，抛出异常
    if (isEmpty()) {
        throw new IllegalStateException("栈为空，无法弹出元素");
    }
    
    // 取出栈顶元素
    E item = elements[top];
    
    // 清空引用，帮助垃圾回收
    elements[top] = null;
    
    // 栈顶指针下移
    top--;
    
    // 返回弹出的元素
    return item;
}

提示：elements[top] = null; 这一步很重要。它释放了对旧对象的引用，避免内存泄漏。

peek 方法：查看栈顶但不移除

@Override
public E peek() {
    // 如果栈为空，抛出异常
    if (isEmpty()) {
        throw new IllegalStateException("栈为空，无法查看栈顶元素");
    }
    
    // 直接返回栈顶元素
    return elements[top];
}

说明：peek 与 pop 的区别在于，它不改变栈的状态，仅读取数据。

动态扩容机制：避免数组越界

当栈不断压入元素，数组可能会装不下。这时我们需要“扩容”。

private void resize(int newCapacity) {
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    
    // 将原数组元素复制到新数组
    for (int i = 0; i <= top; i++) {
        newElements[i] = elements[i];
    }
    
    // 更新引用
    elements = newElements;
}

比喻：就像你家的书架快满了，于是买了一个更大的书架，把旧书一本本搬到新架子上。栈的扩容也是这个道理。

完整的辅助方法实现

为了让栈更实用，我们补充几个常用方法：

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

@Override
public int size() {
    return top + 1;
}

size() 的返回值是 top + 1，因为 top 是索引，从 0 开始计数。

实际案例：括号匹配检测

现在我们来用这个栈解决一个经典问题：判断一个字符串中的括号是否匹配。

比如：{[()]} 是合法的，而 {[(])} 是非法的。

public static boolean isBalanced(String s) {
    ArrayStack<Character> stack = new ArrayStack<>();
    
    for (char c : s.toCharArray()) {
        // 遇到左括号，压入栈
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        }
        // 遇到右括号，检查是否匹配
        else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) {
                return false; // 没有对应的左括号
            }
            
            char top = stack.pop();
            // 判断是否匹配
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
        // 忽略其他字符
    }
    
    // 最后栈必须为空，表示所有括号都匹配
    return stack.isEmpty();
}

使用示例：

System.out.println(isBalanced("{[()]}")); // true
System.out.println(isBalanced("{[(])}")); // false

这个例子完美展示了栈在实际问题中的价值：利用“后进先出”的特性，自动处理嵌套结构。

性能分析与使用建议

优势：实现简单，访问速度快。
缺点：初始容量固定，扩容有性能开销。

建议：在对性能要求极高的场景，可使用 ArrayList 作为底层，避免手动扩容。

总结：从零到一，掌握栈的本质

通过今天这个 Java 实例 – 栈的实现，我们不仅写出了一个可用的栈，更重要的是，理解了“后进先出”背后的逻辑。从数组设计、动态扩容，到实际应用，每一步都让你对数据结构有更深层的认识。

栈虽小，却蕴含大智慧。它不仅是编程的工具，更是思维方式的训练。当你在面试中被问到“如何实现一个栈”，不再只会说“用 Stack 类”，而是能自信地说出“我用数组 + 动态扩容实现了一个高效栈”，那才是真正的成长。

记住：每一个复杂的系统，都是由一个个简单结构组合而成。今天你亲手实现的这个栈，就是你通往更高阶编程之路的第一块砖。继续写下去，你会越来越强。