Deletion in a Circular Queue

Circular Queue Deletion is similar to deletion in a queue. The only difference is due to its characteristic of linking last element with the first element of the circular queue. When an element at front of the circular queue is deleted, the REAR element must also get the information about the new “first” node of the queue.

We have mentioned earlier that a circular queue is used in many applications. A few are 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.

Take example of opened windows on a desk top. When you close a specific application, what happens to the remaining opened applications? Omitting the deleted application, rest of the applications stay open and can still be browsed through ctrl_tab keys. It means that with deletion of an application, its previous and next applications are linked to continue tabbed browsing.

Moving ahead with operations in circular queues, let’s discuss how deletion operation is done in a circular Queue in arrays and linked list representations.

Deletion in Array Representation of Circular Queue

In the linear Array representation of a Circular Queue, two variables, FRONT and REAR, are maintained to store the index of the first and the last elements of the queue respectively. Deletion is done by incrementing the FRONT variable. This excludes the previous first element from the array, indirectly omitting it from circular queue.

To delete, the underflow condition is checked by comparing FRONT with value -1. If underflow condition doesn’t exist, then the FRONT variable value is checked. If it is equal to MAX (size of the array) then FRONT is set to 0, indicating that the element at MAX index is deleted and new FRONT is at index 0.

Such implementation helps in utilizing the slots created when elements are deleted from front. After reaching MAX of the array, insertion is done in the locations that are beyond FRONT and REAR indexes.

If FRONT and REAR are equal it means that there is only one element to be deleted. In this case both FRONT and REAR are set to -1.

Deletion in a Circular Queue

Deletion operation in a Circular Queue is similar to deletion in a queue. The only difference is due to its characteristic of linking last element with the first element of the circular queue. When an element at front of the circular queue is deleted, the REAR element must also get the information about the new “first” node of the queue.

Moving ahead with operations in circular queues, let’s discuss how deletion operation is done in a Circular Queue in arrays and linked list representations.

Deletion in Array Representation of Circular Queue

If FRONT and REAR are equal it means that there is only one element to be deleted. In this case both FRONT and REAR are set to -1

Algorithm DEQUEUE_CIRCULAR_ARRAY(QUEUE, FRONT, REAR, ITEM)
Step 1 	[If underflow, Exit algorithm. Deletion not possible]
        IF (FRONT=-1)  then Exit
Step 2	[Store deleted element in ITEM] 
        ITEM=QUEUE[FRONT]
Step 3	[update front to delete the first element identified by FRONT variable]  
        IF FRONT==REAR then [deletion of only element leaves an empty queue]
		FRONT=-1
		REAR=-1
        Else
	     IF FRONT==MAX then 
		 FRONT=0
             else
                 FRONT=FRONT+1
Step 4  Exit

Deletion in Linked List Representation of a Circular Queue

In dynamic Linked List representation of a Circular Queue, two pointers FRONT and REAR are maintained to store the address of the first and the last elements. LINK part of REAR stores the address of first node (address stored in FRONT pointer)

Deletion in a Circular Queue of the first element in this implementation, first Underflow condition is checked by comparing FRONT with NULL. No deletion is possible if this condition holds true.

The first node’s address is stored in a pointer named TEMP. This helps in storing the deleted node for later processing. By the end of the algorithm it can be returned to memory or freed.

If FRONT and REAR both point to same node then both these pointers are updated with NULL to delete the only node present in the circular queue. Otherwise FRONT pointer is updated with FRONT-> LINK.

Algorithm DEQUEUE_CIRCULAR_DYNAMIC (FRONT, REAR, ITEM)
Step 1 	[Check underflow condition]  
        IF FRONT==NULL then exit 
Step 2 	[Store address of deleted node in TEMP]  
        TEMP=FRONT
        ITEM=TEMP->DATA
Step 3	[Remove the first node from circular Queue]
        If FRONT==REAR then [this node is the first as well as the last node]
	     FRONT=NULL
	     REAR=NULL
        Else
	     FRONT=FRONT->LINK
	     REAR->LINK=FRONT
Step 4  Exit