25. HashSet/Queue/Stack

数组、List、字典解决的是”存取”问题。但有些场景的关注点不是”存了什么值”，而是”怎么进出”或”有没有重复”。这章三种集合各管一摊：HashSet 管唯一、Queue 管排队、Stack 管回退。

HashSet：只留不重复

HashSet<T> 是一组不重复的元素，内部用哈希表实现，增删查都很快（平均 O(1)）。它不保证任何顺序。

HashSet<int> numbers = [];
numbers.Add(1);
numbers.Add(2);
numbers.Add(1);   // 重复，被忽略
foreach (var n in numbers) Console.Write($"{n} ");
// 输出：1 2

HashSet 的集合运算

它原生支持并集、交集、差集等集合运算，方法名很直观，适合做”权限合并""差异对比”之类的事。

HashSet<int> a = [1, 2, 3];
HashSet<int> b = [3, 4, 5];
a.UnionWith(b);          // 并集，a 变成 1 2 3 4 5
Console.WriteLine(string.Join(", ", a));

除了 UnionWith（并集），还有 IntersectWith（交集，只留两边都有的）、ExceptWith（差集，去掉对方也有的）、SymmetricExceptWith（对称差，只留各自独有、去掉共有）。

HashSet<int> x = [1, 2, 3];
HashSet<int> y = [2, 3, 4];
x.IntersectWith(y);
Console.WriteLine(string.Join(", ", x)); // 2 3

还可以用 IsSubsetOf（是不是子集）、IsSupersetOf（是不是超集）、SetEquals（两集合是否完全相同）做包含关系判断。

HashSet 与字典去重怎么选

上一章我们用字典键去重，其实专为去重而生的是 HashSet。区别是：字典去重时还能顺带挂一个 value（比如”出现过几次”）；HashSet 只关心”在不在”，更轻量、语义更清楚。只想去重、不要附带数据，一律用 HashSet。

int[] raw = [1, 2, 2, 3, 3, 3];
HashSet<int> unique = [.. raw];   // 集合表达式展开即去重
foreach (var n in unique) Console.Write($"{n} "); // 1 2 3

Queue：先进先出

队列（queue）像排队买票，先来的先走。入队叫 Enqueue，出队叫 Dequeue。

Queue<string> queue = [];
queue.Enqueue("甲");
queue.Enqueue("乙");
queue.Enqueue("丙");
while (queue.Count > 0)
{
    Console.WriteLine(queue.Dequeue());   // 甲、乙、丙 依次出队
}

Stack：后进先出

栈（stack）像一摞盘子，最后放上去的先被拿走，即 LIFO。压栈叫 Push，弹栈叫 Pop。

Stack<string> stack = [];
stack.Push("甲");
stack.Push("乙");
stack.Push("丙");
while (stack.Count > 0)
{
    Console.WriteLine(stack.Pop());   // 丙、乙、甲 依次弹出
}

三者怎么选

• 要去重、判断某元素在不在 → HashSet<T>
• 要按顺序处理、先到先得（如打印队列、消息排队）→ Queue<T>
• 要后来居上、支持回退（如浏览器后退、撤销）→ Stack<T>

生活化的类比

• HashSet：班级的”已签到名单”，同一个人签两次也只算一次。
• Queue：食堂排队，先排先打饭。
• Stack：摞起来的盘子，每次只能取最上面那一个。

一个综合小例子

把数字先入队、再压栈，能直观看出顺序变化：队列保证入队顺序，栈把它整体反了过来。

Queue<int> q = [];
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);

Stack<int> s = [];
while (q.Count > 0) s.Push(q.Dequeue());

while (s.Count > 0) Console.Write($"{s.Pop()} "); // 3 2 1

Queue 与 Stack 的常见真实场景

这两个结构看似简单，却是很多算法和系统的基础：

• **广度优先搜索（BFS）**用队列：从起点一层层向外扩，先发现的节点先处理。
• **深度优先搜索（DFS）**用栈（或递归，递归本质也是栈）：一条路走到黑，再回退。
• 撤销/重做用栈：每步操作压栈，撤销就弹出。
• 缓冲区/限流用队列：请求来了先排队，按能力慢慢消费。

容量与转换

这三种集合也能和数组互转：ToArray() 把它们变成数组，[.. set] 这类集合表达式又能把数组灌回来。

HashSet<int> unique = [3, 1, 2];
int[] arr = unique.ToArray();
Console.WriteLine(string.Join(", ", arr));

与 List 的对比

集合	进出规则	能不能按索引取	能不能重复
List<T>	任意增删、按索引	能	能
HashSet<T>	只关心唯一	不能	不能
Queue<T>	队首出、队尾进	不能	能
Stack<T>	栈顶进出	不能	能

把这张表记熟，选集合就不纠结了：要下标访问选 List，要去重选 HashSet，要排队伍选 Queue，要回退选 Stack。

HashSet 实战：给一批标签去重

去重是 HashSet 最日常的本事。比如一篇文章带了一堆标签，其中可能有重复，存库前先过一遍 HashSet：

string[] tags = ["C#", "dotnet", "C#", "编程", "dotnet"];
HashSet<string> uniqueTags = [.. tags];
Console.WriteLine($"共 {uniqueTags.Count} 个不重复标签：");
foreach (var t in uniqueTags) Console.Write($"{t} ");
// 共 3 个不重复标签：C# dotnet 编程

也可以拿它做”权限集合”：把用户拥有的权限放进 HashSet，判断某项权限只要 Contains，O(1) 搞定。

用 Queue 模拟任务处理

队列很适合做”生产者-消费者”的雏形：一边往里塞任务，另一边按顺序取出来处理。

Queue<string> tasks = [];
tasks.Enqueue("发邮件");
tasks.Enqueue("生成报表");
tasks.Enqueue("备份数据");

while (tasks.Count > 0)
{
    string job = tasks.Dequeue();
    Console.WriteLine($"正在处理：{job}");
}
// 依次：发邮件 → 生成报表 → 备份数据

这种”先来先处理”的公平语义，是队列区别于栈的根本。

常见坑与注意事项

1. Dequeue/Pop 在空集合上会抛异常：务必先用 Count > 0 判断，或用 TryDequeue/TryPop 安全版本。
2. HashSet 顺序不定：别依赖遍历顺序，需要有序就排序。
3. 队列和栈允许重复值：把同一任务反复入队是允许的，语义上和 HashSet 完全不同。
4. Peek 只看来不出来：想消费元素请用 Dequeue/Pop，别一直 Peek 卡在队首。

HashSet 的底层与性能再聊

HashSet 内部和字典一样用哈希表，所以 Add、Contains、Remove 平均都是 O(1)。它比”先 Contains 再 Add”的手写去重快，也比把数据塞进 List 再 Distinct 更直接——尤其当你需要反复判断”这个元素在不在”时，HashSet 的优势最明显。

不过代价是：哈希表要预留桶空间，内存占用比 List 略高；而且遍历顺序不可预测。所以”要唯一 + 常判断存在”用 HashSet，“要保序 + 偶尔去重”用 List 配合 LINQ 的 Distinct 更合适。

三种集合的线程安全

和 List 一样，HashSet、Queue、Stack 都不是线程安全的：多个线程同时改，可能破坏内部结构。如果在多线程里要用队列，.NET 提供了 ConcurrentQueue<T>（线程安全队列），它的 Enqueue/TryDequeue 可以放心并发调用。初学阶段大多单线程，先记住”这些基础集合别跨线程乱改”即可，真碰到并发场景再换并发版本。

小结

这三种集合都不按”索引”访问，而是按各自规则工作。HashSet 管唯一性，Queue 管公平排队，Stack 管后进先出。理解它们的语义，才能在正确场景用对工具。下章我们专门讲 C# 12 的集合表达式，看看 [...] 如何让创建各种集合都更顺手。