循環隊列的缺點？

最近在接受採訪時我被問到使用循環隊列的缺點。我想不出任何。在互聯網上搜索我發現的唯一答案是難以實現比線性隊列:)。還有其他的缺點嗎？循環隊列的缺點？

根據實現情況，您可能必須在循環隊列中將節點留空，而可以完全填充線性隊列。沒有太大的缺點，除非每個節點都是巨大的！ – asheeshr 2013-02-16 06:15:02

爲什麼節點必須留空？ – 2013-02-16 08:11:27

這取決於你如何實現循環隊列。如果您將數據存儲在每個節點中，則沒有簡單的方法來區分空列表和完整列表。 – asheeshr 2013-02-16 08:14:29

在我看來，那是穿越隊列將必須跟蹤的第一個節點，以檢測橫向結束的任何代碼。但是在多線程環境中，另一個線程可能會刪除第一個節點，這會導致遍歷線程進入無限循環。所以遍歷線程必須保持第一個節點在隊列週期內被鎖定。

2013-02-16 06:35:21

然後再次，在枚舉過程中通常會使用任何列表。例如，常規鏈表的尾部可能會被刪除並移動到頭部（在處理隊列時並不罕見），這可能會破壞迭代器。 – nneonneo 2013-02-16 06:39:21

在多個進程之間共享內存的情況下不會發生這種情況嗎？我問你是否明確提到*線程* – asheeshr 2013-02-16 06:40:11

@AshRj是的，它肯定會發生在多個進程中。 – 2013-02-16 14:47:06

我要說的循環隊列的最大缺點是隻能存儲queue.length元素。如果您將它用作緩衝區，則會限制您的歷史深度。

另一個小缺點是很難分辨一個完整的隊列空隊列，不保留其他信息。

2013-09-16 02:28:21 Justin

不那麼難。查看問題的評論。至少有兩種方法可以做到這一點...... – 2017-12-31 04:51:35

面試官在尋找可能的答案取決於一些額外的背景下，是不是在上面的問題。

例如，高度併發的生產者/消費者系統通常考慮循環隊列。當隊列滿時，隊列前後的操作可以爭用相同的緩存行，這可能會導致類似上下文中的問題。

也許面試官要你來談談它是多麼容易在一個垃圾收集的語言，使無鎖連接隊列成具有圓形基於陣列的隊列進行比較。

或者，也許這只是你如何能夠更好地利用，如果你使用線性隊列週期性轉移，而不是一個循環隊列通過您的語言提供的矢量容器。

2017-12-31 04:51:23

回答