-
Before we start to learn about Circular queue, we should first understand, why we need a circular queue, when we already have linear queue data structure.
-
In a Linear queue, once the queue is completely full, it's not possible to insert more elements.
-
Even if we dequeue the queue to remove some of the elements, until the queue is reset, no new elements can be inserted.
-
When we dequeue any element to remove it from the queue, we are actually moving the front of the queue forward, thereby reducing the overall size of the queue.
-
And we cannot insert new elements, because the rear pointer is still at the end of the queue.
-
Circular Queue is also a linear data structure, which follows the principle of FIFO(First In First Out), but instead of ending the queue at the last position, it again starts from the first position after the last,
-
hence making the queue behave like a circular data structure.
-
Another very important point is keeping the value of the tail and the head pointer within the maximum queue size.
-
In the diagrams above the queue has a size of 8, hence, the value of tail and head pointers will always be between 0 and 7.
-
This can be controlled either by checking everytime whether tail or head have reached the maxSize and then setting the value 0 or, we have a better way, which is, for a value x if we divide it by 8, the remainder will never be greater than 8, it will always be between 0 and 0, which is exactly what we want.
-
So the formula to increment the head and tail pointers to make them go round and round over and again will be,
-
head = (head+1) % maxSize
-
or tail = (tail+1) % maxSize
