【数据结构与算法体系】表、栈和队列

一、抽象数据类型（ADT）导论

在深入具体实现之前，我们必须区分两个经常被混淆的概念：

• 抽象数据类型（ADT）：描述了”做什么”——规定了数据对象及在其上操作的行为，但不涉及具体实现。例如，List ADT 定义了 add(item)、get(index)、size() 等操作的语义。
• 数据结构（Data Structure）：描述了”怎么做”——是 ADT 的具体实现方案。例如，ArrayList 和 LinkedList 都是 List ADT 的不同实现。

理解这种分离是设计可维护软件的基础——客户代码依赖 ADT 接口，而具体实现可以根据场景切换（例如将 ArrayList 换为 LinkedList 以获得更好的插入性能）。

---

二、List ADT 与 ArrayList 实现

2.1 ArrayList 的内部结构

ArrayList 在 Java 中基于动态数组实现。核心成员变量：

public class ArrayList<E> extends AbstractList<E> {
    transient Object[] elementData; // 存储元素的数组
    private int size;               // 当前元素个数
}

2.2 核心操作：add(E e)

public boolean add(E e) {
    modCount++;                     // 结构性修改计数（fail-fast机制）
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();       // 扩容
    elementData[s] = e;
    size = s + 1;
}

扩容机制（Java 17 的 grow() 实现）：

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity,  // 最小增量
                oldCapacity >> 1);          // 偏好增量 = oldCapacity / 2
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

关键公式：新容量 newCapacity = oldCapacity + max(minGrowth, oldCapacity/2)。在 add() 场景中 minGrowth = 1，故实际效果为 $1.5\times$ 扩容（即 $oldCapacity + oldCapacity/2$）。

2.3 为什么是 1.5x 而不是 2x？

这是一个经典的工程权衡。扩容因子 $\alpha$ 的选择涉及空间浪费与摊还时间之间的平衡：

2x 扩容：假设最后一次扩容后容量为 $n$，之前的总容量为 $n + n/2 + n/4 + \cdots = 2n$。这意味着平均浪费的空间为 $n$（当前容量 $n$，数据大小最多也约 $n$）。最坏的空间浪费$\approx 100%$。

1.5x 扩容：类似推导，总容量为 $n + n/1.5 + n/1.5^2 + \cdots = n \cdot \frac{1}{1 - 2/3} = 3n$。最坏浪费 $n$ 但相对 $3n$ 的总分配量来说，更温和。关键在于：1.5x 扩容后，之前已释放的内存块有机会被重用（reuse），因为 $n/1.5 + n/1.5^2 + \cdots < n$ 的累加和 $2n/3 + 4n/9 + \cdots = 2n$ 中，较早释放的块较小，可能组合起来满足后续的扩容需求。而 2x 扩容下，已释放的内存大小 $n + n/2 + n/4 + \cdots = 2n$ 恰好等于下一次扩容所需的大小 $2n$，因此永远无法重用之前释放的内存。

这就是 Java 的 ArrayList 和 Python 的 list（实际上 Python 也使用了约 1.125x 的因子，但通过 realloc 的特殊策略）选择小于 2 的扩容因子的深层原因。

2.4 get 与 set — O(1)

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index); // 直接数组索引：O(1)
}

E elementData(int index) {
    return (E) elementData[index];
}

2.5 add(int index, E element) — O(n)

在中间位置插入需要将 index 开始的后续元素整体后移一位：

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);        // 后移操作：O(n - index)
    elementData[index] = element;
    size = s + 1;
}

System.arraycopy 是 native 方法，底层使用 memmove（或等效的 SIMD 指令），常数因子极小。但渐进复杂度仍为 $O(n)$。

2.6 remove(int index) — O(n)

与中间插入对称，需要将后续元素前移：

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i); // 前移
    es[size = newSize] = null; // 解除引用，帮助GC
}

注意最后一行 es[size] = null：这是 Java 中防止内存泄漏的标准做法。否则即使元素已逻辑删除，数组仍持有它的引用，导致 GC 无法回收。

2.7 完整操作复杂度总结

┌──────────────────┬──────────┬──────────────┐
│     操作          │ 时间复杂度 │ 备注         │
├──────────────────┼──────────┼──────────────┤
│ add(E e)         │ O(1)*    │ *均摊        │
│ add(int, E)      │ O(n)     │ 中间插入     │
│ get(int)         │ O(1)     │              │
│ set(int, E)      │ O(1)     │              │
│ remove(int)      │ O(n)     │              │
│ remove(Object)   │ O(n)     │ 需先查找     │
│ contains(Object) │ O(n)     │              │
│ size()           │ O(1)     │              │
└──────────────────┴──────────┴──────────────┘

---

三、LinkedList 实现

3.1 为什么是双向链表？

Java 的 LinkedList 实现了双向链表（Doubly-Linked List），而非单向链表。每个节点持有 prev 和 next 两个引用：

// Java 内部实现（简化版本）
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

为什么是双向链表？ 核心原因：实现 Deque 接口的需要。双向链表允许在两端都高效地进行增删——addFirst、addLast、removeFirst、removeLast 都是 $O(1)$。单向链表只能在一端高效操作（或在两端都需要 $O(n)$ 找尾节点）。

双向链表还简化了 indexOf 中的”从较近的一端开始搜索”优化。

3.2 LinkedList vs ArrayList 关键操作对比

// LinkedList 的 get(int index) —— O(n)
public E get(int index) {
    checkElementIndex(index);
    return node(index).item; // 遍历链表
}

Node<E> node(int index) {
    // 小优化：从较近一端开始
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;
        return x;
    }
}

即使做了”从较近一端”的优化（$O(n/2)$ 仍为 $O(n)$），get 在 LinkedList 上依然是线性时间。这是 LinkedList 相比 ArrayList 最显著的劣势。

3.3 LinkedList 的内存开销

每个 Node 对象有三部分：

• item：元素引用（4 或 8 字节，取决于 JVM 是 32-bit 还是 64-bit + 压缩指针）
• next：4 字节（压缩指针）
• prev：4 字节（压缩指针）
• Java 对象头：12 字节（64-bit JVM，压缩指针）

每个 Node 实例总计约 24 字节（不含元素本身）。对于包含 100 万个元素的 LinkedList，仅 Node 对象就占用约 24 MB（vs ArrayList 的 Object[] 数组约 8 MB — 仅存储引用）。LinkedList 的内存开销大约是 ArrayList 的 3 倍。

3.4 操作复杂度对比

┌──────────────────┬──────────┬──────────┐
│     操作          │ArrayList │LinkedList│
├──────────────────┼──────────┼──────────┤
│ 随机访问 get(i)  │ O(1)     │ O(n)     │
│ 尾插入 add(E)    │ O(1)*    │ O(1)     │
│ 头插入 add(0,E)  │ O(n)     │ O(1)     │
│ 中间插入 add(i,E)│ O(n)     │ O(n)**   │
│ 尾删除           │ O(1)     │ O(1)     │
│ 头删除           │ O(n)     │ O(1)     │
│ 查找 indexOf     │ O(n)     │ O(n)     │
│ 内存占用         │ 紧凑     │ 3x       │
│ 缓存友好性       │ 好       │ 差       │
└──────────────────┴──────────┴──────────┘
* 均摊
** 虽然插入节点本身是O(1)，但定位到第i个节点需要O(n)

实际性能洞察：即使在 LinkedList 的”优势场景”（头/中间插入），由于现代 CPU 的缓存层次结构，ArrayList 的 System.arraycopy（连续内存块移动，缓存高度友好）在小到中等规模（几千到几万元素）的数据上常常快于 LinkedList 的指针操作（随机内存访问，频繁 cache miss）。这就是为什么 LinkedList 在实践中的使用频率远低于 ArrayList。

---

四、Stack ADT

4.1 LIFO 原则与应用模型

栈（Stack）遵循后进先出（Last-In-First-Out，LIFO）原则。核心操作：

• push(item)：将元素压入栈顶
• pop()：移除并返回栈顶元素
• peek()：返回栈顶元素但不移除
• isEmpty()/size()：辅助操作

4.2 基于数组的栈实现

class ArrayStack<E> {
    private Object[] elements;
    private int top; // 下一个空闲位置
    
    public ArrayStack(int capacity) {
        elements = new Object[capacity];
        top = 0;
    }
    
    public void push(E item) {
        if (top == elements.length) {
            elements = Arrays.copyOf(elements, elements.length * 2);
        }
        elements[top++] = item;
    }
    
    @SuppressWarnings("unchecked")
    public E pop() {
        if (top == 0) throw new EmptyStackException();
        E item = (E) elements[--top];
        elements[top] = null; // 防止内存泄漏
        return item;
    }
    
    @SuppressWarnings("unchecked")
    public E peek() {
        if (top == 0) throw new EmptyStackException();
        return (E) elements[top - 1];
    }
    
    public boolean isEmpty() { return top == 0; }
    public int size() { return top; }
}

所有操作 $O(1)$。扩容虽然触发 $O(n)$ 的复制，但摊还分析表明这 $O(1)$ 均摊成本。

4.3 基于链表的栈实现

class LinkedStack<E> {
    private static class Node<E> {
        E item;
        Node<E> next;
        Node(E item, Node<E> next) { this.item = item; this.next = next; }
    }
    
    private Node<E> head; // 栈顶
    private int size;
    
    public void push(E item) {
        head = new Node<>(item, head); // 新元素成为新的头
        size++;
    }
    
    public E pop() {
        if (head == null) throw new EmptyStackException();
        E item = head.item;
        head = head.next; // GC回收旧头节点
        size--;
        return item;
    }
    
    public E peek() {
        if (head == null) throw new EmptyStackException();
        return head.item;
    }
    
    public boolean isEmpty() { return head == null; }
    public int size() { return size; }
}

所有操作也 $O(1)$。链式实现不需要扩容，但每次 push 涉及 new Node 的对象创建开销。

4.4 表达式求值——双栈算法（Dijkstra’s Two-Stack Algorithm）

这是栈最经典的应用之一，用于求值含有操作符优先级的算术表达式。

class ExpressionEvaluator {
    public static double evaluate(String expression) {
        Deque<Double> values = new ArrayDeque<>();   // 操作数栈
        Deque<Character> ops = new ArrayDeque<>();    // 操作符栈
        
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            
            if (ch == ' ') continue;
            
            if (Character.isDigit(ch)) {
                // 解析完整数字
                StringBuilder sb = new StringBuilder();
                while (i < expression.length() && 
                       (Character.isDigit(expression.charAt(i)) || 
                        expression.charAt(i) == '.')) {
                    sb.append(expression.charAt(i++));
                }
                i--; // 回退一位
                values.push(Double.parseDouble(sb.toString()));
            } else if (ch == '(') {
                ops.push(ch);
            } else if (ch == ')') {
                // 遇到右括号，计算到左括号
                while (ops.peek() != '(') {
                    values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                }
                ops.pop(); // 弹出 '('
            } else if (isOperator(ch)) {
                // 优先级不高于栈顶 → 先计算
                while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(ch)) {
                    values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                }
                ops.push(ch);
            }
        }
        
        // 处理剩余操作符
        while (!ops.isEmpty()) {
            values.push(applyOp(ops.pop(), values.pop(), values.pop()));
        }
        
        return values.pop();
    }
    
    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
    
    private static int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }
    
    private static double applyOp(char op, double b, double a) {
        // 注意：a先入栈，b后入栈，所以a op b
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': 
                if (b == 0) throw new ArithmeticException("除以零");
                return a / b;
        }
        return 0;
    }
}

双栈算法优雅地处理了操作符优先级和括号嵌套，且时间复杂度和空间复杂度都是 $O(n)$。

4.5 函数调用栈

Java 的 JVM 在每个线程内部维护一个调用栈（Call Stack），每个方法调用创建栈帧（Stack Frame），包含：

• 局部变量表（Local Variables）
• 操作数栈（Operand Stack）
• 返回地址（Return Address）

递归过深导致 StackOverflowError 正是因为调用栈超出 JVM 预设的大小（默认约 1MB）。

---

五、Queue ADT

5.1 FIFO 原则

队列（Queue）遵循先进先出（First-In-First-Out，FIFO）原则。核心操作：

• enqueue(item) / offer(item)：加入队尾
• dequeue() / poll()：移除队头
• peek()：查看队头

5.2 循环数组实现（Circular Array Queue）

class CircularQueue<E> {
    private Object[] elements;
    private int head;  // 队头位置
    private int tail;  // 下一个空闲位置
    private int size;
    
    public CircularQueue(int capacity) {
        elements = new Object[capacity];
        head = 0;
        tail = 0;
        size = 0;
    }
    
    public boolean offer(E item) {
        if (size == elements.length) {
            // 扩容
            Object[] newElements = new Object[elements.length * 2];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[(head + i) % elements.length];
            }
            elements = newElements;
            head = 0;
            tail = size;
        }
        elements[tail] = item;
        tail = (tail + 1) % elements.length;
        size++;
        return true;
    }
    
    @SuppressWarnings("unchecked")
    public E poll() {
        if (size == 0) return null;
        E item = (E) elements[head];
        elements[head] = null; // 防止内存泄漏
        head = (head + 1) % elements.length;
        size--;
        return item;
    }
    
    @SuppressWarnings("unchecked")
    public E peek() {
        if (size == 0) return null;
        return (E) elements[head];
    }
    
    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
}

循环数组的关键点：

• 使用模运算 % 实现循环（实际实现中常用位运算 & (capacity-1) 替代，当 capacity 为 2 的幂时）
• head == tail 有两种含义：队列空的初始状态，或队列满的状态。通过额外的 size 变量区分两者（另一种方案是牺牲一个位置，用”tail + 1 == head”表示满）

5.3 Deque（双端队列）

双端队列（Double-Ended Queue）允许高效地在两端进行插入和删除。Java 的 ArrayDeque 基于循环数组实现，是 Stack 和 Queue 的推荐替代品。

// Java 官方推荐：用 Deque 代替 Stack
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);       // 入栈
int top = stack.pop(); // 出栈

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);      // 入队
int head = queue.poll(); // 出队

为什么 ArrayDeque 比 Stack 更好？ Java 的 Stack 继承自 Vector（遗留类，全方法 synchronized），性能差且违反了”组合优于继承”原则——Stack 不是 Vector 的”is-a”关系。

5.4 BFS 中的队列应用

队列是 BFS 的自然助手（逐层处理，先入先出）。滑动窗口最大值问题（Sliding Window Maximum）也是队列（更具体地说是单调队列 / Monotonic Queue）的经典应用：

// 滑动窗口最大值：O(n)
class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // 存储下标，维护单调递减
        
        for (int i = 0; i < n; i++) {
            // 移除超出窗口的元素
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            // 维护单调递减：移除所有小于当前值的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            
            // 窗口形成后记录结果
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

单调队列技巧：通过维护”过期淘汰”和”单调性维护”两条规则，将看似需要 $O(nk)$ 的问题压缩到 $O(n)$。

---

六、Java Collections 源码深潜

6.1 为什么 ArrayList 用 1.5x 扩容（详析）

Java 8 早期版本使用 int newCapacity = oldCapacity + (oldCapacity >> 1)（即 1.5x）。Java 17 使用 ArraysSupport.newLength，对于 add() 调用仍等效于 1.5x。

下面给出摊还分析的严格推导。假设扩容因子为 $\alpha$（$\alpha > 1$），从空表开始连续 $n$ 次 add。

总复制成本：设最终容量为 $n$，扩容发生的容量序列为：$1, \alpha, \alpha^2, \ldots, \alpha^k \geq n$。
总复制成本 $= 1 + \alpha + \alpha^2 + \cdots + \alpha^k = \frac{\alpha^{k+1} - 1}{\alpha - 1} \approx \frac{\alpha n}{\alpha - 1}$。

摊还成本：$\frac{\text{总成本}}{n} \approx \frac{\alpha}{\alpha - 1}$。

• $\alpha = 2$：摊还成本 $\approx \frac{2}{1} = 2$ 次操作/add，空间浪费 ≤ 100%
• $\alpha = 1.5$：摊还成本 $\approx \frac{1.5}{0.5} = 3$ 次操作/add，空间浪费 ≤ 50%

1.5x 的选择在摊还时间成本（$3$ vs $2$）和空间效率之间取得了工程上的平衡。内存分配器（malloc/realloc）也能更好地复用之前的释放块。

6.2 ArrayList 的 fail-fast 机制

// 使用 modCount 检测并发修改
public E next() {
    checkForComodification();
    // ...
}

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

在单线程中，如果在迭代过程中使用非迭代器的方法修改集合（如 list.remove(0) 而非 iterator.remove()），modCount 增加但 expectedModCount 不变，触发 ConcurrentModificationException。这是一种”快速失败”的防御性设计。

6.3 LinkedList 的实现巧妙之处

双向链表允许 listIterator 在任意方向高效遍历。ListIterator 维护当前节点引用，因此 next() 和 previous() 都是 $O(1)$。

---

七、三个 ADT 的内存布局

Stack (数组实现):         Queue (循环数组):        LinkedList:
┌─────┐                   ┌───┬───┬───┬───┐       head → [A]↔[B]↔[C] ← tail
│ top │                   │   │ 2 │ 3 │   │               ↑prev  ↑prev
│  3  │                   ├───┼───┼───┼───┤               ↓next  ↓next
│  2  │                  head→      tail
│  1  │              
│  0  │              
└─────┘
连续内存，缓存友好         连续内存（循环），缓存友好    节点分散，缓存不友好

---

八、面试常见追问

问题一：在什么具体场景下 LinkedList 比 ArrayList 更好？

回答：单纯从时间复杂度看，LinkedList 在”头端频繁插入/删除”时比 ArrayList 好（$O(1)$ vs $O(n)$）。但在实践中，只有当数据量很大（$> 10^5$）且确实只在头部操作时，LinkedList 才有显著优势。

更实用的场景是：需要频繁地通过 ListIterator.add() 在迭代过程中插入元素（如在文本编辑器中维护行列表），此时 LinkedList 可以做到 $O(1)$ 的迭代器插入，而 ArrayList 需要 $O(n)$ 的数组移动。

另外，LinkedList 同时实现了 Deque，可以直接用作双端队列。

问题二：为什么 ArrayList 没有像 C++ 的 vector 一样提供 shrink_to_fit？

回答：Java 的 ArrayList 其实提供了 trimToSize() 方法：

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

但实际中不常用，原因在于：如果随后又有元素添加，立即触发扩容（重新分配 + 复制），反而比”保留多余空间”更差。Java 的设计哲学倾向于让程序员自行调用 trimToSize 而非自动收缩。

问题三：自己实现栈时，用数组还是链表？

回答：

• 数组：操作 $O(1)$，摊还成本低，缓存友好，绝大多数情况推荐
• 链表：每次 push 创建新节点（内存分配），pop 释放节点。当无法预知最大容量且希望避免扩容拷贝时可用，但一般 ArrayDeque 的扩容已经足够高效

Java 官方立场：ArrayDeque 优于 Stack 和 LinkedList（用于队列/栈场景）。

问题四：两个栈如何模拟一个队列？

回答：用 inStack（负责入队）和 outStack（负责出队）。入队时 push 到 inStack。出队时，如果 outStack 为空，将 inStack 所有元素逐个 pop 并 push 到 outStack，然后从 outStack pop。

class TwoStackQueue<E> {
    Deque<E> in = new ArrayDeque<>();
    Deque<E> out = new ArrayDeque<>();
    
    public void offer(E e) { in.push(e); }
    
    public E poll() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
        return out.pop();
    }
}

摊还分析：每个元素恰好被 push 1 次（入 in）、pop 1 次（从 in）、push 1 次（入 out）、pop 1 次（从 out）。总 4 次操作，均摊 $O(1)$ 每次 offer 或 poll。

问题五：手写一个支持 getMin() 的栈（最小栈），所有操作 O(1)

回答：维护两个栈——主栈和辅助栈（存储当前最小值）。

class MinStack {
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> minStack = new ArrayDeque<>();
    
    public void push(int x) {
        stack.push(x);
        int min = minStack.isEmpty() ? x : Math.min(x, minStack.peek());
        minStack.push(min);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

空间优化：仅当新元素 $\leq$ 当前最小值时才 push 到 minStack。pop 时若栈顶 == minStack 顶则同步弹出。这样可以节省大量重复最小值的空间。

---

九、总结

表、栈、队列是构建一切复杂数据结构和算法的基础砖块：

• ArrayList：随机访问 $O(1)$，1.5x 扩容机制平衡了时间与空间
• LinkedList：双向链表，头尾操作 $O(1)$，但缓存性能差
• Stack：LIFO，双栈算法优雅求解表达式求值
• Queue：FIFO，循环数组节省空间，BFS 的自然搭档
• Deque：双端队列，ArrayDeque 是 Java 中栈和队列的最佳实现

理解这些基本 ADT 的底层实现和复杂度特性，是进阶到更加高级的数据结构（优先队列、斐波那契堆、van Emde Boas 树）的必要前提。下一篇【数据结构与算法体系】之摊还分析 将深入剖析动态数组扩容背后的数学原理。