Queue Using Linked List With C++ Program

Consider a scenario where you are required to write a program to store the marks of a hundred students in a particular subject. So, our logic would look like this:

int marks[100]; 

But here arises the problem. After executing the program, supposing you want to increase the number of students to 101, where and how would you store its address?

Also, if you need to reduce the number of students from 100 to 40, then you would only be wasting memory.

To overcome all these challenges, we, therefore, implement a queue using linked list to create a memory or even free memory during the program run time. This would help you to accomplish your tasks efficiently.

Here is the c++ program for implementing queue using linked list.

/* C++ Program To Implement Queue Using Linked List */

#include<iostream>
#include<stdlib.h>
 
using namespace std;
 
struct node
{
  int data;
  struct node *next;
}*front=NULL,*rear,*temp;
 
void insert()
{
  temp=new node;
  cout<<"Enter data:";
  cin>>temp->data;
  temp->next=NULL;
  
  if(front==NULL)
    front=rear=temp;
  else
  {
    rear->next=temp;
    rear=temp;
  }
}
 
void remove()
{
  if(front==NULL)
    cout<<"Queue is empty\n";
  else
  {
    temp=front;
    front=front->next;
    cout<<"Deleted node is "<<temp->data<<"\n";
    delete(temp);
  }
}
 
void display()
{
  if(front==NULL)
    cout<<"Queue is empty\n";
  else
  {
    temp=front;
    while(temp!=NULL)
    {
      cout<<temp->data<<"->";
      temp=temp->next;
    }        
  }
}
 
int main()
{
  int ch;
  while(1)
  {
    cout<<"\n"<<"\n1.Insert\n2.Delete\n3.Display\n4.Exit";
    cout<<"\n\nEnter your choice:";
    cin>>ch;
    cout<<"\n";
    
    switch(ch)
    {
      case 1: insert();
          break;
      case 2: remove();
          break;
      case 3: display();
          break;
      case 4: exit(0);
          break;
      default: cout<<"Wrong Choice!!!";
    }
  }
  
  return 0;
}

Quickly Understanding Queue Data Structure

As we discussed in our earlier post (Queue Implementation Using Array), much like, the queue is also a linear, abstract data structure. While stack is open for operations at only one end, the queue can be operated upon on both ends. At the rear, new elements are added and at the front, elements are removed. Queue follows the FIFO, First In First Out functionality, that is, we would be able to access first the data element that was stored first.

To understand queue better, picturise a single lane road. Only the vehicle that enters first would be able to come out first. Other queue instances could be observed at billing counters, where the buyer who gets into the line first, gets the purchased items billed first and leaves the queue first.

representation of queue in linked list

Basic Operations on Queue Using Linked List

enqueue() Function used to add an element at the rear end of the queue.

dequeue() Function used to remove an element from the front end of the queue.

peek() Function used to access the element at the front end of the queue without deleting it.

isFull() Function used to check the fullness of the queue.

isEmpty() Function used to check the emptiness of the queue.

How To Implement Queue Using Linked List

To understand how to create a queue using linked list, let us consider the following example, where the linked list consists of three nodes.

queue using linked list

The first node’s value is 10 and the address is 100. Similarly, the second and third nodes’ values are 20 and 30 respectively, and their addresses are 200 and 300 respectively. Notice that the link field of the first node contains the address of the second node. Similarly, the second node’s link field contains the address of the third node. Thus, the last node’s link field is null. So, to this linked list, we are going to perform the following functions:

  • enqueue()
  • dequeue()

Note that all these operations must be executed in constant time, that is O(1).

Now, if we consider the beginning of the linked list as the front of the queue, and the end of the linked list as the rear of the queue, we would be able to dequeue in constant time by simply moving the head pointer to the next node and deleting the current node.

However, we wouldn’t be able to enqueue in constant time. This is because we would have to traverse through the whole linked list, to reach the end of the linked list where insertion must take place. So, you must understand that with only the head pointer you would not be able to enqueue and dequeue in constant time.

To overcome this problem, we would therefore not utilize the head pointer, rather the front and rear to carry out the operations in constant time. Thus, with the front pointer, we would dequeue in constant time, and with the rear pointer, we would enqueue in constant time.

1. enqueue()

Let us now see how to enqueue the first node in our mentioned linked list. To begin with, let us define the structure node. This must have the data field of an integer variable to store the value and the link field of type node to store the address of the next node. After this, we shall declare our front and rear pointers and initialize them to null. In this case, note that we are enqueueing to an empty linked list.

To enqueue, let us create a new node and store its address in the pointer ptr. Let us assume that the node is created at the address 100 and it is stored in the pointer ptr. The data field is entered as 1 and the link field is entered as null, as shown below.

queue using linked list

Now the front pointer needs to be adjusted. So, let us initialise the front pointer to null, meaning that we are enqueueing the first node of the queue. To do this, we would equal the front to ptr, such that it points to the first node. We also indicate the rear to ptr as shown below.

queue using linked list

Now, to insert another node, we would again create a new node whose address would be stored in the pointer ptr. Let us make this node’s data field 2 and address field null since this would now be the last node of the linked list.

queue using linked list

Now, note that our front can’t be null. To do this, we would have to make the link field of the rear equal to ptr and thus the link field of the first node now would be 200. So here, our first node points to the second node, and thus the rear is equated to ptr.

queue in singly linked list

Similarly, we can enqueue the third node as well using the same algorithm we followed to enqueue the second node.

queue using linked list

2. isEmpty()

Before we delete a node, we need to check if a queue is empty or not. To do this, we check if both the front and rear pointers are null. If so, then it could be derived that the queue is empty, else it is understood that the queue has some values.

3. dequeue()

After checking whether the queue is empty or not, we proceed to dequeue an element. So, when there exists only one node in the list, we would declare that the front is equal to rear.

queue using linked list

Then we would simply free the memory and assign both front and rear to null. Now the queue is empty.

Let us consider a scenario where there are more nodes, say three nodes in the queue. As is the principle working of the queue, we would have to remove the front node from the queue. To do this, we would equate ptr to the front and traverse the front pointer to the next node and assign it the front.

dequeue operation in queue using linked list

dequeue operation in queue using linked list

Now, the front would contain the address 200 and would point to the second node as the front while deleting the first node.

dequeue operation in queue using linked list

Read More:

Leave a Comment