[数据结构]：循环队列

的尾指针在循环队列，尾部指针指向在队列中的位置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

回答