Circular Queue

FIFO does not imply ``circular''. A FIFO simply means a container has the particular behavior of removing items in the same order as the arrivals of the items. A circular FIFO, or circular queue, has all the properties of a FIFO. In addition, it also reuses empty slots that have been emptied.

Although a circular queue also has head and a tail, it is not easy to track them. This is because when the head and the tail are at the same slot, it is impossible to tell if the circuiar queue is actually full or empty. This makes perfect sense. When a circular queue is empty, the head and the tail are at the same slot. This is because the ``head'' really means ``the next item to remove'', whereas the ``tail'' means ``the next slot to be filled''. When a circular queue is full, however, the head and the tail are the same again!

This means it is better to represent a circular queue remembering the head and a counter that count the number of used slots. The means the tail is computed from the head and the in-use-counter.