Circular queue

Essentials

A circular queue is a fixed-size queue that follows the FIFO (First In, First Out) principle. Rather than ending at the last position like the ordinary queue does, it starts again from the second after the last position.

This data structure is also known as the Ring Buffer. It is very naturally represented as a circle.

The picture below shows a circular queue with a fixed-size of 8 elements and filled with only 5 elements:

There are two important parts:

• the front is a current position to dequeue an element (remove);

• the rear is a current position to enqueue an element (add).

Though we showed a circular queue in the form of a circle, it is usually built on top of an ordinary array – see the example below:

From now on, we shall stick to such representation, but you, as the boss of your mind can always imagine it as a circle.

Internal mechanics

Initially, we have an empty circular queue with a specified size, and both the front and the rear are not set. When performing enqueue and dequeue operations, front and rear shift to the end of the queue.

Suppose we've performed the following sequence of operations:

enqueue 100
enqueue 300
enqueue 250
enqueue 400
enqueue 200
dequeue
dequeue

Then the circular queue will look like:

The most interesting thing comes up when front or rear reaches the end: in this case, it should be shifted to the very beginning.

Here is a sequence of operations:

enqueue 450
enqueue 300
enqueue 350
enqueue 200

The result is the following:

We can reuse free space at the beginning to insert new elements, and as you may guess, front behaves in the same way.

To calculate the next position of rear or front based on the current one it is convenient to use a formula with the modulo operation (%):

next = (current + 1) % size

Here, size is not the number of elements actually stored in the queue but the total number of items to store elements (8 in the picture above).

Completely full circular queue

Another interesting case is when a circular queue is completely full like this:

There are two completely different strategies to handle this case:

• overwrite the existing queue elements;

• notify about the impossibility of enqueue until some elements are dequeued.

The first strategy is similar to the behavior when positions are not occupied at all. Suppose we've enqueued 800 and 750 in the completely full queue – it shifts rear rewriting old numbers 250 and 400. It also shifts front to keep the FIFO order:

The second strategy needs a way to notify a user (a programmer who uses an implementation of a circular queue) by throwing an exception or returning a boolean result that the operation failed.

Application

Circular Queue is used to:

• join the front and the rear part when rebuffering;

• utilize the unused memory locations;

• switch on the traffic lights one by one repeatedly.