任何隊列優於循環隊列的用例？

Question

循環隊列顯然更好，因爲它幫助我們使用彈出元素留下的空白區域。它還節省了每次彈出後可能用於元素橫向移動的時間。

但是有沒有比使用循環隊列優先考慮隊列的用例呢？

Queue =的定義我們將使用線性數組實現。遵循FIFO並且不覆蓋

Circular Queue = Ring Buffer Implementation的定義。遵循FIFO。不會覆蓋。

Answer 1

注意：在很多語言中，queue只是一個接口，並沒有提到任何關於實現的內容。

當使用基於數組的循環隊列，又名環形緩衝區時，您必須處理您推入完整緩衝區的情況。你可以：

1. 忽略插入
2. 覆蓋最早的條目
3. 的位置，直到有空間再
4. （重新）分配內存和複製所有的內容
5. 使用一個超大的緩衝區，所以這種情況下，從未發生

這些選項都有缺點。如果你能和他們一起生活，或者你知道永遠不會填滿緩衝區，那麼環形緩衝區就是要走的路。

選項3 & 4會導致口吃。根據您的使用情況，您可能更喜歡較長但穩定的訪問時間和可靠性，而不是偶爾會出現峯值，因此選擇linked list或其他類型的動態實現，如deque。

例用例的任務，你必須達到一個穩定的幀/採樣率和吞吐量，你不能忍受斷斷續續，如：

• 實時視頻和音頻處理
• 實時渲染
• 聯網
• 線程池當您不希望線程在推送新作業時阻塞時間過長。

但是，基於線性陣列的隊列將遭受同樣的負面影響。我沒有看到在循環隊列中選擇線性隊列的原因。
（除了稍高實現複雜度。）

std::queue在C++使用一個deque作爲默認墊層容器。 deque本質上是一個動態數組數組，它​​似乎是大多數用例的一個很好的基礎，因爲它以小塊分配內存，因此會導致更少的口吃。