QueueTFIFO 的环形数组实现系列C# 与常用数据结构源码剖析 · 栈与队列篇阅读时间约 65 分钟源码基线.NET 8.0.0的dotnet/runtimeSystem.Private.CoreLib/src/System/Collections/Generic/Queue.cs版本说明本文用源码基线解释语义为突出不变量代码均是教学化摘录或伪代码不冒充逐字源码。其他 .NET 版本应按 tag 复核 API 与实现细节。一、队列真正解决的是什么队列提供先进先出FIFO语义先入队的元素先出队。若直接把有效元素放在数组的[0, Count)Enqueue很简单但每次Dequeue都要把剩余元素整体左移单次复杂度为 O(n)。连续清空 n 个元素便可能产生 O(n²) 的复制量。QueueT的关键不是“换一种数组”而是改变对数组下标的解释已经出队的前部空间不立即搬移头部索引向前走尾部到达数组末端后回到 0复用前部槽位。物理数组是线性的逻辑序列是环形映射出来的。环形数组带来三项收益正常入队、出队和查看队首都是 O(1)元素集中在一块数组中通常比逐节点分配更紧凑容量可以复用。代价是状态不再由一个长度完全描述所有操作必须共同维护头、尾、数量和版本不变量。本文关心的不只是方法怎么写还要回答队列满时为什么头尾可以相等扩容为什么需要两段复制删除后是否继续持有对象枚举为什么必须按逻辑顺序游戏主线程的事件队列为什么仍可能拖垮帧时间二、五个字段和一组不变量以.NET 8.0.0为基线理解实现所需的核心状态可抽象为// 教学化字段摘录不是完整源码。 private T[] _array; private int _head; // 下一个出队或查看的位置 private int _tail; // 下一个入队的位置 private int _size; // 逻辑元素数量 private int _version; // 结构修改版本用于枚举失效检测某些版本还含非泛型接口同步相关的状态它不改变环形算法。对容量C _array.Length非空缓冲区应满足0 _size C 0 _head C 0 _tail C 逻辑第 i 个元素位于 (_head i) mod C0 i _size空数组是特殊初始状态容量为 0此时不会计算模 0第一次入队先扩容。普通空队列通常把_head、_tail归到 0。2.1 head、tail 和 size 缺一不可只靠_head与_tail无法区分“空”和“满”容量 4空head 0, tail 0, size 0 容量 4满head 0, tail 0, size 4有些自制环形缓冲区会永久浪费一个槽位以head tail表示空QueueT保存_size因此可以使用全部容量。_tail不是“最后一个元素”而是下一次写入的位置。最后一个逻辑元素应通过头和数量推导。2.2 物理状态与逻辑顺序假设容量为 5依次入队 A、B、C、D出队 A、B再入队 E、F、G物理下标 0 1 2 3 4 物理内容 [F] [G] [C] [D] [E] ^ ^ tail2 head2 size5 逻辑顺序C, D, E, F, G此时head tail但队列是满的。任何把[0, size)当作有效区间的代码都会读错顺序。一个可靠的心智模型是_head是逻辑坐标系的原点数组下标只是其投影。三、边界推进语义是环绕实现不必做取模概念公式是(index 1) % capacity。但对每次只前进一步的场景.NET 8基线源码采用条件归零其意图可写成// 教学伪代码基线实现使用相同的边界思想。 static void MoveNext(ref int index, int length) { int next index 1; if (next length) next 0; index next; }所以“Queue 每次操作都多一次%因此必然慢某个比例”并不符合这个源码版本。即使另一实现使用取模也不能脱离 CPU、JIT/AOT、容量和工作负载给出神奇倍数。真正重要的是边界正确只有在容量大于 0 时推进且结果始终落在合法下标范围。若一次跨越多个位置例如计算逻辑第 i 个元素可使用取模也可先加后减容量。后者仅在已知和不超过某个范围时成立// 当 0 i size length 时加法结果小于 2 * length。 int physical head i; if (physical length) physical - length;自制实现若允许任意大步长或索引加法溢出必须采用相应的范围证明或更宽类型不能机械复制这个技巧。四、Enqueue先保证空间再提交状态入队的抽象步骤如下// 教学伪代码省略真实源码的常量和辅助方法细节。 public void Enqueue(T item) { if (_size _array.Length) Grow(requiredCapacity: _size 1); _array[_tail] item; MoveNext(ref _tail, _array.Length); _size; _version; }队列满时必须先扩容因为_tail正指向_head覆盖它会破坏最老元素。扩容策略通常按比例增长同时确保不少于所需容量并处理数组最大长度和整数溢出具体增长常量属于版本细节不应当成 API 契约。正常入队的时间复杂度为 O(1)。触发扩容的一次入队是 O(n)因为要分配新数组并复制已有元素按几何方式增长时连续 n 次入队的总复制量仍可摊销因此平均每次为摊销 O(1)。“摊销 O(1)”不代表每一帧都没有尖峰实时游戏若在关键帧触发大队列扩容仍可能出现明显抖动。写入引用类型或含引用字段的值类型时运行时还可能执行 GC 写屏障。这是维护回收器引用关系所必需的成本并非 Queue 独有。预设合理容量能减少后备数组替换但不能消除每次引用写入的语义。五、Dequeue、Peek 与 Try 系列5.1 Dequeue取值、清槽、移动头部.NET 8基线语义可简化为// 教学伪代码异常类型和辅助调用与公开 API 语义一致。 public T Dequeue() { if (_size 0) throw new InvalidOperationException(Queue is empty.); T removed _array[_head]; if (RuntimeHelpers.IsReferenceOrContainsReferencesT()) _array[_head] default!; MoveNext(ref _head, _array.Length); _size--; _version; return removed; }旧稿中“Dequeue不清空引用”的说法是错误的。现代实现通过RuntimeHelpers.IsReferenceOrContainsReferencesT()判断T是否为引用类型或内部含托管引用若是则清空离队槽避免后备数组继续让对象可达。对于纯值类型覆盖为零通常没有 GC 收益因此可以跳过写入。清槽不等于缩容。出队后数组容量保持不变后续入队可复用该槽只有显式裁剪才可能换成较小数组。若出队结果仍被调用者、其他集合或 Unity 对象包装引用当然仍不会被回收。5.2 Peek观察但不修改Peek在空队列抛出InvalidOperationException非空时返回_array[_head]。它不改变头、尾、数量与版本。因此一个已经取得的枚举器不会因单纯Peek失效。返回T可能复制值类型。若T是很大的结构体频繁Peek或Dequeue的复制成本应在目标环境测量标准QueueT的公开 API 不提供按引用暴露内部槽位因为那会让生命周期、扩容和修改控制变得危险。5.3 TryDequeue 与 TryPeekTryDequeue(out T result)把“队列可能为空”表达成正常分支空时返回false并把result设为default非空时执行与Dequeue相同的删除语义。TryPeek对应只读观察。它们避免用异常处理正常的无数据状态但并非“永不失败”或“天然线程安全”。while (queue.TryDequeue(out WorkItem item)) { Process(item); }对非空结果若T可空default可能也是合法元素因此必须以布尔返回值判断成功不能用result is null推断。空队列上的 Try 操作不发生结构修改不应借机递增数量版本是否变化应按源码基线验证不要由方法名猜测。选择规则很简单空状态违反调用方不变量时使用Dequeue/Peek让异常暴露错误空状态是轮询或消费循环的正常结果时使用 Try 系列。六、扩容为什么必须按两段复制扩容不只是把物理数组原样复制到更大的数组因为有效元素可能跨越末端。目标是把逻辑顺序展平到新数组[0, size)。若_head _tail且队列未满有效区间连续可以复制_size个元素。若已环绕逻辑序列由两段组成旧数组的[_head, oldLength)然后是[0, _tail)。// 教学伪代码表达 SetCapacity 的逻辑不是逐字源码。 void SetCapacity(int capacity) { T[] next new T[capacity]; if (_size 0) { if (_head _tail) { Array.Copy(_array, _head, next, 0, _size); } else { int rightCount _array.Length - _head; Array.Copy(_array, _head, next, 0, rightCount); Array.Copy(_array, 0, next, rightCount, _tail); } } _array next; _head 0; _tail (_size capacity) ? 0 : _size; _version; }最后一行尾索引的处理容易写错。当新容量正好等于_size队列处于满状态“下一写入位置”应环回 0而不能设置成等于数组长度的非法下标。正常增长后容量大于数量尾索引才是_size。两段长度有一个很好用的校验式(oldLength - head) tail size // 环绕或满队列分支若这个等式不成立复制边界、状态本身或分支条件至少有一处错误。扩容完成后逻辑顺序不变物理布局恢复连续head 0。七、Clear、EnsureCapacity 与 TrimExcess7.1 Clear清除逻辑内容还要释放引用Clear将数量归零并重置头尾。若T是引用类型或含引用基线实现会清除当前有效槽位有效区连续时清一段环绕时清两段。它没有必要清理从未有效或已经在出队时清过的全部容量。连续区clear [head, head size) 环绕区clear [head, length)再 clear [0, tail)Clear通常不归还后备数组因此Capacity保留适合预计还会复用的队列。它属于结构修改已有枚举器应当失效。不能用Count 0推导占用内存已回到初始状态。7.2 EnsureCapacity把可能的扩容移出关键路径基线版本的EnsureCapacity(int capacity)确保容量至少达到请求值并返回实际容量。负数参数应抛出参数范围异常若现有容量足够则无需搬迁。若需要增长它通过容量设置路径展平并复制已有逻辑序列。典型用途是已知 BFS 的节点上界、一个网络批次的最大事件数或可从历史峰值估计工作集。预留不是越大越好一个装着少量元素却长期保留巨大数组的队列会提高内存峰值和 GC 扫描/管理压力。应把容量依据写进设计例如“地图最大可达格 65,536”而不是随手给百万。7.3 TrimExcess以复制换常驻内存参数lessTrimExcess()会在容量明显高于数量时把容量收紧到当前数量.NET 8基线使用接近九成的阈值避免只空出少量槽位就分配复制。阈值属于实现细节不应依赖它控制业务行为。裁剪是 O(n)会分配新数组、复制并展平内容还会使枚举器失效。若裁到恰好等于数量队列是满的尾索引归零。频繁“清一点就 Trim、随后又 Enqueue”会形成收缩—扩容震荡。合理时机通常是关卡切换、长期负载阶段结束或内存预算明确收紧而不是每帧调用。某些新版本可能增加其他重载或调整增长细节使用前应查目标框架的 reference assembly 与对应 runtime tag本文不把未来 API 倒写进.NET 8基线。八、枚举输出逻辑顺序而不是物理顺序foreach必须依次产生从_head开始的_size个元素。对前述物理布局[F,G,C,D,E]结果必须是 C、D、E、F、G。枚举器一般保存创建时的_version和当前逻辑偏移每次取值时把逻辑偏移映射为物理下标。枚举期间发生Enqueue、成功的Dequeue/TryDequeue、Clear、实际扩容或裁剪会改变结构或后备数组。枚举器检测版本不一致后抛出InvalidOperationException这是尽早暴露错误的 fail-fast 机制不是并发同步保证。// 错误枚举期间修改同一个队列。 foreach (WorkItem item in queue) { if (item.Cancelled) queue.Dequeue(); }若要消费直接使用while (TryDequeue(...))若要基于快照遍历并容忍后续修改可以显式ToArray()但要承担 O(n) 复制和额外数组分配。ToArray()也必须保持逻辑 FIFO 顺序而不是物理数组顺序。版本检查不能使跨线程访问安全。另一个线程可能在检查前后修改字段普通读写之间不存在完整队列协议。即使某次压力测试“没出错”也可能只是没有撞上竞态窗口。九、复杂度、内存与 GC 成本模型操作通常成本最坏情况额外说明Enqueue摊销 O(1)O(n)满时分配并复制Dequeue/TryDequeue成功O(1)O(1)含引用的槽位会清零Peek/TryPeekO(1)O(1)不修改版本和状态ClearO(n) 或 O(1)O(n)是否扫描清槽取决于T是否含引用EnsureCapacityO(1) 或 O(n)O(n)仅增长时分配复制TrimExcessO(1) 或 O(n)O(n)达到收缩条件时分配复制枚举O(n)O(n)按逻辑顺序映射下标空间复杂度为 O(capacity)。队列对象本身只有少数字段主要内存来自T[]。若T是引用类型数组保存引用对象本体另行分配若T是值类型值直接内联在数组中。大值类型会使扩容复制更多字节而引用类型会增加对象数和指针追踪。旧数组在扩容后变成待回收对象若它很大分配与回收策略还受具体运行时的大对象规则影响。不要把某个 CoreCLR 阈值直接套到 Unity Mono 或 IL2CPP也不要宣称预分配一定降低总内存它降低增长次数却可能提高常驻和峰值容量。QueueT只保持数组中现有元素的强引用。成功出队或清空会释放槽位引用但调用者拿到的局部变量、闭包、缓存和其他集合仍可能持有对象。内存分析应从 GC 根追踪真实保留路径而不是看到 Queue 的容量就认定所有槽都在保活对象。十、非线程安全事件队列不是并发队列普通QueueT不支持无同步的多生产者/多消费者。典型竞态包括两个生产者覆盖同一尾槽、消费者读到尚未提交的值、数量丢失更新以及扩容期间其他线程继续访问旧数组。可选方案取决于协议简单低频场景可在所有访问处使用同一把锁多线程生产消费通常考虑ConcurrentQueueT并另行设计唤醒、停止和容量控制异步工作流可考虑ChannelT用有界通道表达等待和背压游戏引擎中常让后台线程写入线程安全入口再由主线程批量转入仅主线程拥有的QueueT。把Count 0与随后Dequeue()分开即使单个属性读取和方法调用各自“看起来原子”组合也不是原子协议。另一个消费者可在两步之间取走最后一个元素。锁或 Try 方法只有在适当并发容器/外部同步下才解决竞态普通QueueT.TryDequeue本身不会变成并发操作。十一、案例一BFS 的队列不变量广度优先搜索把待访问节点按层推进。最基本写法如下var frontier new Queueint(); var visited new bool[nodeCount]; frontier.Enqueue(start); visited[start] true; // 入队时标记避免重复入队。 while (frontier.TryDequeue(out int node)) { foreach (int next in graph[node]) { if (visited[next]) continue; visited[next] true; frontier.Enqueue(next); } }关键不是语法而是“入队时标记”。若出队后才标记同一节点可能被多个前驱重复入队队列峰值和工作量急剧增大。已知节点总数时可EnsureCapacity(nodeCount)但大型开放世界图若只探索小区域直接按全图上界预留可能浪费内存。测试 BFS 时应覆盖自环、重复边、不连通图、单节点图和宽度极大的层并验证结果距离而非只验证访问数量。环形数组保持 FIFO 是最短边数路径成立的基础若误按物理下标枚举或复制层序会被破坏。十二、案例二主线程事件队列、帧预算与背压事件队列能把生产与消费解耦却不能创造处理能力。生产速率长期大于消费速率时任何无界 Queue 最终都会增长带来延迟、内存上涨和扩容尖峰。主线程可以按时间和数量双预算消费// 示例策略具体计时 API 与预算应按引擎环境选择。 int processed 0; long deadline Stopwatch.GetTimestamp() budgetTicks; while (processed maxPerFrame Stopwatch.GetTimestamp() deadline events.TryDequeue(out GameEvent evt)) { Dispatch(evt); processed; }但仅限流消费不算完整背压。还要定义队列达到高水位后的策略事件类别可选策略风险输入边沿、交易结果不可静默丢弃限制生产或转移工作延迟上升需要明确超时位置刷新、进度百分比按实体键合并只保留最新值必须保证中间态确实可丢遥测、低级日志采样、批处理或丢弃最旧项要记录丢弃计数避免无声失真可取消后台结果过期代次直接拒绝入主队列需要任务代次和所有权协议标准QueueT没有固定容量和自动背压。若业务需要严格上界应在外层维护容量策略或采用有界通道。不能在超限时盲目Dequeue最旧项因为 FIFO 只规定顺序不证明最旧事件可丢。运行监控至少记录当前深度、观察窗口峰值、入队率、出队率、最老事件年龄、预算耗尽次数和丢弃/合并数量。只看平均 Count 会掩盖尖峰。容量可以根据有证据的峰值预热并在场景结束后评估是否裁剪避免每帧自动伸缩。十三、实现与使用测试清单13.1 状态机边界新队列Count 0TryPeek/TryDequeue返回 false抛异常版本按契约抛出。容量 0 的首次入队成功不发生模 0 或非法下标。填满后head tail仍能依靠 size 判断为满。多次出队再入队发生一次和多次环绕逻辑顺序始终正确。单元素入队、查看、出队后头尾数量回到合法空状态。13.2 扩容与容量管理未环绕状态扩容后顺序不变。环绕状态扩容覆盖右段和左段复制数量之和等于 size。满队列扩容时旧head tail不被误判为空。EnsureCapacity小于现容量不丢元素需要增长时返回容量不小于请求。TrimExcess后顺序不变随后一次入队仍合法避免把阈值具体值写成业务断言。13.3 引用与枚举引用类型成功出队后内部离队槽不再保留该引用测试避免局部变量自身成为 GC 根而造成误判。含引用字段的结构体同样触发必要清槽纯值类型保持正确值语义。Clear对连续区、环绕区和满队列都释放有效槽引用。枚举和ToArray输出逻辑 FIFO 顺序而非物理下标顺序。枚举期间结构修改触发失效单纯Peek不应改变结构。13.4 业务与并发BFS 对重复边和自环不会重复爆量距离结果正确。帧预算耗尽后剩余事件保留下一帧继续且顺序符合业务约定。高水位的拒绝、合并或丢弃策略有指标和测试不静默损失关键事件。所有跨线程访问都通过同一同步协议或并发容器不以压力测试偶然通过作为安全证明。性能报告记录运行时、版本、构建模式、平台、输入分布、预热、容量与 GC 指标不使用脱离环境的倍数。属性测试尤其适合环形队列随机生成 Enqueue、Dequeue、Clear、Ensure 与 Trim 操作序列同时用一个简单参考模型保存逻辑序列每一步比较 Count、Peek、枚举和出队结果。它比只测“入队 1、2、3”更容易击中满、空、环绕和扩容交界。十四、总结环形数组的本质是维护映射QueueT用_head、_tail和_size把线性数组映射成 FIFO 序列。头表示下一读位置尾表示下一写位置数量负责区分头尾重合时的空与满。正常 Enqueue、Dequeue 和 Peek 为 O(1)扩容通过一段或两段复制把逻辑序列展平因此是 O(n)几何增长使连续入队具有摊销 O(1) 成本却不能消除实时帧中的单次尖峰。.NET 8基线使用边界分支推进索引而不是必然执行%成功出队会在T是引用或含引用时清空槽位并非继续无条件保活对象。Clear 保留容量但清理有效引用EnsureCapacity 把扩容移出关键路径TrimExcess 以分配复制换取更小常驻数组。枚举必须服从逻辑顺序并用版本号发现结构修改但版本号不是线程同步。在 BFS 中正确的入队标记决定队列峰值在事件系统中FIFO 也替代不了帧预算和背压。掌握 Queue 的标准不是背出源码而是能写出不变量、证明两段复制边界、解释引用生命周期并用针对空、满、环绕、扩容与并发协议的测试守住这些结论。下一篇PriorityQueueTElement, TPriority.NET 6 最小堆实现 05-02-栈队列-Queue-T-FIFO的环形数组实现
QueueTFIFO 的环形数组实现系列C# 与常用数据结构源码剖析 · 栈与队列篇阅读时间约 65 分钟源码基线.NET 8.0.0的dotnet/runtimeSystem.Private.CoreLib/src/System/Collections/Generic/Queue.cs版本说明本文用源码基线解释语义为突出不变量代码均是教学化摘录或伪代码不冒充逐字源码。其他 .NET 版本应按 tag 复核 API 与实现细节。一、队列真正解决的是什么队列提供先进先出FIFO语义先入队的元素先出队。若直接把有效元素放在数组的[0, Count)Enqueue很简单但每次Dequeue都要把剩余元素整体左移单次复杂度为 O(n)。连续清空 n 个元素便可能产生 O(n²) 的复制量。QueueT的关键不是“换一种数组”而是改变对数组下标的解释已经出队的前部空间不立即搬移头部索引向前走尾部到达数组末端后回到 0复用前部槽位。物理数组是线性的逻辑序列是环形映射出来的。环形数组带来三项收益正常入队、出队和查看队首都是 O(1)元素集中在一块数组中通常比逐节点分配更紧凑容量可以复用。代价是状态不再由一个长度完全描述所有操作必须共同维护头、尾、数量和版本不变量。本文关心的不只是方法怎么写还要回答队列满时为什么头尾可以相等扩容为什么需要两段复制删除后是否继续持有对象枚举为什么必须按逻辑顺序游戏主线程的事件队列为什么仍可能拖垮帧时间二、五个字段和一组不变量以.NET 8.0.0为基线理解实现所需的核心状态可抽象为// 教学化字段摘录不是完整源码。 private T[] _array; private int _head; // 下一个出队或查看的位置 private int _tail; // 下一个入队的位置 private int _size; // 逻辑元素数量 private int _version; // 结构修改版本用于枚举失效检测某些版本还含非泛型接口同步相关的状态它不改变环形算法。对容量C _array.Length非空缓冲区应满足0 _size C 0 _head C 0 _tail C 逻辑第 i 个元素位于 (_head i) mod C0 i _size空数组是特殊初始状态容量为 0此时不会计算模 0第一次入队先扩容。普通空队列通常把_head、_tail归到 0。2.1 head、tail 和 size 缺一不可只靠_head与_tail无法区分“空”和“满”容量 4空head 0, tail 0, size 0 容量 4满head 0, tail 0, size 4有些自制环形缓冲区会永久浪费一个槽位以head tail表示空QueueT保存_size因此可以使用全部容量。_tail不是“最后一个元素”而是下一次写入的位置。最后一个逻辑元素应通过头和数量推导。2.2 物理状态与逻辑顺序假设容量为 5依次入队 A、B、C、D出队 A、B再入队 E、F、G物理下标 0 1 2 3 4 物理内容 [F] [G] [C] [D] [E] ^ ^ tail2 head2 size5 逻辑顺序C, D, E, F, G此时head tail但队列是满的。任何把[0, size)当作有效区间的代码都会读错顺序。一个可靠的心智模型是_head是逻辑坐标系的原点数组下标只是其投影。三、边界推进语义是环绕实现不必做取模概念公式是(index 1) % capacity。但对每次只前进一步的场景.NET 8基线源码采用条件归零其意图可写成// 教学伪代码基线实现使用相同的边界思想。 static void MoveNext(ref int index, int length) { int next index 1; if (next length) next 0; index next; }所以“Queue 每次操作都多一次%因此必然慢某个比例”并不符合这个源码版本。即使另一实现使用取模也不能脱离 CPU、JIT/AOT、容量和工作负载给出神奇倍数。真正重要的是边界正确只有在容量大于 0 时推进且结果始终落在合法下标范围。若一次跨越多个位置例如计算逻辑第 i 个元素可使用取模也可先加后减容量。后者仅在已知和不超过某个范围时成立// 当 0 i size length 时加法结果小于 2 * length。 int physical head i; if (physical length) physical - length;自制实现若允许任意大步长或索引加法溢出必须采用相应的范围证明或更宽类型不能机械复制这个技巧。四、Enqueue先保证空间再提交状态入队的抽象步骤如下// 教学伪代码省略真实源码的常量和辅助方法细节。 public void Enqueue(T item) { if (_size _array.Length) Grow(requiredCapacity: _size 1); _array[_tail] item; MoveNext(ref _tail, _array.Length); _size; _version; }队列满时必须先扩容因为_tail正指向_head覆盖它会破坏最老元素。扩容策略通常按比例增长同时确保不少于所需容量并处理数组最大长度和整数溢出具体增长常量属于版本细节不应当成 API 契约。正常入队的时间复杂度为 O(1)。触发扩容的一次入队是 O(n)因为要分配新数组并复制已有元素按几何方式增长时连续 n 次入队的总复制量仍可摊销因此平均每次为摊销 O(1)。“摊销 O(1)”不代表每一帧都没有尖峰实时游戏若在关键帧触发大队列扩容仍可能出现明显抖动。写入引用类型或含引用字段的值类型时运行时还可能执行 GC 写屏障。这是维护回收器引用关系所必需的成本并非 Queue 独有。预设合理容量能减少后备数组替换但不能消除每次引用写入的语义。五、Dequeue、Peek 与 Try 系列5.1 Dequeue取值、清槽、移动头部.NET 8基线语义可简化为// 教学伪代码异常类型和辅助调用与公开 API 语义一致。 public T Dequeue() { if (_size 0) throw new InvalidOperationException(Queue is empty.); T removed _array[_head]; if (RuntimeHelpers.IsReferenceOrContainsReferencesT()) _array[_head] default!; MoveNext(ref _head, _array.Length); _size--; _version; return removed; }旧稿中“Dequeue不清空引用”的说法是错误的。现代实现通过RuntimeHelpers.IsReferenceOrContainsReferencesT()判断T是否为引用类型或内部含托管引用若是则清空离队槽避免后备数组继续让对象可达。对于纯值类型覆盖为零通常没有 GC 收益因此可以跳过写入。清槽不等于缩容。出队后数组容量保持不变后续入队可复用该槽只有显式裁剪才可能换成较小数组。若出队结果仍被调用者、其他集合或 Unity 对象包装引用当然仍不会被回收。5.2 Peek观察但不修改Peek在空队列抛出InvalidOperationException非空时返回_array[_head]。它不改变头、尾、数量与版本。因此一个已经取得的枚举器不会因单纯Peek失效。返回T可能复制值类型。若T是很大的结构体频繁Peek或Dequeue的复制成本应在目标环境测量标准QueueT的公开 API 不提供按引用暴露内部槽位因为那会让生命周期、扩容和修改控制变得危险。5.3 TryDequeue 与 TryPeekTryDequeue(out T result)把“队列可能为空”表达成正常分支空时返回false并把result设为default非空时执行与Dequeue相同的删除语义。TryPeek对应只读观察。它们避免用异常处理正常的无数据状态但并非“永不失败”或“天然线程安全”。while (queue.TryDequeue(out WorkItem item)) { Process(item); }对非空结果若T可空default可能也是合法元素因此必须以布尔返回值判断成功不能用result is null推断。空队列上的 Try 操作不发生结构修改不应借机递增数量版本是否变化应按源码基线验证不要由方法名猜测。选择规则很简单空状态违反调用方不变量时使用Dequeue/Peek让异常暴露错误空状态是轮询或消费循环的正常结果时使用 Try 系列。六、扩容为什么必须按两段复制扩容不只是把物理数组原样复制到更大的数组因为有效元素可能跨越末端。目标是把逻辑顺序展平到新数组[0, size)。若_head _tail且队列未满有效区间连续可以复制_size个元素。若已环绕逻辑序列由两段组成旧数组的[_head, oldLength)然后是[0, _tail)。// 教学伪代码表达 SetCapacity 的逻辑不是逐字源码。 void SetCapacity(int capacity) { T[] next new T[capacity]; if (_size 0) { if (_head _tail) { Array.Copy(_array, _head, next, 0, _size); } else { int rightCount _array.Length - _head; Array.Copy(_array, _head, next, 0, rightCount); Array.Copy(_array, 0, next, rightCount, _tail); } } _array next; _head 0; _tail (_size capacity) ? 0 : _size; _version; }最后一行尾索引的处理容易写错。当新容量正好等于_size队列处于满状态“下一写入位置”应环回 0而不能设置成等于数组长度的非法下标。正常增长后容量大于数量尾索引才是_size。两段长度有一个很好用的校验式(oldLength - head) tail size // 环绕或满队列分支若这个等式不成立复制边界、状态本身或分支条件至少有一处错误。扩容完成后逻辑顺序不变物理布局恢复连续head 0。七、Clear、EnsureCapacity 与 TrimExcess7.1 Clear清除逻辑内容还要释放引用Clear将数量归零并重置头尾。若T是引用类型或含引用基线实现会清除当前有效槽位有效区连续时清一段环绕时清两段。它没有必要清理从未有效或已经在出队时清过的全部容量。连续区clear [head, head size) 环绕区clear [head, length)再 clear [0, tail)Clear通常不归还后备数组因此Capacity保留适合预计还会复用的队列。它属于结构修改已有枚举器应当失效。不能用Count 0推导占用内存已回到初始状态。7.2 EnsureCapacity把可能的扩容移出关键路径基线版本的EnsureCapacity(int capacity)确保容量至少达到请求值并返回实际容量。负数参数应抛出参数范围异常若现有容量足够则无需搬迁。若需要增长它通过容量设置路径展平并复制已有逻辑序列。典型用途是已知 BFS 的节点上界、一个网络批次的最大事件数或可从历史峰值估计工作集。预留不是越大越好一个装着少量元素却长期保留巨大数组的队列会提高内存峰值和 GC 扫描/管理压力。应把容量依据写进设计例如“地图最大可达格 65,536”而不是随手给百万。7.3 TrimExcess以复制换常驻内存参数lessTrimExcess()会在容量明显高于数量时把容量收紧到当前数量.NET 8基线使用接近九成的阈值避免只空出少量槽位就分配复制。阈值属于实现细节不应依赖它控制业务行为。裁剪是 O(n)会分配新数组、复制并展平内容还会使枚举器失效。若裁到恰好等于数量队列是满的尾索引归零。频繁“清一点就 Trim、随后又 Enqueue”会形成收缩—扩容震荡。合理时机通常是关卡切换、长期负载阶段结束或内存预算明确收紧而不是每帧调用。某些新版本可能增加其他重载或调整增长细节使用前应查目标框架的 reference assembly 与对应 runtime tag本文不把未来 API 倒写进.NET 8基线。八、枚举输出逻辑顺序而不是物理顺序foreach必须依次产生从_head开始的_size个元素。对前述物理布局[F,G,C,D,E]结果必须是 C、D、E、F、G。枚举器一般保存创建时的_version和当前逻辑偏移每次取值时把逻辑偏移映射为物理下标。枚举期间发生Enqueue、成功的Dequeue/TryDequeue、Clear、实际扩容或裁剪会改变结构或后备数组。枚举器检测版本不一致后抛出InvalidOperationException这是尽早暴露错误的 fail-fast 机制不是并发同步保证。// 错误枚举期间修改同一个队列。 foreach (WorkItem item in queue) { if (item.Cancelled) queue.Dequeue(); }若要消费直接使用while (TryDequeue(...))若要基于快照遍历并容忍后续修改可以显式ToArray()但要承担 O(n) 复制和额外数组分配。ToArray()也必须保持逻辑 FIFO 顺序而不是物理数组顺序。版本检查不能使跨线程访问安全。另一个线程可能在检查前后修改字段普通读写之间不存在完整队列协议。即使某次压力测试“没出错”也可能只是没有撞上竞态窗口。九、复杂度、内存与 GC 成本模型操作通常成本最坏情况额外说明Enqueue摊销 O(1)O(n)满时分配并复制Dequeue/TryDequeue成功O(1)O(1)含引用的槽位会清零Peek/TryPeekO(1)O(1)不修改版本和状态ClearO(n) 或 O(1)O(n)是否扫描清槽取决于T是否含引用EnsureCapacityO(1) 或 O(n)O(n)仅增长时分配复制TrimExcessO(1) 或 O(n)O(n)达到收缩条件时分配复制枚举O(n)O(n)按逻辑顺序映射下标空间复杂度为 O(capacity)。队列对象本身只有少数字段主要内存来自T[]。若T是引用类型数组保存引用对象本体另行分配若T是值类型值直接内联在数组中。大值类型会使扩容复制更多字节而引用类型会增加对象数和指针追踪。旧数组在扩容后变成待回收对象若它很大分配与回收策略还受具体运行时的大对象规则影响。不要把某个 CoreCLR 阈值直接套到 Unity Mono 或 IL2CPP也不要宣称预分配一定降低总内存它降低增长次数却可能提高常驻和峰值容量。QueueT只保持数组中现有元素的强引用。成功出队或清空会释放槽位引用但调用者拿到的局部变量、闭包、缓存和其他集合仍可能持有对象。内存分析应从 GC 根追踪真实保留路径而不是看到 Queue 的容量就认定所有槽都在保活对象。十、非线程安全事件队列不是并发队列普通QueueT不支持无同步的多生产者/多消费者。典型竞态包括两个生产者覆盖同一尾槽、消费者读到尚未提交的值、数量丢失更新以及扩容期间其他线程继续访问旧数组。可选方案取决于协议简单低频场景可在所有访问处使用同一把锁多线程生产消费通常考虑ConcurrentQueueT并另行设计唤醒、停止和容量控制异步工作流可考虑ChannelT用有界通道表达等待和背压游戏引擎中常让后台线程写入线程安全入口再由主线程批量转入仅主线程拥有的QueueT。把Count 0与随后Dequeue()分开即使单个属性读取和方法调用各自“看起来原子”组合也不是原子协议。另一个消费者可在两步之间取走最后一个元素。锁或 Try 方法只有在适当并发容器/外部同步下才解决竞态普通QueueT.TryDequeue本身不会变成并发操作。十一、案例一BFS 的队列不变量广度优先搜索把待访问节点按层推进。最基本写法如下var frontier new Queueint(); var visited new bool[nodeCount]; frontier.Enqueue(start); visited[start] true; // 入队时标记避免重复入队。 while (frontier.TryDequeue(out int node)) { foreach (int next in graph[node]) { if (visited[next]) continue; visited[next] true; frontier.Enqueue(next); } }关键不是语法而是“入队时标记”。若出队后才标记同一节点可能被多个前驱重复入队队列峰值和工作量急剧增大。已知节点总数时可EnsureCapacity(nodeCount)但大型开放世界图若只探索小区域直接按全图上界预留可能浪费内存。测试 BFS 时应覆盖自环、重复边、不连通图、单节点图和宽度极大的层并验证结果距离而非只验证访问数量。环形数组保持 FIFO 是最短边数路径成立的基础若误按物理下标枚举或复制层序会被破坏。十二、案例二主线程事件队列、帧预算与背压事件队列能把生产与消费解耦却不能创造处理能力。生产速率长期大于消费速率时任何无界 Queue 最终都会增长带来延迟、内存上涨和扩容尖峰。主线程可以按时间和数量双预算消费// 示例策略具体计时 API 与预算应按引擎环境选择。 int processed 0; long deadline Stopwatch.GetTimestamp() budgetTicks; while (processed maxPerFrame Stopwatch.GetTimestamp() deadline events.TryDequeue(out GameEvent evt)) { Dispatch(evt); processed; }但仅限流消费不算完整背压。还要定义队列达到高水位后的策略事件类别可选策略风险输入边沿、交易结果不可静默丢弃限制生产或转移工作延迟上升需要明确超时位置刷新、进度百分比按实体键合并只保留最新值必须保证中间态确实可丢遥测、低级日志采样、批处理或丢弃最旧项要记录丢弃计数避免无声失真可取消后台结果过期代次直接拒绝入主队列需要任务代次和所有权协议标准QueueT没有固定容量和自动背压。若业务需要严格上界应在外层维护容量策略或采用有界通道。不能在超限时盲目Dequeue最旧项因为 FIFO 只规定顺序不证明最旧事件可丢。运行监控至少记录当前深度、观察窗口峰值、入队率、出队率、最老事件年龄、预算耗尽次数和丢弃/合并数量。只看平均 Count 会掩盖尖峰。容量可以根据有证据的峰值预热并在场景结束后评估是否裁剪避免每帧自动伸缩。十三、实现与使用测试清单13.1 状态机边界新队列Count 0TryPeek/TryDequeue返回 false抛异常版本按契约抛出。容量 0 的首次入队成功不发生模 0 或非法下标。填满后head tail仍能依靠 size 判断为满。多次出队再入队发生一次和多次环绕逻辑顺序始终正确。单元素入队、查看、出队后头尾数量回到合法空状态。13.2 扩容与容量管理未环绕状态扩容后顺序不变。环绕状态扩容覆盖右段和左段复制数量之和等于 size。满队列扩容时旧head tail不被误判为空。EnsureCapacity小于现容量不丢元素需要增长时返回容量不小于请求。TrimExcess后顺序不变随后一次入队仍合法避免把阈值具体值写成业务断言。13.3 引用与枚举引用类型成功出队后内部离队槽不再保留该引用测试避免局部变量自身成为 GC 根而造成误判。含引用字段的结构体同样触发必要清槽纯值类型保持正确值语义。Clear对连续区、环绕区和满队列都释放有效槽引用。枚举和ToArray输出逻辑 FIFO 顺序而非物理下标顺序。枚举期间结构修改触发失效单纯Peek不应改变结构。13.4 业务与并发BFS 对重复边和自环不会重复爆量距离结果正确。帧预算耗尽后剩余事件保留下一帧继续且顺序符合业务约定。高水位的拒绝、合并或丢弃策略有指标和测试不静默损失关键事件。所有跨线程访问都通过同一同步协议或并发容器不以压力测试偶然通过作为安全证明。性能报告记录运行时、版本、构建模式、平台、输入分布、预热、容量与 GC 指标不使用脱离环境的倍数。属性测试尤其适合环形队列随机生成 Enqueue、Dequeue、Clear、Ensure 与 Trim 操作序列同时用一个简单参考模型保存逻辑序列每一步比较 Count、Peek、枚举和出队结果。它比只测“入队 1、2、3”更容易击中满、空、环绕和扩容交界。十四、总结环形数组的本质是维护映射QueueT用_head、_tail和_size把线性数组映射成 FIFO 序列。头表示下一读位置尾表示下一写位置数量负责区分头尾重合时的空与满。正常 Enqueue、Dequeue 和 Peek 为 O(1)扩容通过一段或两段复制把逻辑序列展平因此是 O(n)几何增长使连续入队具有摊销 O(1) 成本却不能消除实时帧中的单次尖峰。.NET 8基线使用边界分支推进索引而不是必然执行%成功出队会在T是引用或含引用时清空槽位并非继续无条件保活对象。Clear 保留容量但清理有效引用EnsureCapacity 把扩容移出关键路径TrimExcess 以分配复制换取更小常驻数组。枚举必须服从逻辑顺序并用版本号发现结构修改但版本号不是线程同步。在 BFS 中正确的入队标记决定队列峰值在事件系统中FIFO 也替代不了帧预算和背压。掌握 Queue 的标准不是背出源码而是能写出不变量、证明两段复制边界、解释引用生命周期并用针对空、满、环绕、扩容与并发协议的测试守住这些结论。下一篇PriorityQueueTElement, TPriority.NET 6 最小堆实现