A circular queue is a
particular implementation of a queue. It is very efficient. It is also quite
useful in low level code, because insertion and deletion are totally
independent, which means that you don't have to worry about an interrupt
handler trying to do an insertion at the same time as your main code is doing a
deletion.
A circular queue is one in which the insertion of new element is done at the very first location of the queue if the last location of the queue is full. Suppose if we have a Queue of n elements then after adding the element at the last index i.e. (n-1)th , as queue is starting with 0 index, the next element will be inserted at the very first location of the queue which was not possible in the simple linear queue. That's why linear queue leads to wastage of the memory, and this flaw of linear queue is overcome by circular queue.
How does it work?
A circular queue
consists of an array that contains the items in the queue, two array indexes
and an optional length. The indexes are called the head and tail pointers
and are labelled H and T on the diagram.
The head pointer points
to the first element in the queue, and the tail pointer points just beyond the
last element in the queue. If the tail pointer is before the head pointer, the
queue wraps around the end of the array.
Is the queue empty or
full?
There is a problem with
this: Both an empty queue and a full queue would be indicated by having the
head and tail point to the same element. There are two ways around this: either
maintain a variable with the number of items in the queue, or create the array
with one more element that you will actually need so that the queue is never
full.
So, in all we can say that the circular queue is a queue in which first element come right after the last element, that means a circular queue has a starting point but no end point.
While dealing with the circular queue we will use the following assumptions :
- Front will always be pointing to the first element of the queue.
- If Front=Rear, the queue will be empty.
- Each time a new element is inserted into the queue, the value of rear is incremented by one i.e.Rear = (Rear + 1);
- Each time when an existing element is deleted from the queue, the value of rear is incremented by one i.e.Front = (Front + 1);
Operations on a Queue :
Just like various other homogeneous data structures the main operations that can be performed on a circular queue are:
- Insertion
- Deletion
- Traversing