Queue Insertion – using Array and Linked List

Queue Insertion operation is also called enqueue. Queue operations implement 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 the REAR of the queue.

It is similar to your taking up the last slot in a queue to pay your grocery bill in a supermarket . In computer terms it is giving printing command to printer, typing from the keyboard and clicking something with mouse. All these are handled by OS through queue because of the latency between CPU and the peripherals.

You have already learnt about arrays and linked lists. So, next we will discuss how Insertion operation of a Queue is implemented using these data Structures.

Insert 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 insert an element, REAR is compared with MAX (size of array storing queue-1). If these two variables are equal, an overflow condition is reported back and new element cannot be inserted. Else REAR variable is incremented to get the position for the new element.

Algorithm ENQUEUE_ARRAY(QUEUE, FRONT, REAR, ITEM)
Step 1 	[If overflow, Exit algorithm. Insertion not possible]
        IF REAR==MAX 	 Then Exit
Step 2	[Generate position for new element to be inserted]  
        REAR=REAR+1
Step 3	[Store new element at the rear] 
        QUEUE[REAR]=ITEM
Step 4  Exit
Insertion Queue with Array

Queue Insertion in Linked List Representation

 In dynamic 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 insert a new element in this implementation, first a node is created by fetching memory using programming language specific allocation function (malloc in C).

The new node is identified by a pointer NEW. To add the new node at the end, REAR->LINK pointer is updated with the address NEW. To make the new node as the last node, update REAR with NEW pointer. This way by updating the LINK pointer of REAR node and the REAR pointer with address of new node, queue insertion is implemented.

Algorithm ENQUEUE_DYNAMIC (FRONT, REAR, ITEM)
Step 1 	[Get a new node from memory]  
        NEW->DATA=ITEM
        NEW->LINK=NULL
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
        Else
	        REAR->LINK=NEW
	        REAR=NEW
Step 3  Exit
Linked List Queue

Be First to Comment

Leave a Reply

Your email address will not be published.