[數據結構]：循環隊列

的尾指針在循環隊列，尾部指針指向在隊列中的位置1過去的最後一個元素的實現：[數據結構]：循環隊列

|1|2|3|4|5| | | 
^  ^
front  tail

爲什麼呢？

我想我可以實現循環隊列尾指針指向最後一個元素，而不是最後一個1。

2011-09-08 Alcott

可以，確實實現它的方式。有一定的對稱性，以具有尾指針指向的位置1過去的最後一個元素：

無論哪種情況，您都需要做更多的工作來區分完整的循環隊列和空的隊列。在Wikipedia article on circular buffers中討論了一些替代方法（包括按照自己的方式）。

2011-09-08 02:53:04

如果tail指向最後一個元素後面的pos 1，那麼當隊列滿時，tail要指向一個超出數組索引的位置（如果隊列在數組中實現），對吧？這可以嗎？ – Alcott

如果它是圓形的，那麼尾巴應該環繞並指向零位，而不是離開陣列的末端。寫入一個完整的循環隊列應該覆蓋最舊的元素（或拋出異常）。 –

我明白了，我正在實施的不是循環的。 – Alcott

它看起來像是執行你使用的方式來確定隊列是空的還是滿的。

2011-09-08 02:51:55 Corbin

回答