Table of Contents

1 Implementation of Queue using Linked List

Implementation of Queue using Linked List

Implementation of Queue using Linked List in C is an important topic to be asked in University Examination and also in Competitive exam.

In this tutorial we have explained with example how can we implement queue using linked list.

Insertion and deletion operations on queue using Linked List are explained in this tutorial.

Implementation of Queue using Linked List is also known as Dynamic implementation of Queue.

In Linked List to store data we used node, Node consist of two field. One field is data which store he data value and second field is pointer named as next which store the address of next node of linked list.

To implement queue using Linked List at first we will define the structure of a node.

struct node
{
int data;
struct node *next;
};

struct node *start ;

Declare FRONT and REAR ends of Queue and initialize them with NULL.

struct node * FRONT = NULL ;

struct node * REAR = NULL ;

Insertion in Queue using Linked List

To insert a new element in queue using linked list we use the following steps

Step 1 – Create a new node to be insert

struct node * newnode ;

Step 2 – Allocate the memory to newly created node

newnode= (struct node *) malloc( sizeof(struct node))

Step 3 – Enter the value of NUM variable it means element to be store in queue.

Step 4- Initialize data field value of new node with NUM

newnode->data = num

Step 5 – Set next field of newnode as null

newnode->next = NULL

Step 6 – IF FRONT = NULL (it means when queue is empty) then newnode will be the first node so

set FRONT=REAR=newnode

ELSE

REAR ->next = newnode

set Rear = newnode

Note – In step 6 statement written in side ELSE block will be used when linkedlist already has some node then insert newnode ( new element) in queue ( linked list) next to the REAR .

Deleting a Node in Queue using Linked List

To delete a node from linked list we use the following steps.

Step 1 – Declare a TEMP variable of structure node type to store the node to be deleted

struct node * TEMP;

Step 2 – Check whether Queue is empty IF FRONT==NULL then display QUEUE is empty

Step 3 – Set TEMP = FRONT ( element will be deleted from front of the Queue)

Step 4 – Set NUM = TEMP-> DATA

Here we declare a variable NUM which will store the value or element to be deleted from queue which is represented by data filed of TEMP

Step 5 – Print deleted element as NUM.

Step 6 – Set FRONT = FRONT ->next

STEP 7 – IF FRONT = NULL then

SET REAR = NULL

STEP 8 – Delete TEMP

Note – In above algorithm step 6 is used when we delete an element or node then next element or node to be deleted will be refer by FRONT so we set it as FRONT->next

Step 7 is used when last node or element will be deleted after that FRONT will refers nothing so linked list will be empty that is why we set REAR as NULL when FRONT will be NULL.

C Program to Implement Queue Using Linked List

C Program to Implement Queue using Linked List is given below –

#include<stdio.h>

#include<stdlib.h>

struct node

{

int data;

struct node *next;

};

struct node * front=NULL;

struct node * rear = NULL;

void qinsert();

void qdelete();

void qtraverse();

void main()

{

int choice;

while(choice!=4)

{

printf(“\nDYNAMIC IMPLEMENTATION OF LINEAR NODE”);

printf(“\n1. Insert”);

printf(“\n2. Delete”);

printf(“\n3. Traverse”);

printf(“\n4. Exit”);

printf(“\n\nEnter your choice [1/2/3/4] : “);

scanf(“%d”,&choice);

switch(choice)

{

case 1: qinsert();

break;

case 2: qdelete();

break;

case 3: qtraverse();

break;

case 4: exit(0);;

default : printf(“\nInvalid choice”);

}

// Function to insert element in Linear node

void qinsert()

{

struct node *newnode;

int num;

newnode=(struct node*)malloc(sizeof(struct node));

printf(“\nEnter element to be inserted in node : “);

scanf(“%d”,&num);

newnode->data=num;

newnode->next=NULL;

if(front==NULL)

{

front=newnode;

rear=newnode;

}

else

{

rear->next=newnode;

rear=newnode;

}

// Function to delete element from Linear node

void qdelete()

{

if(front==NULL)

{

printf(“\nNode is empty (Node underflow)”);

return;

}

struct node *newnode;

int num;

newnode=front;

num=newnode->data;

printf(“\nThe deleted element is : %d”,num);;

front=front->next;

if(front==NULL)

rear=NULL;

free(newnode);

}

// Function to display Linear Node

void qtraverse()

{

struct node *newnode;

if(front==NULL)

{

printf(“\nNode is empty (Node underflow)”);

return;

}

else

{

newnode=front;

printf(“\n\n Queue elements are : \n”);

while(newnode!=NULL)

{

printf(” %d”,newnode->data);

newnode=newnode->next;

}

Output