C# Queue 队列：Enqueue、Dequeue、Peek 与 TryDequeue

Queue<T> 就像柜台前排的队：最先加入的元素最先被取出（FIFO，先进先出）。用 Enqueue 在队尾添加，用 Dequeue 从队首取出，两者都是常数时间。

Enqueue、Dequeue 和 Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var printJobs = new Queue<string>();
        printJobs.Enqueue("invoice.pdf");
        printJobs.Enqueue("photo.png");
        printJobs.Enqueue("report.docx");

        Console.WriteLine("Waiting: " + printJobs.Count);
        Console.WriteLine("Next up: " + printJobs.Peek()); // look, do not remove

        string job = printJobs.Dequeue();                   // remove the front
        Console.WriteLine("Printing " + job);
        Console.WriteLine("Next up: " + printJobs.Peek());

        while (printJobs.Count > 0)
        {
            Console.WriteLine("Printing " + printJobs.Dequeue());
        }
        Console.WriteLine("Waiting: " + printJobs.Count);
    }
}

输出：

Waiting: 3
Next up: invoice.pdf
Printing invoice.pdf
Next up: photo.png
Printing photo.png
Printing report.docx
Waiting: 0

Peek 用来在真正处理下一个元素之前先看看它是什么；Dequeue 则是真正取走它。用 while (queue.Count > 0) 循环一直出队直到队列为空，是处理队列的标准写法。即使循环体里又有新元素入队，这种写法也照样有效，而 foreach 不允许这样做。

空队列异常与 TryDequeue

对空队列调用 Dequeue 和 Peek 会抛出 InvalidOperationException。即使是引用类型，也不会出现“队列为空时返回 null”这种行为。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tickets = new Queue<int>();

        try
        {
            tickets.Dequeue();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        tickets.Enqueue(41);
        tickets.Enqueue(42);

        int ticket;
        while (tickets.TryDequeue(out ticket))
        {
            Console.WriteLine("Serving ticket " + ticket);
        }

        Console.WriteLine(tickets.TryPeek(out ticket)); // false: empty
    }
}

输出：

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue 和 TryPeek 在有元素时返回 true 并给 out 变量赋值，队列为空时返回 false。它们从 .NET Core 2.0 开始提供；在较老的 .NET Framework 代码中，请在调用 Dequeue 之前先检查 Count > 0。

查看队列里的内容

队列可以在不移除任何元素的情况下被枚举。foreach、ToArray 和 Contains 都会从队首到队尾依次看到这些元素。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var line = new Queue<string>(new[] { "Ana", "Ben", "Chloe" });

        foreach (string name in line)
        {
            Console.Write(name + " ");
        }
        Console.WriteLine();

        Console.WriteLine(line.Contains("Ben"));
        string[] snapshot = line.ToArray();
        Console.WriteLine(snapshot[0] + " is first, " + snapshot.Length + " in line");
        Console.WriteLine(line.Count); // nothing was removed
    }
}

输出：

Ana Ben Chloe 
True
Ana is first, 3 in line
3

队列没有索引：line[1] 无法编译，你也不能从中间移除元素。如果你需要这两种操作，那这些数据其实并不是队列，请改用 List<T> 或 LinkedList<T>。和其他集合一样，在对同一个队列的 foreach 中入队或出队，会抛出 InvalidOperationException。

用队列实现广度优先搜索

队列的顺序正是广度优先搜索所需要的：先访问一步之内的所有节点，再访问两步之内的，依此类推。下面的例子在一个小型社交网络中，找出 Ana 和其他每个人之间隔了几层关系：

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var friends = new Dictionary<string, string[]>
        {
            ["Ana"] = new[] { "Ben", "Chloe" },
            ["Ben"] = new[] { "Ana", "Dev" },
            ["Chloe"] = new[] { "Ana", "Dev", "Eli" },
            ["Dev"] = new[] { "Ben", "Chloe", "Fay" },
            ["Eli"] = new[] { "Chloe" },
            ["Fay"] = new[] { "Dev" },
        };

        var distance = new Dictionary<string, int> { ["Ana"] = 0 };
        var queue = new Queue<string>();
        queue.Enqueue("Ana");

        while (queue.Count > 0)
        {
            string person = queue.Dequeue();
            foreach (string next in friends[person])
            {
                if (!distance.ContainsKey(next))
                {
                    distance[next] = distance[person] + 1;
                    queue.Enqueue(next);
                }
            }
        }

        foreach (var pair in distance)
        {
            Console.WriteLine(pair.Key + ": " + pair.Value + " step(s) from Ana");
        }
    }
}

输出：

Ana: 0 step(s) from Ana
Ben: 1 step(s) from Ana
Chloe: 1 step(s) from Ana
Dev: 2 step(s) from Ana
Eli: 2 step(s) from Ana
Fay: 3 step(s) from Ana

每个人只在第一次被访问到时入队一次。因为队列按发现的先后顺序把他们交还回来，所以第一次访问到时走的一定是最短路径。把队列换成 Stack，同样的循环就变成了深度优先搜索，也就不再能找到最短路径了。

同样的结构还可以用来做树的层序遍历、网格上的洪水填充以及链接爬取：先往队列里放一个元素，只要队列不为空，就出队一个元素，再把它尚未访问过的邻居入队。

用 Queue 还是 List 做先进先出

你可以用 Add 和 RemoveAt(0) 把 List<T> 当作队列使用，但 RemoveAt(0) 会把剩下的每个元素都向前挪一格。用这种方式清空一个有 100,000 个元素的列表，大约要移动五十亿次元素；而 Queue<T> 只需要 100,000 次常数时间的操作。队列的内部是一个环形缓冲区：它在数组中记录队首和队尾两个索引，只有在数组满了时才重新分配。

多线程下使用 ConcurrentQueue

Queue<T> 不是线程安全的。当多个线程同时添加或取出元素时，请使用 System.Collections.Concurrent 中的 ConcurrentQueue<T>。它提供 Enqueue、TryDequeue 和 TryPeek，但没有 Dequeue，因为在有其他线程存在的情况下，“先检查 Count 再 Dequeue”可能会在两次调用之间失败。

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        var events = new ConcurrentQueue<int>();

        // 4 parallel iterations each add 1,000 items.
        Parallel.For(0, 4, worker =>
        {
            for (int i = 0; i < 1000; i++) events.Enqueue(i);
        });
        Console.WriteLine(events.Count);

        int total = 0;
        int item;
        while (events.TryDequeue(out item)) total++;
        Console.WriteLine(total + " processed");
    }
}

输出：

4000
4000 processed

如果把 ConcurrentQueue<T> 换成普通的 Queue<T>，根据线程执行时机的不同，计数结果会出错，或者程序直接抛出异常。如果生产者线程和消费者线程需要等待任务到来，而不是空转，可以使用 BlockingCollection<T>（默认包装一个 ConcurrentQueue<T>）或 System.Threading.Channels，它们提供了阻塞和完成通知。手动保护普通集合的方法见 lock。

PriorityQueue

当元素应该按优先级而不是到达顺序离开时（最紧急的工单先处理，Dijkstra 算法中先取当前最短的路径），.NET 6 及以后版本提供了 PriorityQueue<TElement, TPriority>。优先级数值最小的元素最先出队：

var triage = new PriorityQueue<string, int>();
triage.Enqueue("sprained ankle", 3);
triage.Enqueue("chest pain", 1);
triage.Enqueue("headache", 5);

while (triage.TryDequeue(out string patient, out int priority))
{
    Console.WriteLine($"{priority}: {patient}");
}
// 1: chest pain
// 3: sprained ankle
// 5: headache

优先级相同的元素出队顺序不固定；如果需要按到达顺序来决定先后，可以在优先级里加上一个序号。

常见错误

• 出队前不做检查。 空队列会抛出 InvalidOperationException；用 Count > 0 作为循环条件，或者使用 TryDequeue。
• 调用 Peek 后以为元素已经被移除。 只有 Dequeue 才会移除元素。
• 在遍历队列的 foreach 中入队。 会抛出异常；改用 while 循环来处理。
• 在多个线程间共享 Queue<T>。 使用 ConcurrentQueue<T> 或加锁。
• 在大量数据上用 List.RemoveAt(0) 充当队列。 每次调用都是 O(n)。