Circular Queue using Linked List in C++

Circular Queue in C++

 

Circular Queue is a category of Queue data structure. If we equal the linear queue with the linear single linked list, the Circular queue can be equaled by the circular linked list. Here is an article about how to create a circular queue using a circular linked list in C++. Here the circular linked list will be implemented using class.


Circular Queue using Linked List in C++ | PrepInsta
Circular Queue using Linked List
Linear Queue image

Queue VS Circular Queue?

Let’s say, the queue is implemented using an array. So everytime you pop out one element, the front pointer in the array will be increasing by one. After popping out many products, the queue may be impossible to access for storage reasons, even if you don’t have any element in it.
 
That’s why at first the concept of Circular queue came in. In Circular queue, even if you change the front, after some time if the last pointer is accessed with the front pointer, after popping out again, the front pointer will again reach the first position.

 

Circular Queue image

Algorithm to Create Circular Queue (using a Linked List Class) 

In the circular queue, the back (Where elements will be pushed) will be pointing the front (From where elements are to be popped out). That is the main logic behind circular queues, like circular linked lists. Here is the algorithm to implement it in C++.

  • A class is made with the name Node, that represents the nodes in the queue. In our code, the nodes are actually holding an integer value, and a pointer of the same type as the node class.
  • A class is made with the named Queue or Circular_Queue. It is actually a class that will make an array of the Node type.
  • In the default constructor, the front and back will be NULL pointer, to show the queue is empty.
  • The enqueue function (Pushing a node into the queue) will be getting a value or a node value in the argument, and it will be pushing the element in the circular queue using the back pointer. And the new back pointer will be pointing to the front.
  • The Dequeue function will be deleting the node in the front position. And then the back pointer will be pointing to the new front. If the queue becomes null, the front and back both will point to null.
  • The show function will be showing the total circular queue starting from the back to the front.
Circular queue full process Linked List

The code to implement this:

#include<bits/stdc++.h>
using namespace std;

class Node
{
  public:
  int value;
  Node *next;
  Node(int a)
  {value=a;next==NULL;}
};

class Queue
{
  public:
  Node *front,*back;
  int size;
  Queue()
  {front=NULL;back=NULL;size=0;}
  void enqueue(int a)
  {
    cout<<“Pushing “<<a<<” to the Circular Queue”<<endl;
    size++;
    Node *tempnew Node(a);
    if(front==NULL)
    {
      front =temp;
    }
    else back->next=temp;
    back=temp; // back=back->next
    back->next=front;
  }
  int dequeue()
  {
    if(front==NULL) {cout<<“The Circular Queue is empty”<<endlreturn –1;}
    size–;
    int a;
    if(front==back)
    {
      a=front->value;
      delete front;
      front=back=NULL;
      cout<<“Popping the top value “<<a<<” from the Circular Queue”<<endl;
      return a;
    }
    Node *temp=front;
    a=temp->value;
    front=front->next;
    back->next=front;
    delete temp;
    cout<<“Popping the top value “<<a<<” from the Circular Queue”<<endl;
    return a;
  }
  void Show()
  {
    if(size==0) {cout<<“The Circular Queue is empty.”<<endl;return;}
    cout<<“The Queue is:”;
    Node *temp=front;
    while(temp->next!=front)
    {cout<<” “<<temp->value;temp=temp->next;}
    cout<<” “<<temp->value;
    cout<<endl;
  }

};

int main()
{
  Queue q;
  q.enqueue(3);q.enqueue(5);q.enqueue(2);
  q.enqueue(5);q.enqueue(6);
  q.Show();
  q.enqueue(7);q.dequeue();q.dequeue();
  q.Show();
}

Output:

Pushing 3 to the Circular Queue
Pushing 5 to the Circular Queue
Pushing 2 to the Circular Queue
Pushing 5 to the Circular Queue
Pushing 6 to the Circular Queue
The Queue is: 3 5 2 5 6
Pushing 7 to the Circular Queue
Popping the top value 3 from the Circular Queue
Popping the top value 5 from the Circular Queue
The Queue is: 2 5 6 7

Article is contributed by Rahit Saha