栈：从 LIFO 到 ArrayDeque

“栈：从 LIFO 到 ArrayDeque”这一块，我曾经有一种很典型的错觉：内容看懂了，自己也会了。我真正关掉答案后才发现：栈的后进先出很好记，我真正理解它是在调试递归调用和括号匹配时，发现很多“回到上一步”的问题都在保存现场。后来我用画图、手算和最小代码反复验证，才把表面的熟悉变成可以复述的理解。

栈只允许从同一端放入和取出元素，因此最后进入的元素最先离开，即 LIFO。它适合表达“最近尚未完成的事情”：函数调用、表达式括号、撤销记录和深度优先搜索都符合这种模式。

它从哪里来

栈的现实原型就是叠放物品，但它在计算机中的关键价值来自“暂存尚未完成的工作”。早期编译器和 ALGOL 运行时使用栈保存函数调用现场，由此递归、表达式求值和回溯都能使用同一套后进先出模型。

用动态数组实现栈

栈、调用栈和单调栈结构图

图：LIFO、调用帧与单调栈的共同访问模式

public final class SimpleStack<E> {
    private Object[] elements = new Object[8];
    private int size;

    public void push(E value) {
        if (size == elements.length) {
            elements = java.util.Arrays.copyOf(elements, elements.length << 1);
        }
        elements[size++] = value;
    }

    @SuppressWarnings("unchecked")
    public E peek() {
        if (size == 0) return null;
        return (E) elements[size - 1];
    }

    @SuppressWarnings("unchecked")
    public E pop() {
        if (size == 0) return null;
        int index = --size;
        E value = (E) elements[index];
        elements[index] = null;
        return value;
    }
}

push 和 pop 都只操作尾部，通常是 O(1)；扩容时单次为 O(n)，连续压栈的摊销成本仍是 O(1)。弹出后清空槽位不是形式主义，它让已离栈对象能被垃圾回收。

为什么优先使用 ArrayDeque

Java 的 Stack 继承自早期的 Vector，方法带有历史同步负担，接口也混入了不属于栈的按索引操作。现代代码通常写成：

java.util.Deque<String> stack = new java.util.ArrayDeque<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop()); // B

ArrayDeque 采用环形数组，既可以作为栈，也可以作为双端队列。它不接受 null，从而能让 poll 返回 null 明确表示“当前为空”。

一个典型应用：括号匹配

static boolean balanced(String text) {
    java.util.Deque<Character> stack = new java.util.ArrayDeque<>();
    for (char ch : text.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack.isEmpty()) return false;
            char left = stack.pop();
            if (ch == ')' && left != '(' ||
                ch == ']' && left != '[' ||
                ch == '}' && left != '{') return false;
        }
    }
    return stack.isEmpty();
}

遇到左括号时把“尚未闭合的上下文”压栈；遇到右括号时，只需与最近的左括号匹配。这正是 LIFO 的价值。

调用栈保存了什么

每次函数调用都会创建栈帧，保存参数、局部变量、返回地址和部分运行状态。递归不是一种独立魔法，而是反复压入新的调用帧。递归返回时，最近的调用最先恢复，因此天然符合 LIFO。

递归写法通常更接近树的定义，但需要评估最大深度。尾递归在 Java 中也不会被语言规范保证优化，不能依赖编译器自动消除栈帧。

表达式求值中的两个栈

处理中缀表达式时，可以使用操作数栈和运算符栈。遇到数字压入操作数；遇到运算符时，根据优先级决定先计算栈顶操作，括号则控制局部求值范围。

双栈表达式求值过程图

图：操作数栈与运算符栈按优先级协作

更完整的方案可以先用 Shunting-yard 算法把中缀表达式转换成后缀表达式，再用单栈求值。关键仍然是“最近尚未处理的运算符”位于栈顶。

单调栈解决“最近更大/更小”

单调栈中的元素按值保持单调。扫描数组时，把不可能再成为答案的元素弹出，可以把看似双重循环的问题降到 O(n)：每个元素最多入栈、出栈一次。

static int[] nextGreater(int[] values) {
    int[] answer = new int[values.length];
    java.util.Arrays.fill(answer, -1);
    java.util.ArrayDeque<Integer> stack = new java.util.ArrayDeque<>();
    for (int i = 0; i < values.length; i++) {
        while (!stack.isEmpty() && values[stack.peek()] < values[i]) {
            answer[stack.pop()] = values[i];
        }
        stack.push(i);
    }
    return answer;
}

栈里保存索引而不是值，既能比较元素，也能把答案写回原位置。柱状图最大矩形、每日温度、接雨水都能使用类似思想。

DFS 的显式栈细节

若希望显式栈模拟递归的访问顺序，孩子的压栈顺序通常要与递归调用顺序相反。例如想先访问左孩子，就应先压右孩子、再压左孩子。需要后序遍历时，还要保存“节点是否已展开”的状态，不能只存节点本身。

栈溢出与显式栈

递归调用依赖线程调用栈。递归过深时会产生 StackOverflowError。对于深度不受控的树或图遍历，可以把递归改成显式 Deque，让存储位置从线程栈转移到堆，并能更灵活地控制容量和遍历状态。

栈并不会自动解决并发问题。多个线程共享同一个 Deque 时仍需要同步、线程封闭或并发容器。数据结构的操作顺序与线程安全是两个不同维度。

测试清单

空栈 peek/pop 的语义。
容量边界与多次扩容。
弹出后槽位是否释放引用。
连续 push/pop 后顺序是否严格反转。
括号匹配覆盖空串、只有右括号、交叉括号和深层嵌套。
显式 DFS 与递归 DFS 的访问顺序是否一致。

自测

为什么数组栈通常在尾部压栈，而不是头部？
peek 与 pop 有什么区别？
ArrayDeque 为什么比 Stack 更适合作为现代 Java 的栈？
深度优先搜索如何用显式栈代替递归？