Queue implementation using Linked list – Data Structures Part 5

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.

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.

Enqueue

  • 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.

EnQueue implementation using Linked list

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 FRONT pointer. Set the FRONT pointer to point to the FRONT’s next node.
ptr = FRONT;
FRONT = FRONT->next;
free(ptr);

The below image explains the Dequeue process.

DeQueue implementation using Linked list

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.

Linux Device Driver TutorialsC Programming Tutorials
FreeRTOS TutorialsNuttX RTOS Tutorials
RTX RTOS TutorialsInterrupts Basics
I2C Protocol – Part 1 (Basics)I2C Protocol – Part 2 (Advanced Topics)
STM32 TutorialsLPC2148 (ARM7) Tutorials
PIC16F877A Tutorials8051 Tutorials
Unit Testing in C TutorialsESP32-IDF Tutorials
Raspberry Pi TutorialsEmbedded Interview Topics
Reset Sequence in ARM Cortex-M4BLE Basics
VIC and NVIC in ARMSPI – Serial Peripheral Interface Protocol
Bootloader TutorialsRaspberry PI Pico Tutorials
Zephyr RTOS Tutorials - STM32Zephyr RTOS Tutorials - ESP32
VHDL TutorialsUDS Protocol Tutorials
Product Reviews
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments