1. 项目背景与测试目标：为什么我要对比两种动态数组实现的队列

先说明一下这个测试的来由。最近在做一个C#上位机项目，内部模块之间要传递高频数据流，最开始图省事直接用了Queue<T>，结果在数据量上来之后，GC压力明显变大，CPU占用也忽高忽低。于是我开始琢磨：能不能用动态数组（List<T>）自己封装一个队列来替代默认实现？网上搜了一圈，有人说List<T>做队列性能更好，有人说Queue<T>内部本身就是数组，没必要折腾。吵归吵，没人给出严谨的实测数据。

这个标题其实就是我当时踩坑后的一个验证项目：用C#分别基于List<T>和Queue<T>实现两种队列，跑一轮压测，用数据说话。同时，这也是一次典型的数据结构选型实验，正好把算法与数据结构里的“队列”这个概念，从教科书搬到了真实业务场景里。

这个测试适合谁？想搞清楚C#集合类型底层原理的人、正在做高性能服务或上位机开发的人、以及准备面试时被问到“Queue 和List 谁更适合做队列”这类问题的人。我尽量把整个实验思路、代码实现、测试方法、结果数据都摊开讲，你完全可以照着跑一遍。

先说结论，免得你看到最后才松一口气：在绝大多数场景下，直接使用Queue<T>是正确的选择，但List<T>版本并非一无是处，在特定内存分配模式下有它的价值。具体数据和分析见下文。

2. 两种动态数组实现队列的设计思路拆解

2.1 教科书里的队列 vs C#里的Queue

队列这个数据结构，核心规则就八个字：先进先出，后进后出。就像餐厅排队取餐，先来的先取，后来的排队等着。队列有两个基本操作：入队（Enqueue）和出队（Dequeue）。在算法与数据结构的教材里，队列通常有两种实现方式：一种是基于数组（顺序存储），一种是基于链表（链式存储）。

C# 的Queue<T>在底层采用的是**循环缓冲区（Circular Buffer）**方案，本质上就是一个动态数组加上头尾两个指针。当尾部指针到达数组末尾时，如果头部还有空位，新元素会从头部的空闲位置写入，而不是立即扩容。这样做的好处是：出队操作不需要移动元素，时间复杂度是 O(1)，入队操作在不需要扩容时也是 O(1)。

而List<T>是C#里最常用的动态数组，它内部维护一个T[]数组，当元素数量超过容量时会自动扩容到原来的两倍。用List<T>实现队列，最简单的思路是：

• 入队：list.Add(item)，直接在末尾追加；
• 出队：list[0]取出第一个元素，然后list.RemoveAt(0)。

这个方案在逻辑上完全正确，但问题恰恰出在RemoveAt(0)上。List<T>的RemoveAt在移除中间或头部元素时，需要把后续所有元素往前移动一位，这是一个 O(n) 的操作。每出队一个元素，后面的所有元素都要搬家，数据量大时这个成本会非常恐怖。

2.2 List 队列的两种变体：直接删除 vs 标记清理

既然RemoveAt(0)性能差，那有没有优化空间？我设计了两种List<T>队列变体：

变体A：直接删除型。就是上面说的RemoveAt(0)方案，逻辑最简单，代码最直观，但性能大概率最差。

变体B：标记清理型。维护一个headIndex变量记录队列头部的位置。入队时list.Add(item)，出队时返回list[headIndex]并让headIndex++，不物理删除元素。当headIndex达到一定阈值（比如等于list.Count，或者超过某个比例）时，再一次性清理已出队的元素：list.RemoveRange(0, headIndex)，重置headIndex = 0。

变体B的思路和Queue<T>的循环缓冲区非常接近，区别在于Queue<T>会复用前端空间，而变体B只是延迟清理。这种“懒删除”策略在很多场景下都能显著降低出队成本，但也带来了一个隐患：在两次清理之间，数组里残留大量已出队的“废元素”，内存占用会比实际队列长度高。

2.3 为什么不用链表实现来对比

有人可能会问：标题里只说了动态数组，为什么不用LinkedList<T>做第三组对照？我确实考虑了，但最终放弃了。原因有两个：

第一，LinkedList<T>的每个节点都有自己的开销（Next、Previous、Value 三个引用，加上对象头），在缓存局部性上天然劣势明显。数组是连续内存，CPU 缓存友好度极高，而链表节点分散在堆上，每次遍历都可能触发缓存未命中。

第二，题目限定的是“动态数组”，LinkedList<T>属于链式存储，不在讨论范围内。而且我之前单独测过LinkedList<T>队列，在小数据量下没什么优势，大数据量下被Queue<T>甩开一大截，这个结论在很多博客里也反复出现过。

3. C#代码实现：两个版本队列的完整写法

3.1 环境与工具准备

测试环境如下，你可以参考，但不用完全一致：

• 操作系统：Windows 11 Pro 22H2，64位
• 开发工具：Visual Studio 2022 17.8
• 框架版本：.NET 8.0（也兼容 .NET 6/7）
• 测试方式：控制台程序 + BenchmarkDotNet 做微基准
• 硬件：Intel i5-12400F，16GB DDR4 3200MHz

提示：如果你只是临时验证，用Stopwatch手写计时也可以，但在 .NET 平台上做严谨的性能对比，强烈建议使用 BenchmarkDotNet。它能自动处理预热、迭代次数、内存统计、避免 JIT 优化干扰等问题，测出来的数据才真的可信。

3.2 ListQueue：基于List 的直接删除实现

先看最简单的一版实现：

public class ListQueue<T> { private readonly List<T> _list = new(); public int Count => _list.Count; public void Enqueue(T item) { _list.Add(item); } public T Dequeue() { if (_list.Count == 0) throw new InvalidOperationException("队列为空"); T item = _list[0]; _list.RemoveAt(0); return item; } public T Peek() { if (_list.Count == 0) throw new InvalidOperationException("队列为空"); return _list[0]; } }

这段代码的逻辑没有任何问题，能正确实现先进先出。但正如前面所说，RemoveAt(0)会让所有后续元素整体前移。假设队列中有10万个元素，每出队一个元素，就要移动99999个引用。连续出队10万个元素，总移动次数约为 10万 × 10万 / 2 = 50亿次引用移动。这个数字看着都头皮发麻。

3.3 HeadIndexListQueue：基于List 的标记清理实现

再来看优化版：

public class HeadIndexListQueue<T> { private readonly List<T> _list = new(); private int _headIndex; public int Count => _list.Count - _headIndex; public void Enqueue(T item) { _list.Add(item); } public T Dequeue() { if (Count == 0) throw new InvalidOperationException("队列为空"); T item = _list[_headIndex]; _headIndex++; // 当头部索引过大时，触发清理 // 阈值设为容量的一半，减少频繁扩容和内存浪费 if (_headIndex >= _list.Count / 2 && _headIndex > 1024) { CleanUp(); } return item; } private void CleanUp() { if (_headIndex == 0) return; _list.RemoveRange(0, _headIndex); _headIndex = 0; } }

这个设计里有一个细微但很关键的点：清理阈值不能设成_headIndex == _list.Count，否则在大量入队出队交替的场景下，数组始终不会收缩，已经出队的元素一直占着内存，越积越多。设成“超过容量一半”是一个折中方案：既不会频繁触发RemoveRange，又能把浪费的内存控制在一个合理的比例内。

RemoveRange(0, _headIndex)这个操作本身也是 O(n) 的，但它不是每次出队都触发，而是积累到阈值才触发一次。摊还下来，单次出队的均摊复杂度接近 O(1)，这才是有意义的优化。

3.4 SystemQueue：直接用Queue 的对照组

对照组就没必要自己实现了，直接上官方类：

public class SystemQueue<T> { private readonly Queue<T> _queue = new(); public int Count => _queue.Count; public void Enqueue(T item) { _queue.Enqueue(item); } public T Dequeue() { return _queue.Dequeue(); } public T Peek() { return _queue.Peek(); } }

这里多套一层类不是为了装饰，而是为了让三个版本的调用方式保持一致，避免 BenchmarkDotNet 在测量时因为调用路径不同产生额外误差。用接口或基类统一约束一下会更好，我这里直接用了最简单的方式。

4. 压测方案与测试过程实录

4.1 测试场景设计：先入队后出队 vs 交错操作

队列在实际业务里很少出现“一次性塞入海量数据，再一次性全部取出”的情况，更多是边入队边出队。所以我设计了两组测试场景：

场景一：先大量入队，再大量出队。模拟批量任务处理。先入队 N 个元素，然后连续出队 N 个元素。这个场景对HeadIndexListQueue最友好，因为它在入队阶段几乎零开销，出队阶段也只是移动索引。

场景二：入队和出队交替进行。每入队1个元素，就出队1个元素，队列长度始终保持在一个小范围波动。这个场景更加接近消息处理、任务调度的真实工作负载。对Queue<T>来说，循环缓冲区在这种模式下如鱼得水；对HeadIndexListQueue来说，则会不断触发清理逻辑。

每组测试分别跑 1万、10万、100万、1000万 四个量级。每个量级下 BenchmarkDotNet 自动跑多次迭代，最终取中位数。

4.2 完整测试代码：BenchmarkDotNet配置

下面是测试主体的完整代码：

using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Running; [MemoryDiagnoser] [Orderer(BenchmarkDotNet.Order.SummaryOrderPolicy.FastestToSlowest)] public class QueueBenchmark { private ListQueue<int> _listQueue = null!; private HeadIndexListQueue<int> _headIndexQueue = null!; private SystemQueue<int> _systemQueue = null!; [Params(10_000, 100_000, 1_000_000, 10_000_000)] public int N; [GlobalSetup] public void Setup() { _listQueue = new ListQueue<int>(); _headIndexQueue = new HeadIndexListQueue<int>(); _systemQueue = new SystemQueue<int>(); } [Benchmark] public void ListQueue_Enqueue_Dequeue() { for (int i = 0; i < N; i++) _listQueue.Enqueue(i); for (int i = 0; i < N; i++) _listQueue.Dequeue(); } [Benchmark] public void HeadIndexListQueue_Enqueue_Dequeue() { for (int i = 0; i < N; i++) _headIndexQueue.Enqueue(i); for (int i = 0; i < N; i++) _headIndexQueue.Dequeue(); } [Benchmark] public void SystemQueue_Enqueue_Dequeue() { for (int i = 0; i < N; i++) _systemQueue.Enqueue(i); for (int i = 0; i < N; i++) _systemQueue.Dequeue(); } } public class Program { public static void Main(string[] args) { BenchmarkRunner.Run<QueueBenchmark>(); } }

注意：[Params]里的 N 不能设太大，否则 BenchmarkDotNet 单次迭代的时间会非常长。我一开始把 1000万 的量级放进去，跑一次实验等了将近20分钟。如果你时间有限，可以先跑 1万、10万、100万 三组。

4.3 第一次跑的翻车现场：GC干扰

这里必须分享一个踩坑经历。第一版测试代码里，我在循环体内直接new Queue<int>()，结果每组测试的耗时波动极其夸张，同样量级的两轮测试，耗时差距能到3倍。排查了半天，终于意识到问题：大量队列对象的创建和销毁触发了 GC（垃圾回收），而 GC 的时机是不确定的，它把性能数据搅得一团糟。

后来我改成[GlobalSetup]里提前创建队列实例，每个 Benchmark 方法执行前只调用Clear()或者直接重新赋值，这才得到稳定的数据。这里也提醒你：做性能测试时，一定要把对象创建排除在计时范围之外，否则你测的根本不是算法本身，而是 GC 的表现。

5. 测试结果数据与性能差异分析

5.1 先入队后出队场景：ListQueue直接被秒杀

先看场景一的耗时数据（单位：毫秒，数值越小越好）：

看到这个数据，我相信你应该能理解为什么很多人说“RemoveAt(0)是反模式”了。在100万数据量下，ListQueue耗时超过了9秒，而Queue<T>只需要5.7毫秒，性能差距超过1600倍。这个差距完全来自RemoveAt(0)的 O(n) 元素搬移，数据量越大，单次搬移成本越高，总耗时呈二次方增长。

HeadIndexListQueue和SystemQueue的数据非常接近，1000万数据量下分别是66.2ms和61.38ms，差距约8%。这证明了延迟清理策略确实能把动态数组实现队列的均摊成本降到接近循环缓冲区的水平。Queue<T>略快一点，主要赢在它的循环复用机制，不需要像HeadIndexListQueue那样在某些节点做整块的RemoveRange搬移。

5.2 交错入队出队场景：差距缩小但格局不变

再看场景二（每入队1个就出队1个）的数据：

这个场景下，HeadIndexListQueue和SystemQueue的差距从8%拉大到了约2.2倍。原因在于：交替操作时，HeadIndexListQueue每次出队都会让_headIndex持续增长，很快触发CleanUp()，而CleanUp()的RemoveRange需要搬移剩余的所有元素。每次搬移的量虽然不大，但架不住频率高。

而Queue<T>的循环缓冲区完全不需要搬移，它的_head和_tail指针在数组内部循环推进，永远不需要把元素整体挪位置。这正是循环队列相对普通动态数组的先天优势。

5.3 内存分配对比：ListQueue意外“胜出”？

用 BenchmarkDotNet 的[MemoryDiagnoser]还可以看到内存分配情况：

• Queue<T>：100万元素规模下，大约分配 12 MB 内存
• HeadIndexListQueue：大约分配 12.8 MB
• ListQueue：大约分配 17 MB

ListQueue反而多出来的4~5MB，看起来有些反直觉。原因是它频繁RemoveAt(0)导致List<T>内部数组经常处于“前半部分空、后半部分满”的状态，触发扩容时，List<T>会把有效元素复制到新数组，但旧数组在GC还没来得及接管时，峰值内存会短暂上升。加上RemoveAt本身也要移动引用，虽然这不直接产生托管堆分配，但会间接影响 GC 对数组代龄的判断，让 GC 更频繁地把数组提升到第1代。

结论是：在纯内存分配量上，三者差距不大，真正的分水岭在 CPU 时间上。队列本身的存储成本主要取决于容量峰值，和入队出队的顺序关系不大。

6. 常见问题与避坑技巧实录

6.1 为什么我的测试数据和别人不一样

很多读者复现测试时会发现，自己的结果和某些博客公布的数据差距很大。这很正常，导致差异的因素太多了：CPU架构、内存频率、.NET版本、GC模式（工作站/服务器）、是否开启 Tiered PGO，甚至操作系统版本都会影响结果。

比如在 .NET Framework 4.8 上，Queue<T>的实现和 .NET 8 基本一致，但 JIT 优化能力差一个档次，数字细节自然会变。再比如把 GC 模式调成服务器模式，大对象堆的分配策略不同，HeadIndexListQueue的表现可能也会有一点变化。

所以你看性能对比时，重点看相对差距和变化趋势，而不是死记某个绝对数值。只要量级关系保持一致，实验就是可信的。

6.2 用List 实现队列的正确打开方式

虽然Queue<T>是首选，但HeadIndexListQueue这种“标记清理”思路并不是毫无用处。如果你需要频繁访问队列中间的元素（比如根据某个条件删除特定元素），Queue<T>完全做不到，而List<T>天然支持随机访问和按索引插入删除。这种“可随机访问的队列”在实际业务中确实存在，比如某些任务调度器要支持按优先级调整队列内部的任务位置。

反过来，如果你的场景只是简单的先进先出，别折腾，直接用Queue<T>。官方实现已经过无数次优化和测试，自己造轮子只会引入维护成本和潜在bug。我在生产项目里见过有人手写了一个“高性能队列”，结果因为headIndex越过数组边界没有复位，直接抛出越界异常，那天线上消息全部堵塞，教训极其深刻。

6.3 队列满员和扩容策略对性能的影响

Queue<T>和List<T>的默认扩容策略都是容量翻倍。这个策略有一个隐含的性能坑：当你知道队列规模的最大值，却没有提前调用TrimExcess()或者通过构造函数初始化容量，那么扩容会分多次发生，每次扩容都要把旧数组元素复制到新数组。

比如预期队列最多10万个元素，但你从默认容量0开始入队，List<T>的容量变化轨迹是 0→4→8→16→32→...→131072，总共扩容15次，累计复制的元素数量约为26万次。虽然均摊下来每次入队仍然是 O(1)，但多出的拷贝操作会体现在耗时上。

如果你预先知道容量上限，直接在构造函数里传入：

var queue = new Queue<int>(100_000);

或者：

var list = new List<int>(100_000);

这能让内存一次性分配到位，有效减少GC压力。我在项目里做消息缓冲时，就习惯性地给队列设置一个合理初始容量，实测能降低约15%的延迟抖动。

6.4 BenchmarkDotNet使用中的三个隐藏坑

第一个坑是没有[GlobalSetup]导致的污染，前面已经说过了。第二个坑是没有关闭 Hyper-V、核心隔离等虚拟化功能，在 Windows 上这些功能会引入额外的中断延迟，导致测试数据抖动。如果只是做相对对比，影响不大，但做绝对值参考时误差不可忽略。

第三个坑容易被忽视：[Benchmark]方法的命名会影响结果输出排序，但不会影响正确性。真正影响正确性的是 BenchmarkDotNet 的“*** 避免死代码消除 ***”机制，它会自动消费返回值或把结果写入 Volatile 字段。如果你自己用Stopwatch手写测试，记得把结果累加到一个静态字段或者用Console.WriteLine输出，否则编译器可能把整段循环优化掉——我见过有人测出“0毫秒”的离谱数据，就是这个原因。

6.5 其他动态数组实现队列方案的补充

除了上面三种实现，C#生态里还有其他基于数组的队列变体值得提一下。比如System.Collections.Concurrent.ConcurrentQueue<T>，它是线程安全的无锁队列，内部实现比较复杂，但在单线程下的性能其实不如普通Queue<T>，因为原子操作和内存屏障有额外开销。测过之后你会发现，在无并发需求的场景用ConcurrentQueue<T>反而更慢。

另外，System.Buffers.ArrayPool<T>配合循环计数器也能实现高性能队列，这套路适合对内存分配极其敏感的场景（比如热路径上的网络库开发）。它的思路是从池子里租用数组，用完归还，彻底避开 GC 压力。不过复杂度也上来了，需要你自己处理池的租借和归还时机，稍不留神就会造成内存泄漏。

7. 个人经验总结与后续扩展思路

跑完这一轮对比，我最深的感受是：数据结构选型，真的不能靠猜，也不能只看时间复杂度。RemoveAt(0)的 O(n) 复杂度摆在那里，差就是差，不会因为你把代码写得漂亮就变快；而Queue<T>的循环缓冲区设计，在连续出队场景下的优势是碾压级的。教科书里讲的“数组实现队列需要移动元素”这个知识点，很多人觉得抽象，但当我看到100万数据量下9秒钟对5.7毫秒的那一刻，我是真的记住了。

后面我还计划做两个延伸实验。一个是加入ConcurrentQueue<T>做并发场景的对照测试，另一个是用ArrayPool<T>自旋实现高性能队列，对比它在高并发下的表现。如果你对这个方向感兴趣，建议先从单线程的三种实现对比做起，把 BenchmarkDotNet 玩熟练了，再去碰并发和安全边界问题，那样踩坑的成本会低很多。