[data-structure]: the tail pointer of cyclic queue

Question

In the implementation of Cyclic Queue, the tail pointer points to the position 1 past the last element in the queue:

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

why?

I think I can implement the Cyclic Queue with the tail pointer pointing to the very last element, not 1 past the last.

Answer 1

You can, indeed implement it that way. There's a certain symmetry to having the tail pointer point to the position 1 past the last element:

• front points to the first (oldest) used element - the next element to be read
• tail points to the first (oldest) unused element - the next element to be written

In either case, you need to do a bit more to distinguish between a full cyclic queue and an empty one. Some of the alternatives (including doing things your way) are discussed in the Wikipedia article on circular buffers.

Answer 2

It looks like that is the implementation your using's way of determining if the queue is empty or full.

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