IndexedQueue<T> - C# 中的自定义队列

• 下载源代码 - 7.5 KB

引言

Microsoft 提供了 Queue<T> 类，但尽管它是有序的，但它并不提供对其元素的索引访问。由于我需要一个允许通过索引进行高效访问的队列，所以我使用一个由数组支持的可增长循环缓冲区重新实现了队列。这与 Microsoft 的实现方式类似。主要的区别在于我的类暴露了更多一点的功能。这个类非常专业化，但当你需要它时，你*真的*需要它，所以我在这里提供它。我将其用于我的回溯解析器中，作为前瞻缓冲区。

注意：我最初将这个类命名为 Queue<T>，因为这是它的最佳名称，但我将其更改为避免与 Microsoft 的队列冲突。项目名称和文件夹名称反映了旧名称，但类和源文件已使用新名称更新。

Using the Code

使用该代码就像使用 Microsoft 的 Queue<T> 中的代码一样，只是增加了一个索引器属性。我没有实现 IList<T> 的原因是实现 Insert() 并非易事，并且在这一点上，该容器在功能上基本上变成了双端队列，这是一种完全不同的数据结构。我可能会稍后发布一个。

演示代码非常容易理解

var q = new IndexedQueue<int>(1);
Console.WriteLine("Enqueuing 1..20");
for (var i = 0; i < 20; ++i)
    q.Enqueue(i + 1);

Console.WriteLine("Dequeuing 1..10");
for (var i = 0; i < 10; ++i)
    Console.Write("{0} ",q.Dequeue());
Console.WriteLine();

Console.WriteLine("Enqueuing 21..40 (force array wrap)");
for (var i = 0; i < 20; ++i)
    q.Enqueue(i + 21);

Console.WriteLine("Enumerating");
foreach (var i in q)
    Console.Write("{0} ", i);
Console.WriteLine();

Console.WriteLine("Removing 34 (middle of array)");
(q as System.Collections.Generic.ICollection<int>).Remove(34);

Console.WriteLine("Enumerating");
foreach (var i in q)
    Console.Write("{0} ", i);
Console.WriteLine();

Console.WriteLine("Removing 32 (end of array)");
(q as System.Collections.Generic.ICollection<int>).Remove(32);

Console.WriteLine("Enumerating");
foreach (var i in q)
    Console.Write("{0} ", i);
Console.WriteLine();

实现起来相当简单，但从中间移除（对于 ICollection<T>）有点棘手。

无论如何，如果你需要它，它就在这里。大多数人可能永远不需要它，但这就是它。

历史

• 2019年12月12日 - 首次提交