Java栈结构深度解析：从LIFO原理到数组与链表实现

一、栈的本质：一种被严格约束的线性结构

在程序开发中，栈是一种看似简单、实则影响深远的数据结构。它属于线性结构的一种，但与数组、链表等自由访问元素的线性结构不同，栈对元素的插入与删除位置做了极其严格的限制：所有操作只能发生在同一端。这一端通常被称为“栈顶”，另一端则称为“栈底”。

栈的核心规则可以概括为：后进入的元素必须先离开。也就是通常所说的 LIFO，即 Last In, First Out。这个规则并不是人为增加复杂度，而是为了在大量场景中获得更清晰的执行顺序与更简单的状态管理。

可以用现实中的“一摞餐盘”来类比栈的行为。当盘子依次叠放时，最先放下的盘子位于最底部，最后放下的盘子位于最顶部。取用盘子时，人们通常只会从顶部拿取，而不会从中间抽取。这样，最后放上去的盘子反而最先被使用，正好对应栈的后进先出特性。

从抽象数据类型角度看，栈通常提供以下基本操作：

• push：将元素压入栈顶；
• pop：移除并返回栈顶元素；
• peek 或 top：查看栈顶元素但不移除；
• isEmpty：判断栈是否为空；
• size：获取栈中元素数量。

这些接口共同构成了栈的最小可用集合。几乎没有哪个数据结构能够以如此少的操作承载如此多的算法与系统设计场景。

---

二、从浏览器后退到递归调用：栈无处不在

理解栈不能只停留在抽象定义，更要看到它在真实系统与算法中的广泛存在。

1. 浏览器后退与编辑器撤销

当用户浏览多个页面时，浏览器会将历史访问记录依次压入栈中。每打开一个新页面，就相当于执行一次 push，记录当前页面地址。当用户点击“后退”时，浏览器弹出最近访问的页面，即 pop 操作。由于栈只允许从顶部弹出元素，因此用户只能沿着访问顺序的逆序逐步返回，不会跳回到任意历史页面。

编辑器的撤销功能也遵循同样逻辑。每一次编辑操作被记录并压栈，执行撤销时，系统弹出最后一次操作并恢复之前状态。连续撤销就是不断出栈的过程。

2. 方法调用栈

在 Java 等语言中，方法调用的执行机制天然依赖于栈。每次调用一个方法时，虚拟机会为该方法创建栈帧，存放局部变量、操作数栈、返回地址等信息，并将该栈帧压入调用栈。方法返回时对应栈帧出栈，程序继续执行调用点之后的代码。

递归方法尤其能体现调用栈的特点。以计算阶乘为例：

public static int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

每一次递归调用都会产生新的栈帧。随着递归深度增加，栈帧数量不断增多。如果递归结束条件设计不当，就可能导致栈空间耗尽，抛出 StackOverflowError。这也是为什么在设计递归算法时，必须关注递归深度与终止条件。

3. 表达式求值与括号匹配

栈在编译原理和表达式计算中同样发挥关键作用。中缀表达式转后缀表达式、后缀表达式求值、括号配对检查等问题，都可以借助栈简洁地解决。

例如判断一个字符串中的括号是否匹配：

public static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if (!isPair(top, c)) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

栈在这里不仅提供了存储能力，更重要的是利用 LIFO 特性实现了“最近出现的左括号必须最先被匹配”这一规则。

---

三、数组实现：追求访问效率与扩容平衡

数组是实现栈最直接的方式之一。由于数组支持根据下标 O(1) 访问，只要维护一个表示栈顶位置的指针，就能高效完成入栈与出栈操作。

1. 基本结构

基于数组的栈可以定义为：

public class ArrayStack<E> {
    private Object[] elements;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    public ArrayStack() {
        elements = new Object[DEFAULT_CAPACITY];
        size = 0;
    }
}

这里使用 Object 数组存储元素，size 既表示元素个数，也表示下一个元素应该写入的位置，因此也可以理解为栈顶指针。

2. 入栈操作

入栈时，先将元素放入 size 指向的位置，然后 size 自增：

public void push(E item) {
    ensureCapacity(size + 1);
    elements[size] = item;
    size++;
}

如果当前数组已满，则需要进行扩容。常见策略是创建一个更大的数组，将原数组元素复制过去：

private void ensureCapacity(int minCapacity) {
    if (minCapacity > elements.length) {
        int newCapacity = elements.length * 2;
        elements = Arrays.copyOf(elements, newCapacity);
    }
}

扩容虽然单次成本为 O(n)，但由于扩容频率随容量增大而不断降低，因此从长期看，push 操作的均摊时间复杂度仍可视为 O(1)。

3. 出栈与查看栈顶

出栈时先检查栈是否为空，然后返回栈顶元素并将 size 减一：

public E pop() {
    if (isEmpty()) {
        throw new EmptyStackException();
    }
    E item = (E) elements[size - 1];
    elements[size - 1] = null;
    size--;
    return item;
}

将原位置置为 null，有助于避免对象长期被引用而无法被垃圾回收，是一种良好的内存管理习惯。

peek 操作不删除元素，只返回栈顶值：

public E peek() {
    if (isEmpty()) {
        throw new EmptyStackException();
    }
    return (E) elements[size - 1];
}

4. 数组实现的优缺点

数组实现的主要优势在于内存连续、访问速度快、缓存友好。对于绝大多数入栈出栈操作，时间复杂度均为 O(1)。但数组扩容需要额外复制成本，并且当栈中元素数量远小于数组容量时，会存在一定的空间浪费。

---

四、链表实现：摆脱固定容量限制

链表实现栈可以避免数组扩容带来的瞬时开销，也不需要预先分配固定容量。节点按需创建，内存使用更加弹性。

1. 节点定义

使用单链表即可实现栈。每个节点保存数据与下一个节点的引用：

class Node<E> {
    E data;
    Node<E> next;
    Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }
}

2. 栈结构

链表栈只需要维护一个指向栈顶节点的引用：

public class LinkedStack<E> {
    private Node<E> top;
    private int size;
    public void push(E item) {
        Node<E> newNode = new Node<>(item, top);
        top = newNode;
        size++;
    }
    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        E item = top.data;
        top = top.next;
        size--;
        return item;
    }
    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }
    public boolean isEmpty() {
        return top == null;
    }
    public int size() {
        return size;
    }
}

入栈时创建新节点，将其 next 指向当前 top，然后更新 top 指向新节点。出栈时只需将 top 后移一位。所有操作都在链表头部完成，时间复杂度均为 O(1)。

3. 链表实现的适用场景

链表实现不存在扩容问题，也不会因为预分配容量过大而浪费大量空间。但每个节点都需要额外存储引用，内存开销比数组更大，且节点分散在堆中，访问局部性较差。在频繁进行大规模入栈出栈且难以预估最大容量的场景下，链表实现更具优势。

---

五、数组栈与链表栈的对比

维度	数组实现	链表实现
入栈时间复杂度	均摊 O(1)	O(1)
出栈时间复杂度	O(1)	O(1)
空间使用	可能浪费预分配空间	每个节点有额外引用开销
扩容成本	需要复制数组	无扩容概念
内存局部性	较好	较差
实现复杂度	稍复杂，需处理扩容	简单

选择哪种实现方式取决于具体场景。如果栈的最大容量大致可预期，数组实现通常更高效；如果容量波动很大且难以预估，链表实现可避免反复扩容与空间浪费。

---

六、栈的典型算法应用

1. 逆波兰表达式求值

后缀表达式天然适合用栈计算。遇到数字则入栈，遇到运算符则弹出两个操作数计算后将结果入栈：

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String token : tokens) {
        if (isOperator(token)) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(apply(a, b, token));
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

2. 单调栈

单调栈是栈的一种高级用法，通过维护栈内元素的单调性，可以在 O(n) 时间内解决“下一个更大元素”“柱状图最大矩形”等问题。

例如，寻找数组中每个元素右边第一个比它大的元素：

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

单调栈的核心思想是：如果新元素比栈顶元素大，那么栈顶元素对后续结果不再有贡献，可以安全移除。这样每个元素最多入栈出栈一次，整体复杂度保持线性。

3. 深度优先搜索

在图的深度优先搜索中，栈可以替代递归实现非递归遍历。每次从栈顶取出节点，将其未访问的邻居节点压入栈中，即可模拟递归的深入过程。

---

七、工程中的注意事项

1. 优先使用标准栈接口

在 Java 中，推荐使用 Deque 接口及其实现类 ArrayDeque 来替代早期的 Stack 类。Stack 类继承自 Vector，带有不必要的同步开销，且设计上不符合现代集合框架的规范。ArrayDeque 同时支持栈和队列操作，性能更优。

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
String top = stack.pop();

2. 注意空栈与边界条件

任何 pop 或 peek 操作前都应先判断栈是否为空。可以通过 isEmpty 检查，或捕获 EmptyStackException。良好的边界处理能避免运行时异常扩散到上层业务逻辑。

3. 防止递归过深

递归函数本质上是隐式使用系统调用栈。当递归深度不可控时，应考虑将递归改写为显式栈迭代，或限制输入规模，防止栈溢出。

例如，二叉树的中序遍历可以用显式栈实现：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result;
}

这种方式将系统调用栈转移到堆上的显式数据结构中，更适合处理深层遍历场景。

---

八、总结

栈是一种操作受限但应用极广的数据结构。它通过严格的 LIFO 规则，为后退导航、撤销恢复、方法调用、表达式求值、单调区间计算和深度优先遍历等众多场景提供了简洁而高效的解决方案。

掌握栈不仅意味着会写 push 和 pop，更意味着能够在复杂问题中识别“后进先出”的隐含顺序关系，并据此设计出清晰、可维护且高效的算法。无论是数组实现还是链表实现，理解其底层代价与适用边界，才能真正在工程实践中做出合理选择。