第 5 章　栈与队列

本章解决的问题：为什么"后进先出"和"先进先出"这两个简单的规则，能撑起编译器、操作系统、浏览器的半边天？

5.1　栈：后进先出

学习目标：学完本节，你能

• 说清栈的 LIFO 特性与三个核心操作；
• 从零实现一个基于数组的栈，并说清每一步的复杂度；
• 解释"弹出元素后清引用"为什么不是可选项 —— 这是本节最重要的工程细节。

先修：3.1、3.2（数组与动态数组）。 固定术语：栈、后进先出（LIFO）、压栈、弹栈、栈顶。 环境与版本：.NET 8 / C# 12。 预计阅读：24 分钟。

一、直觉：一摞盘子

食堂里的一摞盘子：

• 你只能从最上面拿（不能从中间抽）
• 新的盘子只能放在最上面

所以最后放上去的那个，一定会最先被拿走。这就是后进先出（LIFO，Last In First Out）。

生活中到处都是这个模式：

注意最后一条：2.2 节讲的调用栈本身就是一个栈 —— 这就是"栈"这个名字的由来。

你其实早就在用栈了，只是当时没给它起名字。

二、形式化：三个操作

关键约束：栈不允许访问中间的元素。你只能碰栈顶。

这个限制看起来是缺点，其实是优点 —— 正因为接口这么窄，实现才能这么简单、这么快，而且很难用错。

"栈"和"队列"（5.2 节）都属于受限的线性结构：它们比数组和链表能做的事更少，但正因为限制，它们在特定场景下更简单、更安全。

这是数据结构设计里一个反复出现的主题：限制换来的是清晰和安全。

三、完整实现

新建控制台项目，粘贴以下代码：

using System.Runtime.CompilerServices;

// ==================== 实验一：栈的基本操作 ====================

Console.WriteLine("=== 实验一：后进先出（LIFO）===");
Console.WriteLine();

var stack = new MyStack<string>();

foreach (var name in new[] { "第一本", "第二本", "第三本" })
{
    stack.Push(name);
    Console.WriteLine($"  push({name,-8})  栈内: {stack}   (栈顶 = {stack.Peek()})");
}
Console.WriteLine();

while (!stack.IsEmpty)
{
    string top = stack.Pop();
    Console.WriteLine($"  pop() -> {top,-8}  栈内: {stack}");
}
Console.WriteLine();

Console.WriteLine("  注意：最后 push 进去的「第三本」最先出来 —— 这就是 LIFO（Last In First Out）。");
Console.WriteLine();

// 空栈操作
Console.WriteLine("  空栈上调用 Pop() 会怎样？");
try
{
    stack.Pop();
}
catch (InvalidOperationException ex)
{
    Console.WriteLine($"    抛出异常: {ex.Message}   <- 而不是返回一个错误的值");
}
Console.WriteLine();

// ==================== 实验二：应用 —— 撤销操作 ====================

Console.WriteLine("=== 实验二：应用场景 —— 文本编辑器的撤销 ===");
Console.WriteLine();

var undoStack = new MyStack<string>();
var document = new System.Text.StringBuilder();

void Type(string text)
{
    undoStack.Push(document.ToString());     // 改之前先存一份快照
    document.Append(text);
    Console.WriteLine($"  输入 \"{text}\"      -> 当前内容: \"{document}\"");
}

void Undo()
{
    if (undoStack.IsEmpty) { Console.WriteLine("  没有可撤销的操作了"); return; }
    string previous = undoStack.Pop();        // 回到上一个快照
    Console.WriteLine($"  撤销          -> 当前内容: \"{previous}\"");
    document.Clear();
    document.Append(previous);
}

Type("你好");
Type("，世界");
Type("！");
Console.WriteLine();
Undo();
Undo();
Undo();
Undo();
Console.WriteLine();
Console.WriteLine("  撤销的实现天然就是栈：最后编辑的先被撤销。");
Console.WriteLine("  （真实编辑器用的是「命令模式 + 栈」，但栈这个核心是一样的）");
Console.WriteLine();

// ==================== 实验三：一个容易忽略的内存陷阱 ====================

Console.WriteLine("=== 实验三：弹出元素后，底层数组还持有它吗？ ===");
Console.WriteLine();

// 关键：对象的创建必须隔离到独立方法里（并且禁止内联）。
// 如果写在顶级语句里，那个局部变量的栈槽会一直活到方法结束，
// 导致「对象还活着」恒为 true —— 那是测试方法的假象，不是真实的泄漏。
WeakReference weakLeaky = LeakTest.PushThenPopLeaky();
WeakReference weakFixed = LeakTest.PushThenPopFixed();

GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();

Console.WriteLine($"  LeakyStack（弹出时不清引用）: 对象还活着 = {weakLeaky.IsAlive}");
Console.WriteLine($"                                <- 底层数组 _items[0] 仍然指向它，GC 回收不了");
Console.WriteLine($"  MyStack（弹出时清引用）     : 对象还活着 = {weakFixed.IsAlive}");
Console.WriteLine($"                                <- 引用被置为 null，GC 正常回收");
Console.WriteLine();

Console.WriteLine("  这就是为什么 MyStack.Pop() 里要多写一行 `_items[_count] = default!;`");
Console.WriteLine("  对 int 这类值类型无所谓，但对引用类型，漏掉这行会造成「隐形内存泄漏」：");
Console.WriteLine("  元素明明已经出栈了，却因为底层数组还指着它而无法被回收。");
Console.WriteLine();

// ==================== 实验四：性能 —— 数组栈 vs 链表栈 ====================

Console.WriteLine("=== 实验四：数组实现的栈，性能如何 ===");
Console.WriteLine();

const int N = 1_000_000;
var perfStack = new MyStack<int>();

var sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < N; i++) perfStack.Push(i);
long afterPush = GC.GetAllocatedBytesForCurrentThread();

long sum = 0;
for (int i = 0; i < N; i++) sum += perfStack.Pop();
sw.Stop();

Console.WriteLine($"  压入并弹出 {N:N0} 个元素: {sw.Elapsed.TotalMilliseconds:F1} ms");
Console.WriteLine($"  push 阶段新分配内存: {(afterPush) / 1024.0 / 1024.0:F2} MB（数组扩容所致）");
Console.WriteLine($"  校验和 = {sum:N0}（应为 {(long)N * (N - 1) / 2:N0}）");
Console.WriteLine();
Console.WriteLine("  数组实现栈的代价和动态数组完全一样：push 是摊还 O(1)，偶尔扩容搬运一次。");
Console.WriteLine();

// ==================== 栈的实现 ====================

/// <summary>基于数组的栈。所有操作都是 O(1)（push 为摊还 O(1)）。</summary>
public class MyStack<T>
{
    private T[] _items;
    private int _count;

    public MyStack(int capacity = 4)
    {
        _items = new T[capacity];
    }

    public int Count => _count;
    public bool IsEmpty => _count == 0;

    public void Push(T item)
    {
        if (_count == _items.Length)
        {
            var bigger = new T[_items.Length * 2];
            Array.Copy(_items, bigger, _count);
            _items = bigger;
        }
        _items[_count] = item;
        _count++;
    }

    public T Pop()
    {
        if (_count == 0)
            throw new InvalidOperationException("栈为空，无法 Pop");

        _count--;
        T item = _items[_count];
        _items[_count] = default!;      // ← 清掉引用！对引用类型至关重要
        return item;
    }

    public T Peek()
    {
        if (_count == 0)
            throw new InvalidOperationException("栈为空，无法 Peek");
        return _items[_count - 1];
    }

    public override string ToString()
    {
        var parts = new string[_count];
        for (int i = 0; i < _count; i++) parts[i] = _items[i]?.ToString() ?? "null";
        return "[" + string.Join(", ", parts) + "]";
    }
}

/// <summary>故意写错的版本：Pop 时不清引用，用来演示「隐形内存泄漏」。</summary>
public class LeakyStack<T>
{
    private T[] _items = new T[16];
    private int _count;

    public void Push(T item) => _items[_count++] = item;

    public T Pop() => _items[--_count];     // ← 少了 _items[_count] = default!;
}

/// <summary>
/// 内存泄漏实验的辅助类。
/// 两个栈对象作为静态字段「活下去」，而测试对象只在方法内部创建 ——
/// 方法一返回，对测试对象的局部引用就消失了，此时还活着的就只能是栈内部持有的引用。
/// </summary>
public static class LeakTest
{
    private static readonly MyStack<object> FixedHolder = new();
    private static readonly LeakyStack<object> LeakyHolder = new();

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static WeakReference PushThenPopLeaky()
    {
        object payload = new object();
        LeakyHolder.Push(payload);
        LeakyHolder.Pop();
        return new WeakReference(payload);
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static WeakReference PushThenPopFixed()
    {
        object payload = new object();
        FixedHolder.Push(payload);
        FixedHolder.Pop();
        return new WeakReference(payload);
    }
}

实测输出（.NET 8 Release）：

  注意：最后 push 进去的「第三本」最先出来 —— 这就是 LIFO（Last In First Out）。

  空栈上调用 Pop() 会怎样？
    抛出异常: 栈为空，无法 Pop   <- 而不是返回一个错误的值

=== 实验二：应用场景 —— 文本编辑器的撤销 ===

  输入 "你好"      -> 当前内容: "你好"
  输入 "，世界"      -> 当前内容: "你好，世界"
  输入 "！"      -> 当前内容: "你好，世界！"

  撤销          -> 当前内容: "你好，世界"
  撤销          -> 当前内容: "你好"
  撤销          -> 当前内容: ""
  没有可撤销的操作了

=== 实验三：弹出元素后，底层数组还持有它吗？ ===

  LeakyStack（弹出时不清引用）: 对象还活着 = True
                                <- 底层数组 _items[0] 仍然指向它，GC 回收不了
  MyStack（弹出时清引用）     : 对象还活着 = False
                                <- 引用被置为 null，GC 正常回收

=== 实验四：数组实现的栈，性能如何 ===

  压入并弹出 1,000,000 个元素: 13.8 ms
  push 阶段新分配内存: 8.06 MB（数组扩容所致）
  校验和 = 499,999,500,000（应为 499,999,500,000）

四、实验三值得单独讲：一个隐蔽的内存泄漏

这是本节最有价值的部分。看 Pop() 的两行：

_count--;
T item = _items[_count];
_items[_count] = default!;      // ← 这一行能不能省？

答案：对 int 这类值类型可以省，对引用类型绝对不能省。

为什么？

Pop() 之后，_count 减少了，逻辑上那个元素已经不在栈里了。但底层数组 _items 仍然持有对它的引用：

逻辑视图（count=2）:  [ A, B ]
底层数组（长度 4）:   [ A, B, C, D ]
                              ↑
                        已经"出栈"了，但数组还指着它

只要数组还指着 C 和 D，GC 就不会回收它们。如果这些对象很大（比如一个 10 MB 的图片缓冲区），或者栈被反复压入弹出成千上万次，内存就会持续增长。

实测证据：

  LeakyStack（弹出时不清引用）: 对象还活着 = True    ← 泄漏了
  MyStack（弹出时清引用）     : 对象还活着 = False   ← 正常回收

这个实验的方法本身也值得学。

我第一版把对象创建写在顶级语句里，结果两个都返回 True —— 因为那个局部变量的栈槽一直活到方法结束，payload = null 也没用。

修正的方法是：把对象的创建隔离到一个独立方法里，并加 [MethodImpl(MethodImplOptions.NoInlining)]。这样方法一返回，对测试对象的局部引用就消失了，此时还活着的引用只可能来自栈内部。

测内存泄漏时，"引用到底从哪来"必须想清楚，否则测出来的全是假象。

工程建议：

• 自己写容器类时，Pop / RemoveAt / Clear 都要清引用。
• .NET 的 Stack<T>、List<T>、Queue<T> 内部都做了这件事（可以去看它们的源码）。
• 从 ArrayPool<T> 借来的数组归还前也应该清引用（Array.Clear），否则会把对象"扣"在池子里。

五、实验四：性能与代价

  压入并弹出 1,000,000 个元素: 13.8 ms
  push 阶段新分配内存: 8.06 MB（数组扩容所致）

13.8 ms 处理 200 万次操作，平均每次约 7 纳秒。

代价在哪？

栈比动态数组更适合用数组实现：因为栈的所有操作都在尾部进行，而尾部操作在数组上是 $O(1)$ 的。

对比链表实现：链表栈的 Push/Pop 也是 $O(1)$，但每个元素要多花 32 字节，而且遍历和访存都慢（4.1 节实测慢 3.8～7.4 倍）。

所以数组是栈的标准实现方式。 C# 的 Stack<T> 内部就是一个 T[]。

六、练习

练习 5.1.1（识别） 下面四个场景，哪些适合用栈？ (a) 检查一个字符串里的括号是否配对 (b) 按顺序处理一批任务 (c) 实现"撤销/重做"功能 (d) 求一个表达式 3 + 4 * 2 的值

练习 5.1.2（写代码） 用栈实现一个方法 Reverse<T>(T[] array)，把数组原地反转。 要求：$O(n)$ 时间、$O(n)$ 额外空间（用栈）、不新建数组。

练习 5.1.3（找 bug） 下面这个基于数组的栈实现有两个 bug，请指出：

public class BuggyStack<T>
{
    private T[] _items = new T[4];
    private int _count;

    public void Push(T item)
    {
        _items[_count] = item;
        _count++;
    }

    public T Pop()
    {
        _count--;
        return _items[_count];
    }
}

练习 5.1.4（判断） 判断对错并说明理由： (a) 栈可以用数组实现，也可以用链表实现，两者复杂度一样，所以随便选哪个都行。 (b) Pop() 之后元素就"不在内存里"了。 (c) 用 Peek() 看完栈顶再 Pop()，比直接 Pop() 慢。

练习 5.1.5（挑战·设计） 设计一个栈，除了 Push / Pop / Peek 之外，还要支持 GetMin() —— 返回当前栈中的最小值，要求 $O(1)$ 时间。 （提示：用一个辅助栈。想清楚：什么时候该往辅助栈里压东西？）

七、练习答案

5.1.1

• (a) 适合。 括号匹配是栈的经典应用 —— 最后打开的括号最先闭合，天然的 LIFO。5.3 节会完整实现。
• (b) 不适合，应该用队列。 "按顺序处理"是先进先出，队列才是对的（5.2 节）。
• (c) 适合。 撤销是 LIFO 的典型场景。

  但"重做（Redo）"需要另一个栈：撤销时把操作压入 redo 栈，重做时再从 redo 栈弹出。两个栈配合才完整。

• (d) 适合。 表达式求值是栈最经典的应用之一 —— 既要处理运算符优先级，又要处理括号。5.3 节会完整实现。

5.1.2

static void Reverse<T>(T[] array)
{
    var stack = new MyStack<T>(array.Length);

    foreach (var item in array)
        stack.Push(item);              // 全部压栈

    for (int i = 0; i < array.Length; i++)
        array[i] = stack.Pop();        // 弹出来的顺序正好是反的
}

验证：[1, 2, 3, 4] → 压栈后栈内是 [1, 2, 3, 4]（栈顶是 4）→ 依次弹出得到 4, 3, 2, 1 → 写回数组 ✓

但要说实话：这个做法不如双指针。

3.3 节的相向双指针可以在 $O(1)$ 额外空间下完成同样的反转：

int lo = 0, hi = array.Length - 1;
while (lo < hi) { (array[lo], array[hi]) = (array[hi], array[lo]); lo++; hi--; }

这道题的价值在于演示"栈可以反转顺序"这个性质，而不是推荐你这么做。能用双指针就用双指针。

5.1.3

Bug 1：Push 没有扩容检查。

_items 初始容量是 4。压入第 5 个元素时 _items[4] = item 会抛 IndexOutOfRangeException。

public void Push(T item)
{
    if (_count == _items.Length) Grow();     // ← 缺这一句
    _items[_count] = item;
    _count++;
}

Bug 2：Pop 没有空栈检查，而且不清引用。

public T Pop()
{
    if (_count == 0)                          // ← 缺这一句
        throw new InvalidOperationException("栈为空");
    _count--;
    T item = _items[_count];
    _items[_count] = default!;                // ← 也缺这一句（引用类型会泄漏）
    return item;
}

空栈时 _count-- 变成 -1，然后 _items[-1] 抛 IndexOutOfRangeException。异常是抛了，但抛的是"下标越界"而不是"栈为空" —— 错误信息会误导排查方向。

_count-- 写成 -1 还会污染内部状态：即使调用者 catch 了异常，这个栈对象也已经坏掉了（后续 Push 会写到 _items[-1]）。

5.1.4

• (a) 错。 虽然复杂度都是 $O(1)$，但常数和内存差很多：
  • 数组实现：每个元素 4 字节（int），缓存友好。
  • 链表实现：每个节点约 32 字节，8 倍内存开销，遍历慢 3.8～7.4 倍（4.1 节实测）。

    所以数组是栈的标准实现。链表实现只有在"栈可能极端深、不想预分配大数组"时才有意义 —— 但这种情况很少。

• (b) 错，而且这正是本节的重点。 元素逻辑上不在栈里了（Count 减少），但物理上底层数组可能还持有它的引用，导致 GC 无法回收。必须显式 _items[_count] = default!;。
• (c) 错。 Peek() 和 Pop() 都是 $O(1)$，而且 Peek 做的事情比 Pop 还少（不修改 _count）。

  但从语义上，Peek + Pop 两次调用不如一次 Pop —— 因为在并发场景下，两次调用之间状态可能被其他线程改变。能用一次调用完成的，就别拆成两次。

5.1.5

方案：用两个栈 —— 主栈 + "最小值栈"。

public class MinStack<T> where T : IComparable<T>
{
    private readonly Stack<T> _main = new();
    private readonly Stack<T> _mins = new();     // 辅助栈，栈顶始终是当前最小值

    public void Push(T value)
    {
        _main.Push(value);

        // 关键：只有当新值 <= 当前最小值时才压入辅助栈
        //（用 <= 而不是 <，是为了正确处理重复的最小值）
        if (_mins.Count == 0 || value.CompareTo(_mins.Peek()) <= 0)
            _mins.Push(value);
    }

    public T Pop()
    {
        T value = _main.Pop();
        // 如果弹出的是当前最小值，辅助栈也要跟着弹
        if (value.CompareTo(_mins.Peek()) == 0)
            _mins.Pop();
        return value;
    }

    public T Peek() => _main.Peek();

    public T GetMin() => _mins.Peek();      // O(1)！
}

推演（依次压入 5, 3, 7, 2）：

两个设计要点：

1. 用 <= 而不是 <。 如果压入重复的最小值（比如已有 2，再压入 2），用 < 就只记录一次，弹出时会把辅助栈的 2 弹掉，导致后续 GetMin() 返回错误的值。
2. 辅助栈只在"新值 ≤ 当前最小值"时才压入。 这样辅助栈的空间开销在最坏情况下是 $O(n)$（比如递减序列），但平均情况下远小于 $n$。

复杂度：所有操作都是 $O(1)$，额外空间 $O(n)$ 最坏、通常远小于 $n$。

这个题的价值在于：它展示了"用额外的空间记录额外信息"这个通用套路。同样的思路可以用在"$O(1)$ 求栈中最大值"、"$O(1)$ 求队列最大值"（后者的答案是单调队列，见 5.4 节）。

八、常见错误

九、本节总结

1. 栈是 LIFO：只能操作栈顶，Push / Pop / Peek 都是 $O(1)$。
2. 栈的本质是"受限"：不能访问中间元素，换来的是简单、快速、不易用错。
3. 调用栈就是栈 —— 2.2 节讲的函数调用机制，正是"栈"这个名字的由来。
4. Pop() 必须清引用（_items[_count] = default!;）。实测：不清 → 对象无法回收（True），清了 → 正常回收（False）。这是最容易忽略也最容易在线上造成内存增长的一个细节。
5. 数组是栈的标准实现：所有操作都在尾部，正好是数组最擅长的位置。100 万次 push+pop 实测 13.8 ms。
6. "用额外空间记录额外信息"是个通用套路：比如用辅助栈实现 $O(1)$ 的 GetMin()。

下一节衔接：栈是"后进先出"。但很多场景需要的是相反的规则 —— 先来的先处理：打印队列、消息队列、任务调度、BFS 遍历。这就是队列。而队列有一个比栈更棘手的问题：它在两端操作，怎么用数组高效实现？ 下一节讲环形缓冲区。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "5.1",
  "title": "栈：后进先出",
  "covered": [
    "栈的 LIFO 特性与四个生活场景（含与调用栈的呼应）",
    "三个核心操作及复杂度",
    "基于数组的 MyStack<T> 完整实现",
    "撤销功能的栈实现（快照法）",
    "弹出元素后清引用的必要性（WeakReference 实测 True/False 对比）",
    "内存泄漏测试方法本身的陷阱（局部变量栈槽 + NoInlining 隔离）",
    "数组栈性能实测（100 万次 push+pop = 13.8ms）",
    "用辅助栈实现 O(1) 的 GetMin（含 <= 的必要性）"
  ],
  "unresolved": [
    "括号匹配与表达式求值留到 5.3",
    "队列与环形缓冲区留到 5.2",
    "单调栈留到 5.4"
  ],
  "canonical_terms": {
    "栈": "后进先出（LIFO）的受限线性结构，只能操作栈顶",
    "后进先出（LIFO）": "最后进入的元素最先被取出",
    "压栈": "把元素放到栈顶",
    "弹栈": "取出并移除栈顶元素",
    "栈顶": "栈中唯一可直接访问的位置"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 3.2 的动态数组扩容",
    "读者理解 C# 的 GC 与 WeakReference 基本概念"
  ],
  "word_count_actual": 2340,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch05/Sec51/",
    "内存实验实测 LeakyStack=True / MyStack=False，与实现分析一致",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版内存实验把对象创建写在顶级语句作用域内，导致两个实现都返回 True（局部变量栈槽未释放的假象）；已改为独立方法 + NoInlining 隔离后重测"
  ],
  "next": "5.2 队列与双端队列：先进先出"
}