This article is a continuation of the Series on Data Structures and carries the discussion on different types of data structures and their implementation. The aim of this series is to provide easy and practical examples that anyone can understand. In our previous article, we have seen what is a queue and queue implementation in C using an array. In this article, we will see Queue implementation using Linked list – Data Structures Part 5.
Prerequisites
We are requesting you to go through the below tutorials, before continuing this.
Introduction
In this queue implementation information is stored in the form of nodes and it is following queue rules that is First In First Out(FIFO).In the queue, insertion is taking place in one end and deletion takes place in another end.
Singly Linked List
The below image explains the concept of a singly linked list.
The above shown Linked List has 4 Nodes (Node 0, 1, 2, and 3). Here, Node 0 is the head node, and it is pointing to the next node which is Node 1. And Node 1’s address is pointing to Node 2, Node 2’s address is pointing to Node 3. Finally, Node 3’s address is NULL as there is no node to point.
Queue implementation using Linked list
The main advantage of queue implementation using a Linked list over an array is, that the array size is fixed. So, we can’t shrink or increase the size of the queue. But in this method, we can allocate the memory dynamically. So, Increasing or decreasing the size of the queue is possible in the run time.
Operation Performed on Queue
- Enqueue– Insert an element to the queue.
- Dequeue– Deleting an element from the queue.
- Display– Displaying all the elements in the queue.
- Peek– Showing the first element in the queue without deleting it.
We will have to maintain two pointers that are used to track the FRONT and REAR end.
FRONT is used to track the first element of the queue. REAR is used to track the last element of the queue.
We will be using the below structure as a node for our code.
// Structure to create a node with data and next (pointer to next node)
struct node
{
int data;
struct node *next;
};
Enqueue (Insertion)
Inserting an element into a queue takes place at one end of the queue. The new element added to the queue becomes the last element of the queue.
- Create a new element using the dynamic memory allocation method.
struct node* temp = (struct node*)malloc(sizeof(struct node));
- Check if the Queue is empty, if the queue is empty, set the FRONT and REAR pointer point to the newly created element. And set the next to NULL.
FRONT = temp; REAR = temp; temp->next = NULL;
- If the queue is not empty and going to add an element to the existing queue, make the next pointer of REAR to the new node(
temp) and set REAR to the new node(temp). And set the Last elements next to NULL.
REAR->next = temp; REAR = temp; REAR->next = NULL;
The below image explains the Enqueue process.
Example code
void enqueue()
{
temp=(struct node*)malloc(sizeof(struct node));
if(temp != NULL)
{
printf("Enter the data to insert:");
scanf("%d",&temp->data);
temp->next = NULL;
//if new node is going to insert in empty queue
if(front == NULL)
{
front = temp;
rear = temp;
}
//if new node is going to insert in an existing queue
else
{
rear->next = temp;
rear = temp;
}
}
}
Dequeue (Deletion)
Delete operation on the queue is to remove the element from the list which was inserted first in the queue. i.e. Always remove the very first inserted element.
- Check if the queue is empty or not.
- If the queue is empty point (
FRONT == NULL), then the queue is an underflow. So, there is no node to be removed and exit from there. - If the queue is not empty, delete the node which was pointed by
FRONTpointer. Set theFRONTpointer to point to the FRONT’s next node.
ptr = FRONT; FRONT = FRONT->next; free(ptr);
The below image explains the Dequeue process.
Example code
void dequeue()
{
if(isempty() == false)
{
temp = front;
printf("The deleted element from queue is:%d\n",temp->data);
//if only one node is in queue
if(front == rear)
{
front = NULL;
rear = NULL;
}
//if more than one node is in queue
else
{
front = front->next;
free(temp);
}
}
}
Display
To print all the elements in the queue. We have to traverse throughout the queue one by one. We should not delete or modify any data.
Example code
void display()
{
int i;
if(isempty() == false)
{
temp= front;
while(temp->next != NULL)
{
printf("%d-->", temp->data);
temp = temp->next;
}
printf("%d-->NULL\n", temp->data);
}
}
Peek
This function is used to see the element in the front of the queue. This operation will not remove the element.
Example code
void peek()
{
printf("First element in the queue is:%d\n", front->data);
}
Queue implementation in C
Complete Source Code
Now we can combine the above logic and code. The code is given below.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//Function Declaration
void enqueue();
void dequeue();
void display();
void peek();
struct node
{
int data;
struct node* next;
};
struct node* front = NULL;
struct node* rear = NULL;
int main()
{
int choice;
printf("***Queue Implementation using Singly LinkedList***\n");
while (1)
{
printf("1.Insert element to queue (Enqueue) \n");
printf("2.Delete element from queue (Dequeue) \n");
printf("3.Display all elements of queue \n");
printf("4.Display the first element in the queue \n");
printf("\nEnter your choice :");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
peek();
break;
default:
printf ("\nPlease Enter a Valid Choice\n ");
}
}
}
bool isempty()
{
bool isempty = false;
if(front == NULL)
{
printf("\nQueue is Empty\n");
isempty = true;
}
return isempty;
}
void enqueue()
{
struct node* temp=(struct node*)malloc(sizeof(struct node));
if(temp != NULL)
{
printf("Enter the data to insert:");
scanf("%d",&temp->data);
temp->next = NULL;
//if new node is going to insert in empty queue
if(front == NULL)
{
front = temp;
rear = temp;
}
//if new node is going to insert in an existing queue
else
{
rear->next = temp;
rear = temp;
}
}
}
void dequeue()
{
if(isempty() == false)
{
struct node* temp = front;
printf("The deleted element from queue is:%d\n",temp->data);
//if only one node is in queue
if(front == rear)
{
front = NULL;
rear = NULL;
}
//if more than one node is in queue
else
{
front = front->next;
free(temp);
}
}
}
void display()
{
int i;
if(isempty() == false)
{
struct node* temp= front;
while(temp->next != NULL)
{
printf("%d-->", temp->data);
temp = temp->next;
}
printf("%d-->NULL\n", temp->data);
}
}
void peek()
{
printf("First element in the queue is:%d\n", front->data);
}
Output
***Queue Implementation using Singly LinkedList*** 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :1 Enter the data to insert:12 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :1 Enter the data to insert:14 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :1 Enter the data to insert:16 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :3 12-->14-->16-->NULL 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :4 First element in the queue is:12 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :2 The deleted element from queue is:12 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :2 The deleted element from queue is:14 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :2 The deleted element from queue is:16 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :2 Queue is Empty 1.Insert element to queue (Enqueue) 2.Delete element from queue (Dequeue) 3.Display all elements of queue 4.Display the first element in the queue Enter your choice :
You can also read the below topics.
Embedded Software | Firmware | Linux Devic Deriver | RTOS
Hi, I’m SLR. I am a tech blogger and an Embedded Engineer. I am always eager to learn and explore tech-related concepts. And also, I wanted to share my knowledge with everyone in a more straightforward way with easy practical examples. I strongly believe that learning by doing is more powerful than just learning by reading. I love to do experiments. If you want to help or support me on my journey, consider sharing my articles, or Buy me a Coffee! Thank you for reading my blog! Happy learning!
