5.2　队列与双端队列：先进先出

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

• 说清队列的 FIFO 特性与核心操作；
• 解释为什么不能拿 List<T> 当队列用；
• 实现并理解环形缓冲区 —— 这是队列在工程上的标准解法；
• 说清双端队列（Deque）相对队列多出来的能力。

先修：5.1（栈）、3.1（数组的随机访问）。 固定术语：队列、先进先出（FIFO）、入队、出队、环形缓冲区、双端队列。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：排队

食堂打饭的队伍：

• 新来的人排在队尾
• 打饭的人从队首离开

先进来的先打到饭。这就是先进先出（FIFO，First In First Out）。

队列和栈的区别只有一条：从哪一端出去。

这一条区别，决定了它们的应用场景完全不同：

注意 BFS 那一条：第 12 章讲图的广度优先搜索时，队列是它的核心。届时你会发现，正是"先进先出"保证了"一层一层向外扩散"的顺序。

二、形式化：两个核心操作

和栈的对比：

栈:      Push →  [ A, B, C ]  ← Pop        （同一端）
队列:  Dequeue ←  [ A, B, C ]  ← Enqueue   （两端）

三、核心问题：为什么不能用 List<T> 当队列？

这是本节最重要的问题。第一反应可能是：

var queue = new List<int>();
queue.Add(x);            // 入队：加到末尾，O(1)
queue.RemoveAt(0);       // 出队：删掉第一个，O(n) ！

问题就出在 RemoveAt(0)。

回顾 3.1 节的结论：在数组头部删除元素，必须把后面所有元素往前挪一格。

出队前:  [ A, B, C, D, E, _, _, _ ]
出队后:  [ B, C, D, E, _, _, _, _ ]
           ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
           这四个元素全部被搬动了！

是的 —— 队列的出队操作，在数组上天然就是 $O(n)$。

这意味着什么？ 如果连续入队出队 $n$ 次，总代价是：

$$1 + 2 + 3 + \cdots + n = \frac{n(n-1)}{2} = O(n^2)$$

用 List<T> 当队列，整体会退化成 $O(n^2)$。

四、环形缓冲区：队列的标准解法

核心洞察：出队时，为什么要把元素往前搬？

我们之所以要搬，是为了让"队首永远在数组下标 0 的位置"。但这是一个我们自己强加的约束，解题不需要它。

换个思路：不搬元素，只移动队首的位置。

初始:      [ A, B, C, _, _, _, _, _ ]
             ↑head=0, count=3

出队 A:    [ _, B, C, _, _, _, _, _ ]
                ↑head=1, count=2      ← 元素一个没动，只是 head 往后挪了

入队 D:    [ _, B, C, D, _, _, _, _ ]
                ↑head=1, count=3

入队 E:    [ _, B, C, D, E, _, _, _ ]
                ↑head=1, count=4

问题来了：这样一直加下去，head 会走到数组末尾，但前面明明还有空位（下标 0 那个位置空着）。怎么办？

答案：把数组看成"环形的" —— 走到末尾就绕回开头。

继续入队 F、G、H:
    [ H, B, C, D, E, F, G, _ ]
      ↑                    ↑
   head=1            新元素绕回了前面

再入队 I:
    [ H, B, C, D, E, F, G, I ]
      ↑head=1, count=8   ← 满了，此时才需要扩容

这就是环形缓冲区（Circular Buffer / Ring Buffer）。

实现的关键是取模运算：

// 队尾下标 = 队首下标 + 元素个数，超出容量就绕回去
private int TailIndex => (_head + _count) % _items.Length;

就这么一个 %，把"搬移 $n$ 个元素"变成了"移动一个下标"。

五、完整实现与实测

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

using System.Diagnostics;

// ==================== 实验一：环形缓冲区的内部状态 ====================

Console.WriteLine("=== 实验一：环形缓冲区的内部状态 ===");
Console.WriteLine();

var q = new MyQueue<string>(4);
Console.WriteLine($"  新建队列（容量 4）: {q.DebugInfo()}");
Console.WriteLine();

foreach (var v in new[] { "A", "B", "C" })
{
    q.Enqueue(v);
    Console.WriteLine($"  Enqueue({v}) -> {q.DebugInfo()}");
}
Console.WriteLine();

foreach (var _ in new[] { 1, 2 })
{
    string v = q.Dequeue();
    Console.WriteLine($"  Dequeue() 得到 {v} -> {q.DebugInfo()}");
}
Console.WriteLine();

Console.WriteLine("  注意看 head 的位置：出队时 head 只是往后挪，没有任何元素被搬动。");
Console.WriteLine();

// 再入队几个，观察「绕回去」
foreach (var v in new[] { "D", "E", "F" })
{
    q.Enqueue(v);
    Console.WriteLine($"  Enqueue({v}) -> {q.DebugInfo()}");
}
Console.WriteLine();

Console.WriteLine("  看 Enqueue(E) 那一行：E 被放到了下标 0，也就是数组的最前面 —— 队尾绕回去了。");
Console.WriteLine("  这就是「环形」：数组前面的空位（出队时腾出来的）被重新利用，不会浪费。");
Console.WriteLine("  如果是 List.RemoveAt(0)，前面那块空间就白白空着了，还得靠搬移元素来「补位」。");
Console.WriteLine();

// ==================== 实验二：为什么不能用 List 当队列 ====================

Console.WriteLine("=== 实验二：三种「队列」实现的性能对比 ===");
Console.WriteLine();

const int N = 100_000;
var sw = new Stopwatch();

// ---------- 错误做法：List.Add + List.RemoveAt(0) ----------
sw.Restart();
var listQueue = new List<int>();
for (int i = 0; i < N; i++) listQueue.Add(i);
while (listQueue.Count > 0) listQueue.RemoveAt(0);
sw.Stop();
double listMs = sw.Elapsed.TotalMilliseconds;

// ---------- 我们的环形缓冲区 ----------
sw.Restart();
var myQueue = new MyQueue<int>();
for (int i = 0; i < N; i++) myQueue.Enqueue(i);
long sum1 = 0;
while (!myQueue.IsEmpty) sum1 += myQueue.Dequeue();
sw.Stop();
double mineMs = sw.Elapsed.TotalMilliseconds;

// ---------- C# 内置 Queue<T> ----------
sw.Restart();
var dotnetQueue = new Queue<int>();
for (int i = 0; i < N; i++) dotnetQueue.Enqueue(i);
long sum2 = 0;
while (dotnetQueue.Count > 0) sum2 += dotnetQueue.Dequeue();
sw.Stop();
double dotnetMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  入队 + 出队各 {N:N0} 次：");
Console.WriteLine();
Console.WriteLine($"  List.Add + List.RemoveAt(0) : {listMs,9:F2} ms   出队 O(n)，整体 O(n^2)");
Console.WriteLine($"  环形缓冲区（我们自己实现）  : {mineMs,9:F2} ms   出入队都是 O(1)");
Console.WriteLine($"  C# 内置 Queue<T>            : {dotnetMs,9:F2} ms   出入队都是 O(1)");
Console.WriteLine();
Console.WriteLine($"  List 做法慢了 {listMs / mineMs:F0} 倍。");
Console.WriteLine($"  校验和一致: {sum1 == sum2}（{sum1:N0}）");
Console.WriteLine();

// 放大规模看差距怎么变
Console.WriteLine("  规模放大后的差距：");
Console.WriteLine($"  {"数据量",12} | {"List.RemoveAt(0)",18} | {"环形缓冲区",14} | {"倍数",8}");
foreach (int n in new[] { 25_000, 50_000, 100_000 })
{
    sw.Restart();
    var lq = new List<int>();
    for (int i = 0; i < n; i++) lq.Add(i);
    while (lq.Count > 0) lq.RemoveAt(0);
    sw.Stop();
    double lms = sw.Elapsed.TotalMilliseconds;

    sw.Restart();
    var mq = new MyQueue<int>();
    for (int i = 0; i < n; i++) mq.Enqueue(i);
    while (!mq.IsEmpty) mq.Dequeue();
    sw.Stop();
    double mms = sw.Elapsed.TotalMilliseconds;

    Console.WriteLine($"  {n,12:N0} | {lms,15:F2} ms | {mms,11:F2} ms | {lms / mms,7:F0} 倍");
}
Console.WriteLine();
Console.WriteLine("  数据量涨 4 倍，List 做法的耗时涨约 16 倍 —— 典型的 O(n^2)。");
Console.WriteLine("  环形缓冲区始终是线性的。");
Console.WriteLine();

// ==================== 实验三：双端队列 ====================

Console.WriteLine("=== 实验三：双端队列（Deque）===");
Console.WriteLine();

var deque = new MyDeque<string>(4);
deque.PushBack("B");
deque.PushBack("C");
deque.PushFront("A");           // 从前面插入
deque.PushBack("D");
Console.WriteLine($"  依次 PushBack(B/C/D)、PushFront(A) 后: {deque}");

Console.WriteLine($"  PopFront() = {deque.PopFront()}   剩余: {deque}");
Console.WriteLine($"  PopBack()  = {deque.PopBack()}   剩余: {deque}");
Console.WriteLine();
Console.WriteLine("  双端队列 = 栈 + 队列。两端都能 O(1) 进出。");
Console.WriteLine("  C# 没有内置的 Deque，需要时可以用 LinkedList<T>，或者自己写一个（就像上面这样）。");
Console.WriteLine();

// ==================== 队列的实现 ====================

/// <summary>
/// 基于「环形缓冲区」的队列。
/// 关键：出队时不搬移任何元素，只移动 head 下标，绕回数组开头继续用。
/// </summary>
public class MyQueue<T>
{
    private T[] _items;
    private int _head;      // 队首元素所在的下标
    private int _count;     // 元素个数

    public MyQueue(int capacity = 4)
    {
        _items = new T[Math.Max(capacity, 1)];
    }

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

    // 队尾的下标 = 队首 + 元素个数，超出容量就绕回去
    private int TailIndex => (_head + _count) % _items.Length;

    public void Enqueue(T item)
    {
        if (_count == _items.Length) Grow();
        _items[TailIndex] = item;
        _count++;
    }

    public T Dequeue()
    {
        if (_count == 0)
            throw new InvalidOperationException("队列为空，无法 Dequeue");

        T item = _items[_head];
        _items[_head] = default!;                       // 清引用，避免隐形内存泄漏
        _head = (_head + 1) % _items.Length;            // head 前移，不搬任何元素
        _count--;
        return item;
    }

    public T Peek()
    {
        if (_count == 0) throw new InvalidOperationException("队列为空");
        return _items[_head];
    }

    private void Grow()
    {
        var bigger = new T[_items.Length * 2];
        // 扩容时把环形「拉直」：按出队顺序依次复制到新数组的开头
        for (int i = 0; i < _count; i++)
            bigger[i] = _items[(_head + i) % _items.Length];
        _items = bigger;
        _head = 0;
    }

    /// <summary>把底层数组原样打印出来，好看清「环形」到底是怎么绕的。</summary>
    public string DebugInfo()
    {
        var slots = new string[_items.Length];
        for (int i = 0; i < _items.Length; i++)
            slots[i] = _items[i]?.ToString() ?? "_";
        return $"底层数组[{string.Join(",", slots)}]  head={_head}  ->  队列: [{ToString()}]";
    }

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

/// <summary>双端队列：两端都能 O(1) 插入和删除。</summary>
public class MyDeque<T>
{
    private T[] _items;
    private int _head;
    private int _count;

    public MyDeque(int capacity = 4)
    {
        _items = new T[Math.Max(capacity, 1)];
    }

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

    public void PushBack(T item)
    {
        if (_count == _items.Length) Grow();
        _items[(_head + _count) % _items.Length] = item;
        _count++;
    }

    public void PushFront(T item)
    {
        if (_count == _items.Length) Grow();
        _head = (_head - 1 + _items.Length) % _items.Length;   // 往前挪一格（绕回）
        _items[_head] = item;
        _count++;
    }

    public T PopFront()
    {
        if (_count == 0) throw new InvalidOperationException("双端队列为空");
        T item = _items[_head];
        _items[_head] = default!;
        _head = (_head + 1) % _items.Length;
        _count--;
        return item;
    }

    public T PopBack()
    {
        if (_count == 0) throw new InvalidOperationException("双端队列为空");
        int tail = (_head + _count - 1) % _items.Length;
        T item = _items[tail];
        _items[tail] = default!;
        _count--;
        return item;
    }

    private void Grow()
    {
        var bigger = new T[_items.Length * 2];
        for (int i = 0; i < _count; i++)
            bigger[i] = _items[(_head + i) % _items.Length];
        _items = bigger;
        _head = 0;
    }

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

实测输出（.NET 8 Release）：

=== 实验一：环形缓冲区的内部状态 ===

  新建队列（容量 4）: 底层数组[_,_,_,_]  head=0  ->  队列: []

  Enqueue(A) -> 底层数组[A,_,_,_]  head=0  ->  队列: [A]
  Enqueue(B) -> 底层数组[A,B,_,_]  head=0  ->  队列: [A, B]
  Enqueue(C) -> 底层数组[A,B,C,_]  head=0  ->  队列: [A, B, C]

  Dequeue() 得到 A -> 底层数组[_,B,C,_]  head=1  ->  队列: [B, C]
  Dequeue() 得到 B -> 底层数组[_,_,C,_]  head=2  ->  队列: [C]

  注意看 head 的位置：出队时 head 只是往后挪，没有任何元素被搬动。

  Enqueue(D) -> 底层数组[_,_,C,D]  head=2  ->  队列: [C, D]
  Enqueue(E) -> 底层数组[E,_,C,D]  head=2  ->  队列: [C, D, E]
  Enqueue(F) -> 底层数组[E,F,C,D]  head=2  ->  队列: [C, D, E, F]

=== 实验二：三种「队列」实现的性能对比 ===

  入队 + 出队各 100,000 次：

  List.Add + List.RemoveAt(0) :    111.37 ms   出队 O(n)，整体 O(n^2)
  环形缓冲区（我们自己实现）  :      1.60 ms   出入队都是 O(1)
  C# 内置 Queue<T>            :      1.29 ms   出入队都是 O(1)

  List 做法慢了 70 倍。
  校验和一致: True（4,999,950,000）

  规模放大后的差距：
           数据量 |   List.RemoveAt(0) |          环形缓冲区 |       倍数
        25,000 |            6.23 ms |        0.29 ms |      22 倍
        50,000 |           26.72 ms |        0.49 ms |      54 倍
       100,000 |          108.76 ms |        0.99 ms |     110 倍

  数据量涨 4 倍，List 做法的耗时涨约 16 倍 —— 典型的 O(n^2)。
  环形缓冲区始终是线性的。

=== 实验三：双端队列（Deque）===

  依次 PushBack(B/C/D)、PushFront(A) 后: [A, B, C, D]
  PopFront() = A   剩余: [B, C, D]
  PopBack()  = D   剩余: [B, C]

六、读实验一：把"环形"看明白

这张输出值得逐行读一遍，因为它把环形缓冲区的内部机制完全暴露出来了：

两个关键观察：

1. 出队时数据一个都没动。 head 从 0 挪到 2，B 和 C 还在原来的位置上。这就是 $O(n) \to O(1)$ 的来源。

2. Enqueue(E) 时下标"绕回去"了。 E 被放到了下标 0 —— 那个位置本来是 A 的，A 出队后空出来了，现在被循环利用。

环形缓冲区的名字就是这么来的：数组在逻辑上首尾相连，成了一个环。下标从 capacity - 1 再加 1 就回到 0（靠 % 运算实现）。

扩容时为什么要"拉直"？

private void Grow()
{
    var bigger = new T[_items.Length * 2];
    for (int i = 0; i < _count; i++)
        bigger[i] = _items[(_head + i) % _items.Length];   // 按出队顺序依次复制
    _items = bigger;
    _head = 0;                                              // 拉直后 head 归零
}

扩容时不能简单地 Array.Copy，因为元素在数组里可能是"断成两截"的（比如 [E,F,_,_,C,D]）。必须按逻辑顺序（从 head 开始绕一圈）依次复制到新数组的开头，这样新数组就是"拉直"的，head 也回到 0。

七、读实验二：$O(n^2)$ 是怎么来的

看 List 那一列的增长：

• 数据量涨 2 倍（25k → 50k），耗时涨 4.3 倍
• 数据量涨 4 倍（25k → 100k），耗时涨 17.5 倍

接近平方增长 —— 这正是 $O(n^2)$ 的特征。而环形缓冲区那一列：

• 数据量涨 4 倍，耗时涨 3.4 倍（接近线性的 4 倍）

两者的差距随规模持续拉大（22 → 54 → 110 倍）。如果数据量到 1000 万，差距会是几千倍。

这是一条很实用的工程排查经验：

如果你在生产代码里看到 List.RemoveAt(0)、List.Insert(0, ...)，或者 queue.RemoveAt(0) 这样的写法，基本可以确定是一个性能 bug。

正确的替代是：Queue<T>（队列语义）、LinkedList<T>（需要在两端增删）、或者环形缓冲区。

.NET 还有一个专门的 System.Collections.Generic.PriorityQueue<TElement, TPriority>（.NET 6+），以及 ConcurrentQueue<T>（并发场景）。

关于 Queue<T>（1.29 ms）和我们自己实现的版本（1.60 ms）：

差了约 24%。这个差距来自官方实现的一些细节优化（比如它内部用了一个 _tail 字段而不是每次算 %，以及数组扩容时的处理）。但数量级完全一致 —— 说明我们自己实现的环形缓冲区思路是对的。

八、双端队列：两端都能进出

双端队列（Deque，Double-Ended Queue）：两端都能 $O(1)$ 插入和删除。

双端队列是栈和队列的超集：你可以只用它的一端，把它当栈用；也可以一端进另一端出，把它当队列用。

实现的关键只有两行不同：

// 从前面插入：head 往前挪一格
_head = (_head - 1 + _items.Length) % _items.Length;   // 注意 +Length 防止负数

// 从后面删除：算出尾部的下标
int tail = (_head + _count - 1) % _items.Length;

注意 (_head - 1 + _items.Length) % _items.Length 里的 + _items.Length。

因为 C# 里 -1 % 4 的结果是 -1（不是 3），负数取模会得到负数。加上一个 Length 就能把结果拉回正数范围。这是环形缓冲区里最容易写错的一处。

双端队列用在哪？

• 滑动窗口最大值（5.4 节）—— 单调队列就是双端队列的应用
• 工作窃取调度器（work-stealing）：线程从自己队列的头部取任务，从别人的队列尾部"偷"任务
• 撤销/重做缓冲区：新操作从一端进，历史从另一端淘汰

C# 没有内置的 Deque。 需要时有两个选择：

• LinkedList<T>：现成，但内存开销大、缓存不友好
• 自己写一个（就像本节的 MyDeque<T>）：多写 40 行代码，换 8 倍的内存效率

这是少数几个"值得自己造轮子"的场景。

九、练习

练习 5.2.1（判断） 判断对错并说明理由： (a) 队列可以用 List<T> 实现，Add 入队、RemoveAt(0) 出队。 (b) 环形缓冲区的容量是固定的，用满就不能再加了。 (c) 环形缓冲区里，队首元素的下标永远是 0。

练习 5.2.2（推演） 一个容量为 5 的环形缓冲区，_head = 3，_count = 4。 (a) 队尾元素在哪个下标？ (b) 此时再 Enqueue 一个元素，它会放在哪个下标？ (c) 此时 Dequeue() 两次，head 变成多少？

练习 5.2.3（写代码） 用两个栈实现一个队列，要求 Enqueue 和 Dequeue 的摊还复杂度都是 $O(1)$。 （提示：一个栈负责入队，一个负责出队。想清楚什么时候把元素从第一个栈倒到第二个栈。）

练习 5.2.4（工程判断） 你的服务需要维护一个"最近 1000 条日志"的缓冲区，新日志不断产生，旧的自动淘汰。 (a) 用 List<T> + RemoveAt(0) 行不行？为什么？ (b) 用 Queue<T> 呢？ (c) 如果要求"随时能按时间倒序取出全部 1000 条"，你的方案要改吗？

练习 5.2.5（挑战·环形缓冲区的真实应用） 一个高频交易系统需要在内存里缓冲最近 100 万条行情数据，要求：

• 写入速度必须极快（不能有 GC 压力）
• 旧数据被新数据自动覆盖（不需要保留全部历史）
• 允许多个消费者线程按顺序读取

请设计这个结构。特别说明： (a) 为什么不能用 Queue<T>？ (b) 用环形缓冲区的话，"覆盖旧数据"怎么实现？ (c) 多线程读写需要注意什么？

十、练习答案

5.2.1

• (a) 功能上可以，性能上不行。 RemoveAt(0) 是 $O(n)$，连续 $n$ 次入队出队就是 $O(n^2)$。

  实测：10 万次入队出队，List 做法 111.37 ms，环形缓冲区 1.60 ms，慢 70 倍。而且规模越大差距越大。

• (b) 错。 环形缓冲区可以扩容，只是在"需要拷贝并拉直"这一点上比普通动态数组麻烦一些（见 Grow() 实现）。

  不过要说明：很多环形缓冲区的使用场景本来就是"容量固定"的（比如音频缓冲、日志环形缓冲），因为它们的设计意图就是"覆盖旧数据"而不是"无限增长"。这种固定容量的版本更简单、更没有 GC 压力。

• (c) 错。 head 是任意下标，会随着出队操作不断前移并绕回。

  这正是它与"用 List 当队列"的本质区别：List 做法强制队首在下标 0（所以要搬元素），环形缓冲区让队首可以"漂移"（所以不用搬）。

5.2.2

容量 = 5，_head = 3，_count = 4。

(a) 队尾下标 = (_head + _count - 1) % 5 = (3 + 4 - 1) % 5 = 6 % 5 = 1。

队尾在下标 1。

验证：元素分布在下标 3, 4, 0, 1（从 head 开始绕一圈，共 4 个）。下标 1 确实是最后一个 ✓

(b) 队尾的下一个空位 = (_head + _count) % 5 = (3 + 4) % 5 = 7 % 5 = 2。

新元素放在下标 2。

验证：此时占用的是 3, 4, 0, 1，空位是 2 ✓

(c) 两次出队后 _head 从 3 依次变成 4、0。

_head = 0，_count = 2。

这道题的价值：让你亲手算一遍 % 运算。环形缓冲区的所有 bug 几乎都出在取模算错或忘记加 +Length 上。

推荐的做法：不要心算，写一个小的"状态推演"（就像本节实验一那样打印底层数组），一眼就能看出对不对。

5.2.3

方案：两个栈 —— _inStack（负责入队）和 _outStack（负责出队）。

public class QueueWithTwoStacks<T>
{
    private readonly Stack<T> _inStack = new();
    private readonly Stack<T> _outStack = new();

    public void Enqueue(T item)
    {
        _inStack.Push(item);                    // 直接压入入栈，O(1)
    }

    public T Dequeue()
    {
        // 只有当出栈为空时，才把入栈的全部元素「倒」过来
        if (_outStack.Count == 0)
        {
            if (_inStack.Count == 0)
                throw new InvalidOperationException("队列为空");

            while (_inStack.Count > 0)
                _outStack.Push(_inStack.Pop());  // 倒过来后，顺序就正了
        }
        return _outStack.Pop();
    }

    public int Count => _inStack.Count + _outStack.Count;
}

为什么顺序是对的？

_inStack 里是 [A, B, C]（栈顶是 C）。把它们依次弹出并压入 _outStack：

• 弹出 C → 压入 _outStack，_outStack = [C]
• 弹出 B → 压入，_outStack = [C, B]
• 弹出 A → 压入，_outStack = [C, B, A]（栈顶是 A）

现在从 _outStack 弹出，得到的是 A, B, C —— 正好是入队顺序 ✓

为什么摊还是 $O(1)$？

单个 Dequeue 最坏是 $O(n)$（正好赶上倒栈）。但关键在于：每个元素在整个生命周期里，最多被"倒"一次。

• 入队：压入 _inStack 一次
• 转移：从 _inStack 弹出、压入 _outStack 各一次
• 出队：从 _outStack 弹出一次

总共每个元素被操作 4 次常数操作。所以 $n$ 次操作的总代价是 $O(n)$，摊还到每次是 $O(1)$。

这是摊还分析的一个经典案例 —— 和 3.2 节动态数组的"扩容搬运总量小于 $2n$"是同一类推理：某一次操作很贵，但那种贵操作总次数有限，摊下来就便宜了。

5.2.4

• (a) 不行。 RemoveAt(0) 是 $O(n)$。虽然 $n$ 只有 1000（挪 1000 个引用是微秒级），但：

  注意这里的判断：如果日志产生频率很低（比如每秒几条），用 List 完全可以接受 —— $O(n)$ 不代表慢，要看 $n$ 和调用频率。

  但如果每秒有几千条日志，那就是每秒几千次 $O(1000)$ 的搬移操作，累计起来就明显了。这时候该换结构。

• (b) Queue<T> 很合适。 入队 $O(1)$，出队 $O(1)$。当 Count > 1000 时 Dequeue() 一条即可。

  var logs = new Queue<LogEntry>();
  void Add(LogEntry log)
  {
      logs.Enqueue(log);
      if (logs.Count > 1000) logs.Dequeue();   // 淘汰最旧的
  }
  

  这是最简单、最不容易出错的方案，推荐使用。

• (c) 要改。 Queue<T> 只能从队首顺序访问（Peek），不支持"倒序取出全部"。 两个选择：

  1. 用 List<T> + 环形缓冲区：自己维护 head 和 count，倒序时按逆序下标读取。
  2. 用 LinkedList<T>：可以从尾部往前遍历（它是双向的）。
  3. 最简单：仍然用 Queue<T>，倒序时 logs.Reverse().ToList()（$O(n)$ 一次，可接受）。

  要问清楚需求："倒序取出"是每次读取都要，还是偶尔调用？

  • 偶尔调用 → 直接 Reverse() 就行，不用改结构。
  • 每秒调用几百次 → 才值得换成双端队列。

5.2.5

(a) 为什么不能用 Queue<T>？

Queue<T> 有两个问题：

1. 它会持续增长（或持续分配）。 虽然有 Dequeue() 可以淘汰旧数据，但每次 Enqueue/Dequeue 都可能触发内部的数组操作和边界检查，在高频写入下会产生 GC 压力和不可预测的延迟。
2. 它不是为"并发读写"设计的。 Queue<T> 不是线程安全的。ConcurrentQueue<T> 虽然是并发的，但它是无界的（会一直增长），且内部使用了复杂的无锁结构，写入延迟不如环形缓冲区稳定。

高频交易系统最怕的就是"不可预测的延迟" —— GC 停顿、锁竞争都会导致错过交易时机。

(b) 用环形缓冲区，怎么实现"覆盖旧数据"？

固定容量，写满就从头覆盖：

public class MarketDataRingBuffer
{
    private readonly MarketData[] _buffer;
    private long _writeIndex;         // 下一个要写的槽位（单调递增，不取模）

    public MarketDataRingBuffer(int capacity)
    {
        _buffer = new MarketData[capacity];
    }

    public void Write(in MarketData data)
    {
        // 写入时直接覆盖，不需要检查「满没满」
        _buffer[_writeIndex % _buffer.Length] = data;
        _writeIndex++;
    }

    public MarketData ReadAt(long sequence)
        => _buffer[sequence % _buffer.Length];
}

关键设计：

1. _writeIndex 用 long 且单调递增，不取模。 取模只在访问数组时做。这样做的两个好处：

   • 能判断"有没有被覆盖"：消费者记录自己的 sequence，如果 _writeIndex - sequence > capacity，说明这条数据已经被新数据覆盖了。
   • 避免 ++ 回绕：long 在可预见的未来不会溢出（每秒 100 万条也要 29 万年）。

2. 写入是纯粹的"赋值 + 自增"，没有任何分支判断 —— 这才是极致的低延迟。

3. 固定容量意味着零分配：数组在构造时就分配好，之后永远不再 new，所以没有 GC 压力。

(c) 多线程读写需要注意什么？

1. 写指针的可见性。 写线程更新 _writeIndex 后，读线程必须能及时看到。需要用 Volatile.Write / Volatile.Read（或 Interlocked）来保证内存屏障，防止 CPU 指令重排导致"读到新数据但看到旧下标"。

2. 避免伪共享（False Sharing）。 如果写指针和读指针在同一个缓存行（64 字节）里，两个线程分别修改它们会导致缓存行在两个核之间来回弹跳，性能急剧下降。解决方法是给指针加上填充（padding），让它们落在不同的缓存行上。

3. 单生产者单消费者（SPSC）最安全。 生产者和消费者各占一个线程、各管一个指针，不需要任何锁 —— 只需要内存屏障保证可见性。这是最高效的形态。

4. 多生产者需要 CAS。 如果有多个线程同时写，就必须用 Interlocked.CompareExchange 来原子地抢占写位置，成本会高不少。

这就是为什么 Disruptor（LMAX 交易所开源的高性能队列框架）能在单机上做到每秒处理 600 万笔订单 —— 它的核心就是这个环形缓冲区 + 无锁设计。

本节只是让你理解原理。真要在生产上用，请直接用成熟的库（比如 Disruptor 的 .NET 移植版），或者 System.Threading.Channels —— 自己写无锁代码极容易出错，而且 bug 往往只在特定 CPU 和负载下才复现。

十一、常见错误

十二、本节总结

1. 队列是 FIFO：队尾入、队首出。Enqueue / Dequeue 都是 $O(1)$。
2. 队列和栈的唯一区别是"从哪一端出去"，但这决定了它们完全不同的应用场景。
3. 绝对不要用 List<T> 当队列：RemoveAt(0) 是 $O(n)$，整体退化成 $O(n^2)$。实测 10 万次慢 70 倍。
4. 环形缓冲区是队列的标准解法：不搬元素，只移动 head 下标；下标超出容量就用 % 绕回开头。
5. 实测对比：List 做法 111.37 ms、环形缓冲区 1.60 ms、官方 Queue<T> 1.29 ms。我们自己实现的版本和官方只差 24%，数量级完全一致。
6. 双端队列两端都能 $O(1)$ 进出，是栈和队列的超集。实现上只比队列多两行（注意负数取模要 + length）。
7. 固定容量的环形缓冲区是低延迟系统的基石：零分配、无 GC 压力、可无锁。Disruptor 就是靠它做到每秒 600 万笔订单的。

下一节衔接：栈和队列本身很简单。但它们真正的威力在于解决特定类型的问题 —— 比如"括号是否匹配"、"表达式怎么求值"、"下一个更大的元素是谁"。下一节我们用栈实现一个完整的四则运算计算器，你会看到运算符优先级和括号是如何被栈优雅地处理的。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "5.2",
  "title": "队列与双端队列：先进先出",
  "covered": [
    "队列的 FIFO 特性与与栈的唯一区别",
    "List.RemoveAt(0) 导致 O(n^2) 的完整论证",
    "环形缓冲区的原理与底层数组状态逐行演示",
    "MyQueue<T> 完整实现（含扩容时「拉直」）",
    "三种实现的性能对比（111.37ms / 1.60ms / 1.29ms）与规模放大趋势",
    "双端队列 MyDeque<T> 实现与负数取模陷阱",
    "环形缓冲区在低延迟系统中的应用（Disruptor/SPSC/伪共享）",
    "两个栈实现队列与摊还分析"
  ],
  "unresolved": [
    "单调队列留到 5.4",
    "BFS 用队列留到第 12 章",
    "ConcurrentQueue/Channels 属于并发编程，本书不展开"
  ],
  "canonical_terms": {
    "队列": "先进先出（FIFO）的受限线性结构，队尾入队首出",
    "先进先出（FIFO）": "最先进入的元素最先被取出",
    "入队": "把元素放到队尾",
    "出队": "取出并移除队首元素",
    "环形缓冲区": "用取模让下标绕回开头的固定数组，出队不搬移元素",
    "双端队列": "两端都能 O(1) 插入删除的队列"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 5.1 的栈与 3.1 的数组随机访问",
    "读者理解取模运算与 C# 中负数取模的行为"
  ],
  "word_count_actual": 3120,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch05/Sec52/",
    "实测数据逐项核对：111.37/1.60/1.29 ms；规模放大 22/54/110 倍；环形缓冲区状态逐步验证",
    "练习 5.2.2 的取模推演已手工验算（队尾下标 1、新元素下标 2、head 变 0）",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版 DebugInfo 只打印 head 和 count，看不出「绕回」，且注释误写成「到 F 时绕回」（实际按 (_head+_count)%4 计算，绕回发生在 E）；已改为打印底层数组并修正注释"
  ],
  "next": "5.3 应用：括号匹配与表达式求值"
}