循環隊列理論

Question

我需要幫助理解循環隊列概念。我在stackoverflow上閱讀了一篇文章，沒有一個答案正在回答我遇到的心理障礙。

例如說我在一個圓形隊列中有8個單元格。

 Head        Tail 
empty|U | I | S | K | M | empty | empty 

說我插入兩個字符˚F& P，這將令隊列變化。

Tail Head         
empty|U | I | S | K | M | F | P 

現在讓我們讓事情變得有趣，如果我刪除3個條目。

Tail         Head     
empty| empty | empty | empty | K | M | F | P 

很明顯，我的頭和尾現在已經改變，我有3個新的可用點。但爲了好的措施，我想添加兩個條目。

  Tail    Head     
A| B | empty | empty | K | M | F | P 

這裏是我的問題

我有沒有實現這個吧？大聲笑當你在尾巴和頭部處於相同的位置，即「K」時完全填充隊列時會發生什麼？如果有人能解釋這個概念更多的細節和清晰度，我會讚賞它。

謝謝！

Answer 1

它在我看來像你是對的。通過顯示頭部和尾部的整數值，可以使圖表更清晰

循環隊列中有許多解釋和示例。我發現沒有比我在前段時間提供的答案中發佈的更好的解釋here。它解釋瞭如果頭部和尾部顯示隊列是空的，有空間還是已滿的情況。

在您的圖表的最後一行中，該隊列有2個空間可容納多個項目。添加第三個會使tail = head，並覆蓋K，這是你不想做的。

當tail = head時，隊列爲空。測試完整隊列稍微複雜一些。請參閱鏈接以獲取完整說明。

Answer 2

我執行此權利嗎？

是的，的確，你做到了。

當您完全填充隊列時會發生什麼情況，如尾部和頭部位於相同的位置（即「K」）？

K將被覆蓋。這種溢出情況可以通過條件TAIL == HEAD來檢查。

如果有人能解釋這個概念更多的細節和清晰度，我將不勝感激。

你必須明白，在傳統的線性FIFO隊列中，每當達到最大尺寸時，元件都需要連續移位。例如，如果隊列的大小爲5，則在5（數字1-5）連續插入並且然後刪除（數字1被刪除）之後，隊列變爲[空，2,3,4,5]。你可以在這裏看到，雖然有1個元素的位置，但除非將所有元素向上移動一個元素，否則不能插入。這就是爲什麼使用循環隊列的原因。它不需要元素移位。

但是，如果您的隊列不斷溢出，隊列的整個用途就會丟失。我會建議使用鏈接列表（線性或循環），因爲它動態添加和刪除元素。

請記住，隊列實際上在內存有限制時使用。例如。輸入/輸出流是一個隊列。當內存很大並且數據溢出不是首選時，會使用鏈接列表。