Implementation of Queue using Linked List in C++

Queue using Linked List

In this section, we will learn how the implementation of Queue using Linked List in C++ which is dynamic in nature and it’s size is variable so we do not need to reallocate the entire Linked List. This implementation of the queue is more efficient as compared to the array implementation of the queue. The Linked List Implementation of queue is also better in terms of
  • space
  • memory
  • time complexity
Implementation of Queues using Linked List in C++

Steps to Implement using Linked List in C++

  • We will create a Linked list to perform the operations on the queue.
  • Create a linked list to insert the elements .
  • Similarly, Perform the deletion operation in Linked List.
  • Implement all the methods of the queue in a Linked List.
C++ Implementation of Queues using Linked List

Algorithm for Enqueue:-

  1. Return Queue full
  2. Else
  3. Rear+Rear+1
  4. Queue[Rear]=Data
  5. If(Front== -1)
  6. Front= 0

Algorithm for Dequeue:-

  1. If(Front==-1||Front==Rear+1)
  2. Return
  3. Else
  4. Queue[Front]=0
  5. Front=Front+1

Implementation of using Linked List in C++

#include<iostream>
#include<stdio.h>
using namespace std;

struct LinkedListNode //structure of link node
{
  int data;
  LinkedListNode *next;
} *front = NULL,*rear = NULL,*pointer = NULL,*nextpointer = NULL;

void enqueue (int item) //push the value in the queue
{
  nextpointer = new LinkedListNode;
  nextpointer->data = item;
  nextpointer->next = NULL;
  if (front == NULL)
    {
      front = rear = nextpointer;
      rear->next = NULL;
    }
  else
    {
      rear->next = nextpointer;
      rear = nextpointer;
      rear->next = NULL;
    }
}

int dequeue () //remove the value from the queue
{
  int item;
  if (front == NULL)
    {
      cout << "Queue is empty!!\n";
    }
  else
    {
      pointer = front;
      item = pointer->data;
      front = front->next;
      delete (pointer);
      return (item);
    }
}

int main ()
{

  int n, counter = 0, x1;
  cout << "Enter the number of values to be pushed into queue:-\n";
  cin >> n;
  cout << "Enqueue the value:-\n";
  while (counter < n) { cin >> x1;
      enqueue (x1);
      counter++;
    }
  cout << " After Dequeue :-\n";
  while (true)
    {
      if (front != NULL)
	cout << dequeue () << endl;
    else
	break;
    }
}
Output:-
Enter the number of values to be pushed into the queue:-
3
Enqueue the value:-
25
50
75
After Dequeue :-
25
50
75

Following Operations can be Implemented in queue using Linked List in C++:-

  • Enqueue Operation:- Insertion in Queue, the element added first (Enqueued) will go out of the queue first (Dequeued).
  • Dequeue(Deletion) Operation:- It is the process of removing element from the Queue.