队列<T> vs列表<T>

Question

我目前使用List<T>作为队列（使用lst[0]，然后lst.removeAt(0)）来保存对象。在给定的时间内最多约20个项目。我意识到有一个实际的Queue<T>类。我想知道是否有任何好处（性能，内存等）使用Queue<T>而不是List<T>充当队列？

Answer 1

性能可以分析。虽然在这种情况下，你可能需要运行代码数百万次才能真正获得有价值的差异。

我会这样说：Queue<T>会暴露你的意图更明确的人都知道队列是如何工作的。

像队列一样使用的列表不是很清楚，特别是如果你有很多不必要的索引和RemoveAt(magicNumber)代码。从代码维护的角度来看，Dequeue是更多的消费品。

如果这会给您带来可衡量的性能问题，您可以解决它。不要每个潜在的性能问题提前。

Answer 2

除了Queue<T>类实现队列和List<T>类实现列表这一事实之外，还存在性能差异。

每当您从List<T>中删除第一个元素时，都会复制队列中的所有元素。队列中只有20个元素可能不明显。但是，当您从Queue<T>中取出下一个元素时，不会发生这样的复制，并且总是会更快。如果队列很长，则差异可能很大。

Answer 3

我想强调HugoRune已经指出的内容。队列比列表快得多，在这个用例中，列表的内存访问是1对n。我有一个类似的用例，但我有数百个值，我将使用Queue，因为它的速度快了一个数量级。

有关队列正在List上实现的说明：关键是“已实施”。它不会在出队时将每个值复制到新的内存位置，而不是使用循环缓冲区。这可以在“列表顶部”完成，而不会受到直接使用List意味着的副本的处罚。

Answer 4

简短的回答：当它的使用就像一个队列
Queue<T>比List<T>更快。当像列表一样使用时，List<T>比Queue<T>更快。

龙答案：
甲Queue<T>为出队操作，这是一个O（1）的操作速度更快。整个数组的后续项目块不会向上移动。这是可能的，因为Queue<T>不需要从随机位置移除，而仅从顶部移除。所以它保持一个头（物品被拉到Dequeue）和尾部位置（物品被添加到Enqueue）。另一方面，从List<T>的顶部移除需要自己将每个后续项目的位置移动一个。这是O（n） - 最坏的情况是，如果你从顶层移除，这是一个出队操作。如果您在循环中出队，速度优势可以引人注目。

一个List<T>是更好的性能，如果你需要索引访问，随机检索等。Queue<T>将不得不枚举完全找到合适的索引位置（它不公开IList<T>）。

也就是说，Stack<T>与List<T>距离更近，在推动和弹出操作中没有性能差异。它们都推动结束并从数组结构中移除（两者都是O（1））。

---

当然，你应该使用正确的结构，揭示了意向。在大多数情况下，它们的表现会更好，因为它们是为此目的而量身定制的。我相信根本没有任何性能差异，微软不会仅仅在框架中包含Queue<T>和Stack<T>仅仅是不同的语义。如果是这样的话，它本来就容易扩展。考虑SortedDictionary<K, V>和SortedList<K, V>，两者都完全相同，但仅通过性能特征进行区分;他们在BCL中找到了一席之地。