[data-structure]：循环队列的尾部指针

Question

在循环队列的实现中，尾部指针指向队列中最后一个元素之后的位置1：

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

为什么？

我想我可以用尾部指针指向最后一个元素来实现循环队列，而不是超过最后一个元素1。

Answer 1

你可以，确实可以这样实现它。让尾部指针指向最后一个元素之后的位置1有一定的对称性：

• front指向第一个(最旧的)使用的元素-下一个要为read
• tail的元素指向第一个(最旧的)未使用的元素-下一个将写入

的元素

在这两种情况下，您都需要做更多的工作来区分满循环队列和空循环队列。在Wikipedia article on circular buffers中讨论了一些替代方案(包括按您的方式做事情)。

Answer 2

看起来这是你用来判断队列是空还是满的实现方式。

http://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction