的尾指針在循環隊列,尾部指針指向在隊列中的位置1過去的最後一個元素的實現:[數據結構]:循環隊列
|1|2|3|4|5| | |
^ ^
front tail
爲什麼呢?
我想我可以實現循環隊列尾指針指向最後一個元素,而不是最後一個1。
的尾指針在循環隊列,尾部指針指向在隊列中的位置1過去的最後一個元素的實現:[數據結構]:循環隊列
|1|2|3|4|5| | |
^ ^
front tail
爲什麼呢?
我想我可以實現循環隊列尾指針指向最後一個元素,而不是最後一個1。
可以,確實實現它的方式。有一定的對稱性,以具有尾指針指向的位置1過去的最後一個元素:
front
指向第一(最舊)使用元件 - 的下一個元素被讀取tail
指向第一(最舊的)未使用的元素 - 要寫入的下一個元素無論哪種情況,您都需要做更多的工作來區分完整的循環隊列和空的隊列。在Wikipedia article on circular buffers中討論了一些替代方法(包括按照自己的方式)。
它看起來像是執行你使用的方式來確定隊列是空的還是滿的。
http://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction
如果tail指向最後一個元素後面的pos 1,那麼當隊列滿時,tail要指向一個超出數組索引的位置(如果隊列在數組中實現),對吧?這可以嗎? – Alcott
如果它是圓形的,那麼尾巴應該環繞並指向零位,而不是離開陣列的末端。寫入一個完整的循環隊列應該覆蓋最舊的元素(或拋出異常)。 –
我明白了,我正在實施的不是循環的。 – Alcott