Insertion in Circular Queue is similar to how insertion is done in a queue. Circular Queue is also implemented as FIFO (First In First Out) data structure. The circular nature of this queue is implemented by linking the last element of the queue with the first element.
The circular queue is an important data structure where you need to make the first element follow after traversing or accessing the last element. It’s like a giant wheel where every person will come back to the start position after a full round. You can see use of this data structure in many applications in computer science. Looping through the opened windows on a desk top (ctrl+tab), running a presentation in loop or play turns of multiple players in a game are few examples.
You have already learnt about circular queues. So, next we will discuss how Insertion operation is done in a circular Queue using arrays and linked list representations.
Insert using an Array Representation
In the linear Array representation of a circular Queue, insertion is similar to that in a normal queue. When the last index of the queue has been used to insert an element, next element is inserted at index 0 (if it is not already used).
Two variables FRONT and REAR are maintained to store the index of the first and last elements of the queue respectively. To insert an element, REAR is compared with MAX (size of array storing queue-1) or FRONT variable. If these two variables are equal, an overflow condition is reported back. New element cannot be inserted.
If REAR is equal to MAX, new REAR will be 0 else REAR variable is incremented to get the position for the new element.
Algorithm ENQUEUE_CIRCULAR_ARRAY(QUEUE, FRONT, REAR, ITEM) Step 1 [If overflow, Exit algorithm. Insertion not possible] IF (FRONT==REAR+1) OR (FRONT==0 AND REAR==MAX) Then Exit Step 2 [Generate position for new element to be inserted] IF REAR==MAX then REAR=0 Else REAR=REAR+1 Step 3 [Store new element at the rear] QUEUE[REAR]=ITEM Step 4 Exit
Insert using an Linked List Representation
In dynamic Linked List representation of a Circular Queue, two pointers FRONT and REAR are maintained to store the address of the first and last elements. LINK part of REAR stores the address of first node (address stored in FRONT pointer)
To insert a new element in this implementation, first a node is created by fetching memory using programming language specific function (malloc in C). This new node is identified by a pointer NEW. To add this at the end, NEW->LINK gets LINK part of REAR Node, REAR->LINK gets NEW and REAR pointer gets NEW. This way the insertion in circular queue is implemented.
Algorithm ENQUEUE_CIRCULAR_DYNAMIC (FRONT, REAR, ITEM) Step 1 [Get a new node from memory] NEW->DATA=ITEM Step 2 [Add the new node to the QUEUE at the end] If FRONT==NULL then [the new node becomes first as well as last node] FRONT=NEW REAR=NEW REAR->LINK=FRONT Else NEW->LINK=REAR->LINK REAR->LINK=NEW REAR=NEW Step 3 Exit