隊列的兩種常見實現之間有什麼區別？

Question

在Java中，隊列的一個實現是「圓形陣列」，另一個是「鏈接列表」。它們有什麼不同？

Answer 1

在他們是如何使用的術語，幾乎沒有任何區別可言，當你到了隊列的大小限制，除了（我將在幾秒鐘之解釋......）

由於出於其他考慮：

• 鏈表的方法是有利的，因爲可以動態調整隊列，沒有額外的努力 - 這是鏈表的基礎。當然，這可以通過重新分配一個數組來複制，但這並不是最簡單的方法。

• 另外，在鏈表中，沒有未使用的內存：在圓形數組方法中，如果隊列的大小小於數組的最大容量，則會出現「空槽」。但是，這並不意味着鏈表是更多的內存效率，這是因爲：

• 圓形陣列方式的優點是沒有開銷。鏈表中的每個節點都需要存儲對下一個節點的引用 - 如果列表變大，這會加起來。另一方面，循環數組只是您通過索引訪問的內存塊，因此沒有開銷。

有贊成的和反對的每種方法，但實際上，它涉及到的具體情況它用在...除非你使用隊列沒有結束，它可能不會太大的差異。

Answer 2

正常情況下，圓陣的實現是在重複使用的內存稍微好一點，但運行有如果有太多的項目添加到隊列增長的風險 - 可能持有過多的內存，如果正常的存儲和最大存儲容量是在實踐中太不同了。

鏈表更靈活，但一般涉及到更多的垃圾回收。

在實踐中，我認爲我會感到驚訝，如果你發現你的代碼的瓶頸取決於這個選擇 - 無論使用哪一個似乎是最直觀的給你。

Answer 3

大約與ArrayList和LinkedList之間的差異相同。

• 對於數組，您需要估計隊列有多大才能獲得，因爲您需要爲其分配存儲空間。但是做到這一點，當接近容量時它更緊湊。 「自由點」仍然佔用陣列中的空間，而他們在LinkedList中沒有這樣做。

• 對於鏈表，很容易拆卸和從中間添加元素（儘管這不應該在所有需要的隊列）。

• 數組是隨機存取，這意味着你可以迅速得到該元素的位置x。同樣，這個特性在隊列中是沒有用的，但是。

Answer 4

作爲鏈表實現不具有固定尺寸的隊列，而一個爲圓形陣列實現，又名ring buffer，典型地具有固定大小（雖然這將有可能使一個調整大小，很多ArrayList調整的方式）。

鏈表實現使用每個元素更多的內存，但數組實現需要更多的連續內存。隨着元素數量變得非常大，這兩個問題確實只是一個重大問題。

向圓形陣列實現添加/刪除元素非常便宜，因爲它只涉及調整計數器和設置引用，而鏈接列表實現必須在添加時分配元素，並在刪除時導致GC開銷。

Answer 5

編寫代碼，使其僅使用接口，但創建隊列除外。然後很容易切換實現。

爲一個開始選擇一個實現。我通常會使用數組變量（例如ArrayList），因爲它們更小，並且在今天的計算機上往往會稍微快一點，我認爲這是由於緩存（我只是做了一點基準，通過10000個元素隊列推送10000000個元素，〜 ArrayBlockingQueue爲8.3s，LinkedBlockingQueue爲10-11s）。如果我需要索引訪問，我也會使用數組變量。只有在列表或隊列中間有很多插入/刪除的情況下，我才選擇鏈接列表變體。

如果您遇到性能問題並且分析顯示隊列是瓶頸（這不太可能），那麼應使用隊列的兩個實現進行基準測試並選擇更好的隊列。