1. 栈是什么？理解 LIFO 特性

栈（Stack）是一种非常基础且重要的数据结构，它的核心特点是 LIFO（Last In First Out，后进先出）。你可以把它想象成一摞盘子——你总是把新洗好的盘子放在最上面，需要用时也是先从最上面取。最后一个放上去的盘子，第一个被拿走。

在计算机世界中，栈的这种特性被广泛应用。例如：

​​​​​​

• 函数调用：当 A 调用 B，B 调用 C 时，C 先返回，然后 B 返回，最后 A 返回。

• 浏览器的后退按钮：你浏览的页面依次入栈，点击后退时弹出当前页面，回到上一个页面。

• 撤销操作（Undo）：每次操作入栈，撤销时弹出最近的操作。

栈通常支持两个基本操作：

• push：将元素压入栈顶。

• pop：将栈顶元素弹出并返回。

此外，还经常提供 peek（查看栈顶元素但不弹出）和判断是否为空等方法。

2. 栈的应用场景举例：括号匹配

在编程中，括号匹配是一个经典问题。比如表达式 {[()]} 是合法的，而 {[(])} 则不合法。我们可以用栈轻松解决：

• 遍历字符串的每个字符。

• 如果是左括号（{、[、(），则将其压入栈。

• 如果是右括号（}、]、)），则检查栈顶是否是对应的左括号：

  • 如果匹配，弹出栈顶；

  • 如果不匹配或栈已空，则表达式非法。

• 遍历结束后，如果栈为空，说明所有括号都正确匹配；否则有未闭合的左括号。

这正是栈“后进先出”特性的典型应用：最近遇到的左括号必须与接下来遇到的右括号匹配。

3. 用数组实现栈的思路

为什么选择数组？

栈可以用数组或链表实现。数组的优势在于：

• 内存连续，CPU 缓存友好，访问速度快。

• 实现简单，push 和 pop 操作只需移动下标。

• 扩容虽然需要复制数据，但均摊成本很低（每次扩容后，后续很多次 push 都不再扩容）。

设计成员

我们可以设计一个简化版的栈，内部使用数组存储元素，用一个 size 变量记录当前元素个数（即栈顶位置的下一个索引）。栈顶元素始终位于 size - 1 处。

• 数组：private Object[] elements;

• 元素个数：private int size;

• 初始容量可以设为 10（像 ArrayList 一样）。

push 操作

1. 检查数组是否已满（size == elements.length），如果是，则进行扩容。

2. 将新元素放入 elements[size] 位置。

3. size++。

pop 操作

1. 检查栈是否为空（size == 0），如果是，抛出异常（如 EmptyStackException）。

2. size--，取出 elements[size]。

3. 将原位置设为 null，帮助垃圾回收（避免内存泄漏）。

4. 返回取出的元素。

扩容机制

当数组已满时，我们需要一个更大的数组来容纳新元素。通常扩容为原容量的 1.5 倍或 2 倍（Java 的 ArrayList 是 1.5 倍，ArrayDeque 是 2 倍）。我们选择 2 倍，实现简单。

扩容步骤：

1. 创建一个新数组，长度为原数组的 2 倍。

2. 使用 System.arraycopy 将原数组的所有元素复制到新数组。

3. 将成员变量 elements 指向新数组。

4. 原数组失去引用，会被垃圾回收。

4. 手写代码：MyArrayStack

下面我们实现一个简单的泛型栈 MyArrayStack<E>

import java.util.EmptyStackException;

/**
 * 基于数组实现的简单栈（模仿 ArrayDeque 的栈功能）
 * @param <E> 元素类型
 */
public class MyArrayStack<E> {
    // 存储元素的数组
    private Object[] elements;
    // 当前栈中的元素个数
    private int size;

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 构造一个默认容量的栈
     */
    public MyArrayStack() {
        elements = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    /**
     * 压入元素到栈顶
     * @param item 要压入的元素
     */
    public void push(E item) {
        // 检查是否需要扩容
        if (size == elements.length) {
            grow();
        }
        // 将元素放到 size 位置，然后 size 加 1
        elements[size++] = item;
    }

    /**
     * 弹出栈顶元素
     * @return 栈顶元素
     * @throws EmptyStackException 如果栈为空
     */
    @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        // 因为 size 指向下一个空位，所以栈顶元素在 size-1
        E item = (E) elements[--size];
        // 将原位置置为 null，帮助 GC
        elements[size] = null;
        return item;
    }

    /**
     * 查看栈顶元素但不弹出
     * @return 栈顶元素
     * @throws EmptyStackException 如果栈为空
     */
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (E) elements[size - 1];
    }

    /**
     * 判断栈是否为空
     * @return true 如果栈为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回栈中元素个数
     * @return 元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 扩容：将数组容量扩大为原来的 2 倍
     */
    private void grow() {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity * 2;
        // 创建新数组
        Object[] newElements = new Object[newCapacity];
        // 复制原数组内容到新数组
        System.arraycopy(elements, 0, newElements, 0, size);
        // 将 elements 指向新数组
        elements = newElements;
        // 原数组不再被引用，等待垃圾回收
    }

    // 可选：为了测试方便，重写 toString 打印栈内容（从栈底到栈顶）
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");
            sb.append(elements[i]);
        }
        sb.append("]");
        return sb.toString();
    }
}

5. 扩容时的数据迁移详解

假设当前数组容量为 4，已经存了 4 个元素（size = 4）。此时再调用 push(5)：

1. 检测到 size == elements.length，触发 grow()。

2. 新容量 = 4 * 2 = 8。

3. 创建长度为 8 的新数组。

4. 使用 System.arraycopy(elements, 0, newElements, 0, size) 将原数组的 4 个元素复制到新数组的索引 0~3 处。

5. 将 elements 引用指向新数组，原数组失去引用，后续会被 GC 回收。

6. 回到 push 方法，将新元素 5 放入 elements[4]，size 变为 5。

整个过程如下图所示（文字示意）：

原数组: [ A, B, C, D ]   size = 4, 容量 = 4
push(E) 触发扩容
新数组: [ null, null, null, null, null, null, null, null ] 容量 = 8
复制后: [ A, B, C, D, null, null, null, null ]
替换引用后: elements 指向新数组
最后 push 新元素: [ A, B, C, D, E, null, null, null ]  size = 5

6. 测试代码及结果

我们来写一个简单的测试类，验证栈的基本功能以及扩容是否正常工作。

public class MyArrayStackTest {
    public static void main(String[] args) {
        MyArrayStack<Integer> stack = new MyArrayStack<>();

        // 测试 push 和扩容
        for (int i = 1; i <= 15; i++) {
            stack.push(i);
            System.out.println("push " + i + "，当前栈：" + stack);
        }

        // 测试 pop 和 peek
        System.out.println("栈顶元素 peek: " + stack.peek());
        while (!stack.isEmpty()) {
            System.out.println("pop: " + stack.pop() + "，剩余栈：" + stack);
        }

        // 测试空栈异常
        try {
            stack.pop();
        } catch (EmptyStackException e) {
            System.out.println("捕获到空栈异常，正确！");
        }
    }
}

运行结果示例（具体输出可能因实现略有不同）：

push 1，当前栈：[1]
push 2，当前栈：[1, 2]
...
push 10，当前栈：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
push 11，当前栈：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  （此处已扩容一次）
...
push 15，当前栈：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
栈顶元素 peek: 15
pop: 15，剩余栈：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
pop: 14，剩余栈：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
...
pop: 1，剩余栈：[]
捕获到空栈异常，正确！

从输出可以看到，当 push 第 11 个元素时，数组自动扩容，后续操作一切正常。

7. 总结与思考

• LIFO 特性：通过 push 和 pop 在数组末尾操作实现。

• 数组实现：用数组存储，size 记录元素个数，栈顶在 size-1 处。

• 动态扩容：当数组满时，创建新数组并复制原数据，保证栈可以无限增长。

• 数据迁移：扩容时的复制操作，是数组实现动态容量的核心。

与 Java 集合框架的对比

Java 标准库提供了多种栈的实现：

• java.util.Stack：继承自 Vector，是线程安全的（同步的），但效率较低，已不推荐使用。

• java.util.ArrayDeque：双端队列，可以用作栈（push/pop 方法），底层也是循环数组，但扩容策略为 2 倍，且支持从两端操作，性能优于 Stack。

我们手写的 MyArrayStack 实际上就是 ArrayDeque 简化版（只实现了栈功能，未使用循环数组）。