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

05 min read

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

queue using linked list enqueue

Dequeue operation in a queue

dequeue in linked list

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error