 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 = data
newNode -> next = NULL
if ( REAR == NULL)
FRONT = REAR = newNode
end if
else
REAR -> next = newNode
REAR = newNode
end 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 if
end Algorithm_Dequeue
else
temp = FRONT
FRONT = FRONT -> NEXT
free(temp)
end else
end 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
}
else
front = 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 node
front = front -> next; // Move FRONT to the next node
free(temp); // Delete the temporary node
if(front == NULL)
rear = NULL;
return data;
}

/* Function to check if thw queue is empty */
int empty()
{
if(front == NULL)
{
return 1;
}
else
return 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 POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

2    3