隊列<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中找到了一席之地。