C# 中的栈、队列和优先级队列

Stack`List`Queue和PriorityQueue`Data` 是 C# 中用于高效存储、组织和管理数据的基本数据结构。
它们不仅有助于解决算法难题，而且在实际应用中也极其重要，例如在不同的工作流中进行搜索、任务排序、数据插入、删除和更新等操作。
本文将介绍每种数据结构的主要特性，解释其工作原理，并展示实际应用场景，以帮助读者加深记忆和理解。
那么，让我们开始探讨 C# 中的这些重要数据结构吧。

堆

AStack代表一个后进先出 ( LIFO
) 集合。这意味着最后添加的元素将最先被移除。

构造函数

构造函数	描述
`Stack()`	创建一个空栈。
`Stack(int capacity)`	创建一个具有初始内部容量的堆栈。当已知预期大小时非常有用。
`Stack(IEnumerable collection)`	创建一个堆栈，其中项目是从另一个集合复制的（最后一个元素成为顶部）。

核心运营

成员	描述	例子
`Push(T item)`	将物品添加到顶部	`stack.Push(\"A\");`
`Pop()`	移除并返回最顶层元素。如果为空则抛出异常。	`var item = stack.Pop();`
`Peek()`	返回顶部元素，但不将其移除。如果为空，则抛出异常。	`var item = stack.Peek();`
`TryPop(out T result)`	安全弹出（如果为空则返回 false）	`if(stack.TryPop(out var value)){...}`
`TryPeek(out T result)`	安全查看（如果为空则返回 false）	`if(stack.TryPeek(out var value)){...}`

实用方法

成员	描述
`Count`	栈中元素的数量
`Clear()`	移除所有物品
`Contains(T item)`	检查堆栈中是否包含给定的元素
`ToArray()`	返回一个按后进先出 (LIFO) 顺序排列的新数组
`GetEnumerator()`	遍历栈（栈顶→栈底）
`TrimExcess()`	多次删除后降低内存占用。

例子

    Stack stack = new();

    stack.Push(\"First\");

    stack.Push(\"Second\");

    stack.Push(\"Third\");

    Console.WriteLine(\"Top of the stack: \" + stack.Peek());

    Console.WriteLine(\"Removing items:\");

    while (stack.Count > 0)

        Console.WriteLine(stack.Pop());

    Console.WriteLine(\"Stack empty? \" + (stack.Count == 0));

输出

Top of the stack: ThirdRemoving items:ThirdSecondFirstStack empty? True

队列

AQueue表示一个FIFO（先进先出）集合。
第一个插入的元素也是第一个被移除的元素。

构造函数

构造函数	描述
`Queue()`	创建一个空队列。
`Queue(int capacity)`	创建一个具有预定义容量的队列。
`Queue(IEnumerable collection)`	初始化一个包含元素的队列，其中第一个元素成为队列的队首。

核心运营

成员	描述	例子
`Enqueue(T item)`	在背面（尾部）添加物品。	`queue.Enqueue(\"A\");`
`Dequeue()`	移除并返回最前面的物品。如果为空则抛出异常。	`var item = queue.Dequeue();`
`Peek()`	退回前面的物品，无需将其移除。	`var item = queue.Peek();`
`TryDequeue(out T result)`	安全出队	`if(queue.TryDequeue(out var x)) { ... }`
`TryPeek(out T result)`	安全偷窥	`if(queue.TryPeek(out var x)) { ... }`

实用方法

成员	描述
`Count`	元素数量
`Contains(T item)`	检查该物品是否存在
`ToArray()`	按先进先出 (FIFO) 顺序退回物品
`Clear()`	移除所有元素
`GetEnumerator()`	遍历队列头部 → 尾部
`EnsureCapacity(int capacity)`	确保足够的内部存储空间，避免调整大小
`TrimExcess()`	减少未使用的内存

代码：

Queue queue = new();queue.Enqueue(\"First\");queue.Enqueue(\"Second\");queue.Enqueue(\"Third\");Console.WriteLine(\"Front of the queue: \" + queue.Peek());Console.WriteLine(\"Processing queue:\");while (queue.Count > 0)

    Console.WriteLine(queue.Dequeue());Console.WriteLine(\"Queue empty? \" + (queue.Count == 0));

输出

Front of the queue: FirstProcessing queue:FirstSecondThirdQueue empty? True

优先级队列

APriorityQueue类似于队列，不同之处在于元素移除基于优先级而非插入顺序。
默认情况下，它的行为类似于最小堆（优先级值越低，优先级越高）。

类型：

PriorityQueue

TElement→ 你存储的值
TPriority→ 决定处理顺序（默认情况下，数字越小优先级越高）

构造函数：

承包商	描述
`PriorityQueue()`	创建一个空的优先级队列
`PriorityQueue(int initialCapacity)`	预先分配容量以减少调整规模
`PriorityQueue(IEnumerable items)`	创建包含指定项的队列
`PriorityQueue(IEnumerable items, IComparer? priorityComparer)`	相同，但允许自定义优先级逻辑

核心方法

成员	描述	例子
`Enqueue(TElement element, TPriority priority)`	添加一个元素及其优先级	`queue.Enqueue(\"Task\", 2);`
`Dequeue()`	移除并返回优先级最高的元素	`var item = queue.Dequeue();`
`Peek()`	返回优先级最高的元素，而不进行移除操作。	`var item = queue.Peek();`
`TryDequeue(out TElement element, out TPriority priority)`	安全出队	`if(queue.TryDequeue(out var e, out var p)) {...}`
`TryPeek(out TElement element, out TPriority priority)`	安全偷窥	`if(queue.TryPeek(out var e, out var p)) {...}`

实用方法

成员	描述
`Count`	物品数量
`Clear`	移除所有元素
`EnsureCapacity(int capacity)`	预先分配内存
`TrimExcess()`	减少内存占用
`EnqueueDequeue(element, priority)`	插入项目，然后移除优先级最高的项目。
`UnorderedItems`	退回内部物品，顺序不限

代码：

PriorityQueue queue = new();queue.Enqueue(\"Fix critical bug\", 1);queue.Enqueue(\"Team meeting\", 2);queue.Enqueue(\"Review PR\", 3);Console.WriteLine($\"Count: {queue.Count}\");Console.WriteLine($\"Peek: {queue.Peek()}\");if (queue.TryDequeue(out string? task, out int priority))

    Console.WriteLine($\"Dequeued: {task} (Priority {priority})\");queue.EnqueueRange([

    (\"Refactor service\", 4),

    (\"Write documentation\", 5)]);string removed = queue.EnqueueDequeue(\"Urgent hotfix\", 0);Console.WriteLine($\"Removed during EnqueueDequeue: {removed}\");Console.WriteLine(\"nRemaining items by priority:\");while (queue.TryDequeue(out string? t, out int p))

    Console.WriteLine($\"→ {t} (p={p})\");queue.TrimExcess();

输出

Count: 3Peek: Fix critical bugDequeued: Fix critical bug (Priority 1)Removed during EnqueueDequeue: Urgent hotfixRemaining items by priority:→ Team meeting (p=2)→ Review PR (p=3)→ Refactor service (p=4)→ Write documentation (p=5)

将优先级队列转换为最大堆

要在优先级队列中返回最大值而不是最小值，您可以创建一个自定义比较器：

var queue = new PriorityQueue( comparer: Comparer.Create((x, y) => y.CompareTo(x)));

例子：

var queue = new PriorityQueue( comparer: Comparer.Create((x, y) => y.CompareTo(x)));queue.Enqueue(\"Low importance\", 1);queue.Enqueue(\"Medium importance\", 5);queue.Enqueue(\"High importance\", 10);while (queue.TryDequeue(out string? task, out int priority))

    Console.WriteLine($\"{task} (priority {priority})\");

High importance (priority 10)Medium importance (priority 5)Low importance (priority 1)

栈、队列和优先级队列（快速比较）

结构	订单规则	核心运营	示例用例
堆	LIFO（后进先出）	推/弹/尿	撤销系统、调用栈、DFS
队列	先进先出 (FIFO)	入队/出队/查看	调度、任务处理、广度优先搜索
优先级队列	基于优先级的排序	入队(元素，优先级) / 出队	工作调度、人工智能路径规划、医院分诊

真实案例

Stack – 撤销历史记录

在文本编辑器中输入内容时，每个操作都会被添加到历史记录栈中。
如果用户按下撤销按钮，我们会弹出最后一个操作。

var undoStack = new Stack();Type(\"Hello\");Type(\"Hello World\");Type(\"Hello World!\");Undo(); // removes \"Hello World!\"Undo(); // removes \"Hello World\"return;void Undo(){

    if (undoStack.TryPop(out string? lastAction))

        Console.WriteLine($\"Undo → removed: {lastAction}\");}void Type(string text){

    undoStack.Push(text);

    Console.WriteLine($\"Typed: {text}\");}

队列 – 打印队列

打印队列（打印机按到达顺序处理作业）

var printQueue = new Queue();AddPrintJob(\"Report.pdf\");AddPrintJob(\"Invoice.docx\");AddPrintJob(\"Presentation.pptx\");ProcessNextJob(); // ReportProcessNextJob(); // InvoiceProcessNextJob(); // Presentationreturn;void ProcessNextJob(){

    if (printQueue.TryDequeue(out string? job))

        Console.WriteLine($\"Printing: {job}\");}void AddPrintJob(string document){

    printQueue.Enqueue(document);

    Console.WriteLine($\"Added: {document}\");}

PriorityQueue – 医院急诊室分诊

医院急诊室分诊：
病人不是按到达顺序就诊，而是按病情严重程度就诊。

var erQueue = new PriorityQueue(

    comparer: Comparer.Create((a, b) => a.CompareTo(b)) // lower value = higher priority);erQueue.Enqueue(\"Head trauma\", 1);erQueue.Enqueue(\"Broken arm\", 4);erQueue.Enqueue(\"High fever\", 3);erQueue.Enqueue(\"Cardiac arrest\", 0);Console.WriteLine(\"Patients being treated:\");while (erQueue.TryDequeue(out string? patient, out int severity))

    Console.WriteLine($\"{patient} (severity {severity})\");