Queue Deletion – using Array and Linked List

Queue Deletion operation is also called dequeue. Queue works on FIFO (First In First Out) principle. The element added at the beginning of the queue is deleted first. A new element can be added at REAR of the queue.

If you have ever boarded a bus or plane you will understand this concept. If you are standing at the head of the queue of passengers, you will be the first one to board. In computer terms a print command given is completed first than those given later. These are handled by OS through queue. This queue is saved in the printer buffer to match the different execution speeds as CPU and the printer.

You have already learnt about insertion in queues implemented with arrays and linked lists. So, next we will discuss how deletion operation is done in Queue is implemented using these data Structures.

Delete an element in a Queue using an Array

In the linear Array representation of a Queue, two variables FRONT and REAR are maintained to store the indexes of the first and last elements respectively. To delete an element, FRONT is compared with -1 (indicating no elements are present in the queue).

If FRONT is -1  an underflow condition is reported back. Since no element is there so deletion is not possible. Else FRONT variable is incremented to get the position of the next element in the queue. Incrementing of FRONT will update the next element of the queue. This is similar to situation that when you board the plane, the next person will become the first person of queue.  

Algorithm DEQUEUE_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 argument] 
        ITEM=QUEUE[FRONT]
Step 2	[Generate position for next first element of the queue]  
        FRONT=FRONT+1
Step 4  Exit

Queue Deletion in Linked List Representation

 In the Linked List representation of a Queue, two pointers FRONT and REAR are maintained to store the address of the first and last linked list nodes.

To delete an element in this implementation, the address of the node identified by FRONT pointer is stored in a temporary pointer TEMP. It can be permanently deleted by using programming language specific function memory deallocation methods (like free in C).  

FRONT pointer is updated FRONT=FRONT->LINK, remove it. This way by updating the LINK pointer of FRONT node, the queue deletion is implemented.

Algorithm DEQUEUE_DYNAMIC (FRONT, REAR, ITEM)
Step 1 	[Check if queue has some elements]  
	If FRONT==NULL then report underflow and exit
Step 2	[Store the value of first node of the QUEUE in ITEM]
        TEMP=FRONT
        ITEM=TEMP->DATA
Step 3	[Remove the first node of the QUEUE ]
        If FRONT==REAR then
	      [There is only one node in the queue to be deleted]
	      FRONT=NULL
	      REAR=NULL
        Else
	      FRONT= FRONT->LINK
Step 4  [Free the deleted node]
        Free (TEMP)
Step 5  Exit

admin