05-04-栈队列-Stack-Queue-PriorityQueue-Channel与BlockingCollection选型

Queue、Stack、PriorityQueue、Channel 与 BlockingCollection从顺序语义到背压的选型方法系列C# 与常用数据结构源码剖析 · 栈与队列篇阅读时间约 60 分钟前置知识Stack、Queue 和 PriorityQueue 的内部结构async/await、线程和取消版本边界ChannelT、PriorityQueueTElement,TPriority等 API 的可用性必须以目标 TFM/reference assembly 和实际 Unity BCL 为准不根据当前机器能编译就推断所有目标可用。一、选型的第一个问题是“谁应该先被处理”容器名称不是性能标签而是顺序契约。QueueT表达先进先出StackT表达后进先出PriorityQueueTElement,TPriority表达按比较器定义的优先级出队。ChannelT不只是一个并发 Queue它还建模生产者和消费者的异步协调、完成、错误和背压。BlockingCollectionT则用阻塞线程的方式组织生产者消费者并可包装不同的IProducerConsumerCollectionT。如果顺序选错代码即使很快也是错的。用 Stack 做网络消息队列会让老消息长期饥饿用 FIFO Queue 做紧急任务调度会让新的高优先级任务在大量旧工作之后等待用 PriorityQueue 假装稳定 FIFO则在优先级相同时依赖了它并未承诺的顺序。第二个问题才是“谁会同时访问”。普通 Stack、Queue 和 PriorityQueue 不提供并发写安全枚举器的版本检测不是锁。单线程 PlayerLoop 内使用普通容器通常最清晰不应为了“以后可能多线程”提前把所有路径换成并发管道。当生产和消费确实跨线程或异步边界时才需要选择同步契约。二、五种主要工具的语义对照工具核心顺序等待模型容量策略典型适用场景StackTLIFO无内建等待动态数组DFS、解析状态、撤销栈QueueTFIFO无内建等待环形数组BFS、单线程事件队列、帧间工作PriorityQueueE,P最小优先级默认 comparer无内建等待堆数组A*、计时器、调度、Top-KChannelT通常是 FIFO 管道受选项影响await/ValueTask有界或无界异步生产消费、背压和完成传播BlockingCollectionT由底层并发集合决定常见 FIFO阻塞线程可有界同步多线程工作者管道ArrayPoolT不在这张顺序表中因为它不是队列没有 FIFO、LIFO 或优先级语义。它是数组所有权与复用工具可以为上述系统的数据载荷提供缓冲却不能代替任务调度容器。把它与 Queue 放在同一层决策树是类别错误。复杂度也不应简化成全部 O(1)。Stack Push 与 Queue Enqueue 在不扩容时是常数工作扩容时是 O(n)因而连续操作是均摊 O(1)。PriorityQueue 入队和出队需要沿堆高修复是 O(log n)。Channel 和 BlockingCollection 的实际成本还包含同步、等待者管理、调度、竞争和用户回调不能用一个 O(1) 标签与普通 Queue 直接比速度。三、什么时候选 StackStack 适合“最新上下文必须先完成”的问题。语法解析遇到左括号时入栈遇到右括号时必须与最近未闭合左括号匹配DFS 要先深入刚刚发现的分支临时操作失败时要按执行相反顺序做补偿。这些都是 LIFO 语义。static bool HasBalancedParentheses(ReadOnlySpanchar text) { var stack new Stackchar(); foreach (char c in text) { if (c () stack.Push(c); else if (c ) !stack.TryPop(out _)) return false; } return stack.Count 0; }撤销/重做通常不是只有一个 Stack而是 undo 与 redo 两个栈及明确规则新操作进入 undo 时清空 redo撤销时从 undo 弹出、执行反操作并放入 redo重做反之。命令必须保存足以可逆的数据而不是只保存方法名。历史无上限会增加内存应以条目数、字节预算或快照策略限制。Stack 不适合需要公平性的持续工作流新任务持续到达时旧任务可能永远无法处理。它也不是线程安全工作队列多线程 LIFO 需要专门并发结构或同步协议。四、什么时候选 QueueQueue 适合到达顺序就是服务顺序的工作。BFS 按与起点的边数层次扩展因此使用 FIFO游戏主线程可将本帧新生的非紧急工作入队在后续帧依次处理。static void ProcessWithinBudget(QueueIWorkItem queue, long deadline) { while (queue.TryPeek(out IWorkItem? item)) { if (Stopwatch.GetTimestamp() deadline) break; queue.Dequeue(); item.Execute(); } }这个示例表达帧预算但它还需要队列长度上限和超时策略。如果生产速率长期大于消费速率每帧“只处理预算内工作”会让延迟和内存无限增长。系统必须选择限制生产合并可替代任务丢弃过期任务提高消费并行度或明确向上游反压。Queue 的环形数组实现使尾部入队和头部出队在不扩容时无需搬移所有元素这比List.RemoveAt(0)更符合 FIFO。但 Queue 的枚举不是消费foreach不会自动出队。需要移交所有权时应通过Dequeue/TryDequeue表达。五、什么时候选 PriorityQueue优先队列适合“最值得处理的元素先出队”。默认 comparer 下是最小 priority 先出想让大数优先可使用反向 comparer 或设计清晰的 priority 类型不建议盲目对整数取负因为最小值取负有溢出边界。A* 将候选节点按f g h优先展开计时器按下一到期时间出队服务调度可按截止时间与业务等级组成复合优先级。但标准 PriorityQueue 不保证同优先级的稳定性。若需 FIFO 破平可把单调递增序号纳入复合 priorityreadonly record struct WorkPriority(int Level, long Sequence); sealed class WorkPriorityComparer : IComparerWorkPriority { public int Compare(WorkPriority x, WorkPriority y) { int level x.Level.CompareTo(y.Level); return level ! 0 ? level : x.Sequence.CompareTo(y.Sequence); } }标准优先队列不是任务数据库。更改已入队元素内部的 priority 字段不会自动修复堆。当 API 不提供 decrease-key/删除句柄时寻路可以采用“将新优先级再入队出队时丢弃过期版本”的惰性策略。这会增加队列项数需要过期率与容量监控。六、Channel 的价值是协议不是“await 版 Queue”Channel 将写端和读端分离为ChannelWriterT与ChannelReaderT并为可写/可读等待、完成和故障提供契约。它适合生产者和消费者生命周期不同且不应为等待空队列或满队列长期占用一个线程的场景。var channel Channel.CreateBoundedJob(new BoundedChannelOptions(256) { FullMode BoundedChannelFullMode.Wait, SingleReader true, SingleWriter false }); await channel.Writer.WriteAsync(job, cancellationToken); await foreach (Job next in channel.Reader.ReadAllAsync(cancellationToken)) await ProcessAsync(next, cancellationToken);下面的时序把有界Wait模式的压力传导、正常消费和关闭排空放在同一条时间线上。它表达的是 API 协议不规定 Channel 内部必须使用某种队列或唤醒结构。ConsumerChannelReaderBounded bufferChannelWriterProducerConsumerChannelReaderBounded bufferChannelWriterProducerloop[Drain buffered items]Canceling one wait does not complete the shared channelWriteAsync item ACommit item AData is availableRead item ADeliver item AWriteAsync item B while fullWait for capacityRead one buffered itemCapacity is availableCommit item BComplete or TryComplete errorClose the write sideReadAsyncDeliver next itemCompletion succeeds or faults关闭 writer 后仍可读取已提交的条目只有缓冲区排空后reader 才观察到最终完成或故障。某个WriteAsync/ReadAsync的取消只终止那次等待不替代管道所有者的关闭协议。有界不自动等于背压。当 FullMode 是Wait且生产者真的await WriteAsync时容量压力才会沿调用链向上游传播。如果生产者改用TryWrite后忽略 false那是丢弃。如果 FullMode 是 DropOldest、DropNewest 或 DropWrite那是按定义丢数据不是等待。每一种丢弃都必须有业务语义、指标与告警。SingleReader/SingleWriter是调用方对拓扑的承诺实现可用它们选择更简化路径。如果实际有多个写者却声明单写者就违反契约。AllowSynchronousContinuations也不是一个“加速”开关允许续体同步执行会改变调用栈、重入、延迟归属与锁交互必须根据完整管道审查。6.1 完成、故障和取消是三个维度写者完成表示不再有新数据读者仍应消费已缓冲数据然后观察正常完成或故障。取消某个读取等待不必然意味着 Channel 已完成也不会自动停止其他生产者。必须定义谁有权完成 writer多生产者如何协调最后完成故障是否终止全部管道关闭时是排空还是丢弃。常见错误是启动消费 Task 后忽略它。这会让 I/O 异常、取消和管道故障失去所有者。服务生命周期应保存消费 Task关闭时停止生产、完成 writer、等待消费者退出并对超时做明确处理。七、什么时候保留 BlockingCollectionBlockingCollectionT适合已有同步工作者线程且“无工作时阻塞该专用线程”是可接受设计的系统。它通过Add/Take、有界容量和CompleteAdding组织生产消费。但底层不必然是 FIFO默认常与并发队列配合也可传入其他IProducerConsumerCollectionT顺序由该集合决定。“新代码一律改 Channel”也太绝对。如果消费操作是长时间占用专用线程的同步原生 APIBlockingCollection 可以比为了形式上 async 而包装更直接。如果大量工作本身是异步 I/O阻塞线程等数据与等 I/O 则浪费线程Channel 更容易表达该生命周期。在 Unity 中需要格外小心大多数 UnityEngine API 只能从主线程调用。后台消费者可以解析纯数据、压缩或 I/O但创建 GameObject、修改 Transform 等操作需要通过明确的主线程提交边界。选 Channel 不会自动把续体调度到 Unity 主线程。八、容量、背压和过载策略任何长时间队列都应有容量理由。无界 Channel、普通 Queue 和无上限 BlockingCollection 都可以在生产长期快于消费时耗尽内存。“理论上消费者更快”不是容量证明因为发布停顿、下游 I/O 抖动、限流与故障会改变速率。容量可以从可接受等待时间与峰值生产率估算再用压测验证。例如容许缓冲 200 ms压力期生产速率为每秒 5,000 条初始容量估计可从 1,000 附近开始但还要纳入条目字节大小、消费抖动和恢复时间。这是建模示例不是所有系统的推荐容量。过载时可选策略包括等待上游拒绝并返回错误丢弃最新/最旧按键合并持久化到磁盘降级精度或扩展消费。日志可能允许丢弃低优先级条目支付命令则不应静默丢弃。策略必须属于业务协议不是底层类库默认值。九、完整案例异步日志不是“开个后台 Task”一个日志管道要先定义哪些日志可丢容量满时谁承担延迟写盘失败如何传播关闭时是否排空以及进程崩溃时允许丢失多少。DropOldest可能适合高频调试采样却会丢掉错误发生前的上下文Wait保留数据却可以把慢磁盘的延迟传回请求路径。消费者不应为每条日志都单独打开文件并AppendAllTextAsync。应明确持有 stream按数量或时间批量写入并定义 flush 与 fsync 需求。批处理减少 I/O 调用但增加崩溃时尚未持久的数据窗口这个窗口是产品指标不是只由程序员选一个“快”数字。管道还需要自观测当前长度或估算水位写入等待时间丢弃数消费速率批大小最旧条目延迟写盘错误与关闭耗时。Channel 本身不会替你建立这些指标。十、决策树需要处理的是一次性连续数据吗 ├─ 是考虑 Array/Span/ArrayPool不要伪装成队列。 └─ 否谁先处理 ├─ 最新上下文先 → StackT ├─ 最早到达者先 → QueueT └─ 按业务优先级 → PriorityQueueTElement,TPriority 生产和消费是否跨并发/异步边界 ├─ 否 → 优先普通容器在调度层控制帧预算。 └─ 是等待时是否应释放线程 ├─ 是 → ChannelT明确容量、FullMode、完成与取消。 └─ 否使用专用同步工作者 → BlockingCollectionT 或明确锁协议。 生产速率可能长期高于消费吗 ├─ 是 → 必须有界定义等待/拒绝/丢弃/合并/持久化策略。 └─ 否 → 仍需设定监控与故障上限不用“理论更快”代替证据。十一、测试与代码评审清单顺序是 FIFO、LIFO、优先级还是可丢弃的最新状态是否有单元测试锁定相同优先级是否需稳定顺序若需是否将唯一序号纳入 priority队列是否有显式容量、条目字节估算、最大等待和过载策略Channel FullMode 与WriteAsync/TryWrite组合的真实语义是什么丢弃是否被计数谁拥有完成 writer 的权力读端如何区分正常完成、故障和外部取消后台消费 Task 是否被保存和等待还是启动后丢失异常SingleReader/SingleWriter 选项是否与真实拓扑一致是否存在重入或多个消费者执行用户代码是否占用内部锁是否可能阻塞整个管道Unity 后台工作是否触及只能在主线程调用的引擎 API提交边界是否清楚压测是否包含稳态、短时突发、消费者停顿、故障、取消和关闭排空指标是否包含吞吐、P95/P99 延迟、队列水位、丢弃、分配和关闭时间目标 TFM/Unity BCL 是否真正提供该 API是否在 IL2CPP Player 或目标服务运行时执行过探针十二、本篇结论Stack、Queue 和 PriorityQueue 先解决顺序问题Channel 和 BlockingCollection 再解决生产消费的协调问题ArrayPool 则是与这两层正交的内存所有权工具。不应把它们放进一张只比“O(1) 还是 O(log n)”的榜单因为它们保证的语义不同。对单线程实时游戏循环普通容器、明确帧预算和可观测长度往往比引入异步管道更容易控制。对异步 I/O 和多生产者消费者Channel 的完成、错误、等待和有界 FullMode 能将协议变成可编程 API。对专用同步工作者BlockingCollection 仍可是直接选择。真正的上线门槛不是代码能入队和出队而是在消费者变慢、下游故障、取消和关闭时仍能说清数据去向、内存上限和错误所有者。能回答这些问题的容器和协议才是适合当前场景的选择。建议实验为同一生产消费任务构建有界 Channel 与 BlockingCollection 版本分别模拟稳态、突发、消费停顿与关闭比较的重点是线程占用、水位、尾延迟、丢弃和错误传播而不是一个脱离语义的每秒操作数。下一篇ArrayPool 与 MemoryPool 的所有权和复用边界。