StackLIFO 语义、数组实现与工程边界系列C# 与常用数据结构源码剖析 · 栈与队列篇源码边界现代 .NET 的System.Collections.Generic.StackT实现细节须以目标运行时的dotnet/runtime发行 tag 为准前置知识数组、泛型、摊销分析、GC 引用可达性一、栈首先是一份访问契约栈规定后进先出Last In, First OutLIFO最后压入的元素最先弹出。它只公开栈顶这一端典型操作是Push、Pop和Peek。这种限制不是缺陷而是模型的核心。看到StackUndoCommand维护者立刻知道调用者不应随机访问历史中间项如果改用ListUndoCommand虽然也能从尾部模拟栈却额外暴露了索引、插入和排序等不属于该抽象的能力。需要先区分三个容易混淆的“栈”StackT是托管堆上的集合对象后备存储通常也是托管数组线程调用栈保存栈帧、返回地址和部分局部状态由运行时与 ABI 管理IL 求值栈是虚拟机验证和执行模型中的概念。三者都体现 LIFO但生命周期、容量限制和所有权完全不同。StackT.Push不会把任意业务对象“放到线程栈上”也不能用它规避 GC。本文展示的源码均为便于讨论的等价伪代码不是对某个版本文件的逐字复制。研究具体发布版时应切到对应dotnet/runtimetag检查System.Private.CoreLib中的Stack.cs并在目标 TFM 下实际编译 API。不要从仓库 main 分支反推旧版 .NET Framework、Unity Mono 或 IL2CPP 的实现。二、字段、不变式与内存布局现代 .NET 实现可抽象为三个关键字段// 等价伪代码字段名接近现代 .NET但不承诺适用于所有版本。 private T[] _array; private int _size; private int _version;_array是后备数组_size是当前有效元素数也等于下一次Push在容量足够时的写入下标_version用于让枚举器检测结构性修改。历史实现或显式ICollection支持还可能涉及同步根等成员但不能据此假定每个版本具有完全相同的字段布局。一个合法 Stack 必须保持这些不变式0 _size _array.Length 有效区间_array[0 .. _size) 栈底 _array[0] 非空时 栈顶 _array[_size - 1] 非空时 空闲区间_array[_size .. Length)依次压入 A、B、C 后物理数组和逻辑顺序如下下标 0 1 2 3 数组 [A] [B] [C] [unused] ^ ^ 栈底 栈顶 _size 3 弹出顺序C - B - A这与ListT都采用连续数组并不等于“二者实现完全相同”。它们共享尾部追加的一些成本模型但公共契约、枚举顺序、异常、容量 API 和内部快速路径可以不同。正确说法是Stack 用数组和一个边界索引实现受限的 LIFO 集合。容量是数组可容纳的元素数Count是逻辑元素数。容量大于 Count 很正常空闲槽位已经占据数组空间却不属于集合。数组对象本身还有对象头和长度等运行时开销引用类型元素的槽位保存引用值类型元素则内联存放。大型结构体会让复制、扩容和返回值成本增加包含引用字段的结构体还会影响 GC 扫描和清理策略。三、Push快路径、扩容与摊销成本容量充足时Push只需把元素写到_array[_size]更新数量并使版本失效。现代实现可能为了帮助 JIT 内联而把少见的扩容路径拆到单独方法中// 等价伪代码省略具体异常和最大数组长度处理。 public void Push(T item) { int size _size; T[] array _array; if ((uint)size (uint)array.Length) { array[size] item; _size size 1; _version; return; } PushWithResize(item); }PushWithResize会选择一个大于当前容量的新容量分配新数组复制有效区间然后写入新元素。许多实现采用几何增长因此单次扩容是 O(n)但连续 n 次 Push 的总复制量仍为 O(n)平均到每次就是摊销 O(1)。这不意味着每次 Push 都是固定延迟实时帧中恰好触发扩容时仍可能同时承担分配和复制。具体默认容量、增长倍数、接近数组上限时的钳制规则都属于实现细节应按目标 tag 核验。生产代码不应依赖“必定从 4 开始并永远翻倍”。更稳定的工程结论是若数量上界已知构造时给出容量或调用目标框架实际提供的容量 API可以把扩容移出热点代价是提前占用内存。int expectedDepth nodes.Count; var work new StackNode(expectedDepth);预估不是越大越好。高估会提高常驻内存若 Stack 被对象池长期持有偶发峰值还可能污染池。对巨大的引用数组即使大多数槽位未使用GC 仍需管理这个数组对象它所在的堆区域和回收行为取决于运行时与数组字节大小不能仅按元素数量猜测。EnsureCapacity、TrimExcess等成员的公开可用性以及行为必须针对 TFM 检查 reference assembly 或直接编译。文章和 IDE 所用的 SDK 不能替代目标环境。即使目标 API 存在也应基于需求使用EnsureCapacity 表达“至少容纳多少元素”不会改变 CountTrimExcess 尝试缩小后备存储却可能让下一轮增长再次分配。具体收缩阈值不是业务契约。四、Pop、Peek 与 Try 系列的精确语义4.1 Pop读取、缩小有效区间、必要时清引用Pop在非空时返回栈顶元素并将 Count 减一空栈时抛出InvalidOperationException。现代 .NET 的关键逻辑可抽象为// 等价伪代码。 public T Pop() { if (_size 0) throw new InvalidOperationException(Stack empty.); int index --_size; T item _array[index]; if (RuntimeHelpers.IsReferenceOrContainsReferencesT()) _array[index] default!; _version; return item; }清理槽位不是为了修改逻辑内容而是为了断开后备数组对已弹出对象的强引用。原来“Stack.Pop 刻意不清引用以实现零开销”的说法是错误的现代实现会针对引用类型或内部包含引用的值类型清理已释放槽位对纯值类型可以省去无意义清零。实际条件和生成代码仍须固定运行时验证。注意调用方得到的返回值item仍然引用该对象。只有调用方也不再保存引用时对象才可能不可达。清槽位既不是立即释放内存也不保证马上触发 GC它只是移除 Stack 内部的一条引用路径。4.2 Peek观察但不修改Peek返回_array[_size - 1]不改变 Count通常也不增加_version。空栈时它同样抛出InvalidOperationException。这使 Peek 适合“先检查栈顶状态再决定是否弹出”但在多线程环境中Peek后再Pop并不是原子事务。4.3 TryPop 与 TryPeek把空栈变成正常分支当空栈属于正常控制流时Try API 比捕获异常更清楚while (stack.TryPop(out Node? node)) { Visit(node); } if (stack.TryPeek(out Node? next)) { Preview(next); }失败时返回falseout 参数取默认值成功时返回true。对可空引用和泛型代码应结合 nullable 注解理解“失败时可能为空”而不是只看运行时值。TryPop 成功后与 Pop 一样属于结构修改并处理空闲槽位TryPeek 成功与否都不移除元素。Try API 的主要价值是语义与控制流并不能笼统称作“零开销”或保证比Count 0后调用 Pop 快多少。单线程中二者都可正确工作并发中Count检查与 Pop 之间存在竞态而 Stack 本身也不承诺多线程写安全。五、Clear、容量与 GC 的真实关系Clear()把逻辑 Count 置零并更新版本。对于可能持有托管引用的 T现代实现还需清理原有效区间以免这些对象继续被后备数组引用。对不含引用的值类型运行时可以避免无意义清理。Clear 通常保留数组容量以便后续复用所以它减少的是可达业务对象和逻辑内容不一定降低 Stack 自身后备数组占用。var stack new Stackbyte[](capacity: 1_000); // ... Push 与 Pop/Clear 会移除有效元素引用 // 但 stack 自身的后备数组可能继续保留其容量。 stack.Clear();若确实需要降低长期驻留容量可以在目标 API 支持时评估 TrimExcess或丢弃整个 Stack 让其随可达性回收。两种做法都不是免费的缩容会分配和复制丢弃对象会在以后重建。正确策略取决于峰值频率稳定反复使用时保留容量通常合理一次性异常峰值后长期闲置时回收大数组可能更合适。内存分析还应区分逻辑保留有效区间里的元素本来就应被 Stack 持有陈旧引用逻辑移除后槽位仍保留引用现代实现通过条件清理避免容量保留空闲数组槽位占空间但不引用旧对象调用方保留Pop 返回值、闭包、缓存或事件仍持有对象GC 尚未执行对象已经不可达进程内存却未立即下降。把这些情况全部称作“内存泄漏”会妨碍定位。托管泄漏通常指对象因意外引用而长期可达保留容量则是集合复用策略需要用内存快照、对象引用链和时间序列判断。六、枚举顺序、版本检测与线程安全Stack 的枚举顺序是从栈顶到栈底即与连续 Pop 的顺序一致而不是数组下标从小到大的物理顺序var stack new Stackstring(); stack.Push(A); stack.Push(B); stack.Push(C); Console.WriteLine(string.Join(,, stack)); // C,B,AToArray()的结果顺序也应按目标 API 契约理解不能因为后备数组是 A、B、C 就假定结果必然按下标排列。需要写存档协议时应显式定义顺序并添加往返测试而不是序列化私有字段或依赖反射看到的布局。枚举器通常捕获创建时的_version。在枚举期间 Push、Pop 或 Clear 会让版本改变后续枚举操作抛出InvalidOperationException。这是尽早暴露错误的 fail-fast 检测不是线程同步机制也不保证在所有竞争时序下提供一致快照。foreach (var item in stack) { // stack.Pop(); // 不要在同一 Stack 的枚举中修改它 Consume(item); }StackT不保证多个线程并发读写安全。即便属性读取看起来简单一个线程检查 Count 后另一个线程也可能先弹走元素。需要跨线程 LIFO 工作分发时应评估ConcurrentStackT并理解它的复合操作与快照语义需要把多步逻辑作为整体保护时仍可能需要显式锁。不要依赖ICollection.SyncRoot猜测泛型 Stack 会自动同步。七、案例一用迭代 DFS 控制遍历状态深度优先搜索天然适合栈。迭代版避免递归深度受线程调用栈限制还能显式控制访问顺序public static IEnumerableNode DepthFirst(Node root) { var pending new StackNode(); var visited new HashSetNode(); pending.Push(root); while (pending.TryPop(out Node? node)) { if (!visited.Add(node)) continue; yield return node; // 为保持从左到右访问按反序压栈。 for (int i node.Children.Count - 1; i 0; i--) pending.Push(node.Children[i]); } }对树可以省略 visited对可能成环的图不能省略否则算法可能无限循环。压栈顺序决定弹出顺序希望左孩子先访问就要先压右孩子。空间复杂度不是简单等于树高它取决于图结构、分支数和待处理前沿最坏可达 O(V)。若节点引用量巨大应在结束后让局部 Stack 尽快离开作用域而不是无条件放入全局池。Unity 中可用这种模式遍历技能依赖图、行为树、场景对象关系或寻路重建步骤。应避免在每帧为同一个固定规模任务不断新建集合可以复用局部工作缓冲但必须在归还池前 Clear并制定峰值容量淘汰策略。Unity 的具体 GC、Mono 与 IL2CPP 表现随版本和平台变化必须在目标 Player 上用 Profiler 验证不能照搬桌面 CoreCLR 微基准。八、案例二撤销系统需要的不只是两个 Stack最小撤销/重做模型由两个栈组成执行新命令时压入 undo并清空 redo撤销时从 undo 弹出、执行反向操作再压入 redo重做则反向搬运。public sealed class CommandHistory { private readonly StackICommand _undo new(); private readonly StackICommand _redo new(); public void Execute(ICommand command) { command.Execute(); _undo.Push(command); _redo.Clear(); } public bool TryUndo() { if (!_undo.TryPop(out ICommand? command)) return false; command.Undo(); _redo.Push(command); return true; } public bool TryRedo() { if (!_redo.TryPop(out ICommand? command)) return false; command.Execute(); _undo.Push(command); return true; } }工程实现还要处理异常原子性。如果Undo()抛异常命令已经从栈弹出是否应放回如果 Execute 部分修改状态后失败能否安全回滚命令若直接持有大型场景快照历史栈会有意延长其生命周期需要设置条数或字节预算。多人编辑还要考虑命令的因果关系两个普通 Stack 并不能解决冲突合并。因此 Stack 只负责历史顺序不负责事务、持久化或内存预算。把这些职责明确分层才不会将集合选型误认为完整系统设计。九、案例三解析器中的操作数顺序与错误边界逆波兰表达式可以用操作数栈求值。二元运算必须注意先弹出的是右操作数public static int EvaluatePostfix(IEnumerablestring tokens) { var values new Stackint(); foreach (string token in tokens) { if (int.TryParse(token, out int number)) { values.Push(number); continue; } if (!values.TryPop(out int right) || !values.TryPop(out int left)) throw new FormatException(Missing operand.); values.Push(token switch { checked(left right), - checked(left - right), * checked(left * right), / when right ! 0 left / right, / throw new DivideByZeroException(), _ throw new FormatException($Unknown operator: {token}) }); } if (!values.TryPop(out int result) || values.Count ! 0) throw new FormatException(Expression has extra operands.); return result; }表达式10 3 -必须得到 7而不是 -7。末尾还要验证只剩一个值否则1 2会被误判为有效表达式。真实解析器还需定义溢出、除零、词法错误和最大嵌套深度Stack 让状态管理清晰却不会自动提供输入安全。括号匹配也是类似用法但栈中最好存放“括号类型 源位置”这样报错时能指出未闭合符号所在行列而不只是返回 false。教科书算法走向工程代码关键往往是保留诊断上下文。十、复杂度、性能与选型操作时间复杂度是否修改结构备注Push摊销 O(1)扩容当次 O(n)是可能分配并复制Pop/TryPop成功O(1)是引用相关 T 需清理槽位Peek/TryPeekO(1)否仅观察栈顶ContainsO(n)否按相等比较线性扫描ClearO(n) 或近似 O(1)取决于 T 是否含引用及实现是通常保留容量ToArrayO(n)否分配新数组并复制枚举O(n)否逻辑顺序为栈顶到栈底扩容/收缩O(n)是分配与复制有效元素复杂度相同不表示延迟相同。元素大小、是否含引用、是否触发扩容、JIT、GC、CPU 缓存和发布模式都会影响常数项。没有完整环境、基准源码和原始报告时不应写“比 List 快若干倍”或“TryPop 零开销”。Stack 与 List 的主要选择依据是语义要验证某条热路径再使用 BenchmarkDotNet 或目标 Unity Player 的分析工具。适合 Stack 的场景包括 DFS、解析器状态、嵌套结构检查、撤销历史和需要反向处理的工作列表。不适合的情况包括需要先进先出使用QueueT需要按优先级取元素使用PriorityQueueTElement,TPriority需要随机访问或中部编辑考虑ListT需要双端高效操作评估专门 deque 实现需要多线程 LIFO评估ConcurrentStackT或显式同步最大深度很小且处于已证明的极热路径可以评估数组加栈指针但调用方必须自行维护越界、清引用与异常安全。最后一种自定义方案不天然更快。它可能减少抽象层也可能因为遗漏清理、重复扩容或无法被 JIT 优化而更差。只有剖析数据能证明它值得维护。十一、测试清单同时验证语义与资源行为一个可靠的 Stack 使用方至少应覆盖新栈 Count 为零Peek/Pop 抛出预期异常Try 方法返回 false按 A、B、C 压栈后Peek 为 C 且 Count 不变弹出顺序为 C、B、A元素数超过初始容量时扩容前后的内容和顺序保持正确Clear 后 Count 为零并能再次正常 Pushforeach 与 ToArray 的顺序满足调用方协议枚举期间修改会失败业务代码没有依赖未定义的并发行为DFS 对环、重复边、深链和空子节点的策略明确撤销命令抛异常时历史状态符合预先定义的事务策略解析器覆盖操作数不足、冗余操作数、除零、溢出和未知符号大规模引用对象 Pop/Clear 后用内存分析确认没有其他意外引用链容量预估、池化和 TrimExcess 策略在真实峰值回放中验证而非只看一次分配量Unity 场景分别在目标编辑器与 Player、目标脚本后端和目标设备上测试。如果文章要进一步声称某个版本改变了增长规则、增加了容量 API 或改善了某条路径还需追加四项证据目标 TFM 编译结果、reference assembly、对应运行时 tag 的源码差异以及可复现基准。API 文档回答“能否调用”源码回答“如何实现”基准回答“在该环境影响多大”三者不能相互替代。十二、总结StackT的优点不是神秘的性能捷径而是一份小而清晰的 LIFO 契约。现代 .NET 通常以连续数组保存有效区间以_size标记下一写入位置以_version检测枚举期间修改。Push 在容量充足时为常数时间扩容使其成为摊销常数Pop、Peek 与 Try 系列围绕同一栈顶边界提供异常式或分支式 API。理解实现时最重要的三个纠偏是数组型不代表与 List 完全相同现代 Pop 会在 T 可能含托管引用时清理释放槽位Clear 通常清逻辑内容却保留容量。工程上还要管理扩容尖峰、对象池峰值污染、枚举顺序、并发边界和上层事务语义。把 Stack 用在 DFS、撤销和解析器中时它解决的是“下一项从哪里取”的顺序问题。正确性、错误恢复、内存预算和跨线程协调仍由系统设计承担。涉及具体版本的 API 与内部实现始终以目标 reference assembly、发行 tag 和目标平台测试为准。下一篇QueueFIFO 的环形数组实现