Implementation of Queue using Linked list | Queue insertion and deletion operations

Queue data structure implementation can be done using arrays and linked lists. Now, let us see the linked list implementation of queue.

Enqueue and dequeue operations in a linked list

enqueue()

• Create a newNode with the given value and set the node's pointer to NULL.
• Check whether queue is EMPTY.
• If it is EMPTY, set FRONT and REAR to newNode.
• Else, set the pointer of REAR to newNode and make REAR as the newNode.

Algorithm_Enqueue

`newNode -> data = datanewNode -> next = NULLif ( REAR == NULL)FRONT = REAR = newNodeend ifelseREAR -> next = newNodeREAR = newNodeend Algorithm_Enqueue`

dequeue()

• Check if the queue is EMPTY.
• If it is EMPTY, then display "EMPTY QUEUE" and exit.
• Else, create a temporary node and set it to FRONT.
• Make the next node as FRONT and delete the temporary node.

Algorithm_Dequeue

`if(FRONT == NULL)print "EMPTY QUEUE" and exit.end ifend Algorithm_Dequeueelsetemp = FRONTFRONT = FRONT -> NEXTfree(temp)end elseend Algorithm_Dequeue`

Now, let us see a program for linked list implementation of queue.

C program for queue implementation using linked list

`#include <stdio.h>#include <stdlib.h>/* Structure with a node and a pointer */struct node{int data;struct node *next;} *rear,*front,*temp,*newNode;/* Initialising front and rear in empty list */void create(){front = rear = NULL;}/* Function to insert elements in the queue */void enqueue(int data){newNode = (struct node*) malloc(sizeof(struct node));newNode -> data = data;newNode -> next = NULL;if(rear != NULL){rear -> next = newNode;rear = newNode;  // Make the new node as REAR}elsefront = rear = newNode;  // In a empty queue, the inserted element becomes FRONT and REAR}/* Function to dequeue elements in a queue */int dequeue(){int data;data = front -> data;temp = front;   // Copy FRONT to a temporary nodefront = front -> next;   // Move FRONT to the next nodefree(temp);  // Delete the temporary nodeif(front == NULL)rear = NULL;return data;}/* Function to check if thw queue is empty */int empty(){if(front == NULL){return 1;}elsereturn 0;}/* Function to display elements */void display(){if(empty())printf("\nEMPTY QUEUE\n");else{temp = front;printf("\nQUEUE ELEMENTS : ");while(temp != NULL){printf("%d ",temp -> data);temp = temp -> next;}}}/* Main Function */int main(){int num,choice;while(1){printf("\n\nQUEUE OPERATIONS\n\n1.ENQUEUE\n2.DEQUEUE\n3.DISPLAY\n\n");scanf("%d",&choice);switch (choice){case 1:printf("\nEnter item : ");scanf("%d",&num);enqueue(num);break;case 2:if(!(empty()))printf("\nDequeued element : %d",dequeue());break;case 3:display();break;default: exit(0);}}return 0;}`

OUTPUT

Enqueue operation in a queue

Dequeue operation in a queue

Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`