Insertion in Circular Queue

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

admin