Circular Queue using Array in C++

Circular Queue in C++

 

A basic linear data structure is Linear queue, where you can get First in First out feature for nodes. Circular Queue is a implementation of that very linear queue in which you can overcome the problems regarding linear fixed length queues. Here is an article on how to implement a Circular Queue using array in C++.

 
Circular Queue using Array in C++ | PrepInsta
Circular queue using array
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

If we create a queue using an array, where enqueuing and dequeuing takes O(1) time and space complexity each, one the queue is full, you cannot insert new elements, also sometimes when you delete elements, the queue may be totally empty but still the front will be in the back most position, so you can’t insert any value over there.

In this meantime, a circular queue comes into the picture. In Circular queue, the front and back only overlap when the queue is empty, but there is no problem when you want to delete elements and insert them again. The front pointer wanders around the queue in the circular path.

Also : Circular Queue using Array

Members of Circular Queue:

Circular queues are almost like Linear regular Queue with some modifications.
 
  • Front : From where nodes are to be popped out.
  • Back : Back or Rear, where nodes are pushed into.
  • Enqueue : Pushing a new node at the back.
  • Dequeue : Popping out nodes from front, if any.
  • Overflow : If the Circular Queue has predefined storage and is full.
  • Underflow : If the Circular Queue is empty.
  • Size : Number of nodes present.
Circular Queue full process using array

The code to implement this:

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

class CQueue
{
  public:
  int *array,Size;
  int front,back;
  CQueue(int size)
  {
    Size=size;arraynew int[size];
    front = back = –1;
  }

int isFull()
{
    if((front==back+1)||(front == 0 &&back== Size– 1))
        return 1;
    return 0;
}
int isEmpty()
{
    if (front == –1return 1;
  return 0;
}

void enqueue(int value)
{
    cout<<“Pushing the value : “<<value<<endl;
    if (isFull())
        cout<<“Can not push “<<value<<“, The Circular Queue is Full.”<<endl;
    else
    {
        if (front == –1front = 0;
        back = (back + 1) % Size;
        array[back] = value;
  }
}

int dequeue()
{
  int element;
  if (isEmpty()) {
    cout<<“The Circular Queue is empty.”<<endl;
    return –1;
  }
    element = array[front];
    if (front ==back) {
      front = –1;
      back = –1;
    }

    else {
      front = (front + 1) % Size;
    }
    cout<<“Popping out the value : “<<element<<endl;
    return element;
  
}

void Show(){
    int i;
    if (isEmpty()) cout<<“The Circular Queue is empty.”<<endl;
    else
    {
        cout<<“The Circular Queue is :”<<endl;
        for (i=fronti!=back;i= (i+1)%Size)
            cout<<array[i]<<” “;
    cout<<array[i]<<endl;
  }
}
};

int main() {

  CQueue CQ(6);
  CQ.enqueue(2);CQ.enqueue(7);
  CQ.enqueue(3);CQ.enqueue(9);
  CQ.Show();
  CQ.enqueue(8);CQ.enqueue(4);
  CQ.enqueue(1);
  CQ.dequeue();
  
  CQ.enqueue(10);CQ.dequeue();
  CQ.Show();

  return 0;
}

Output:

Pushing the value : 2
Pushing the value : 7
Pushing the value : 3
Pushing the value : 9
The Circular Queue is :
2 7 3 9
Pushing the value : 8
Pushing the value : 4
Pushing the value : 1
Can not push 1, The Circular Queue is Full.
Popping out the value : 2
Pushing the value : 10
Popping out the value : 7
The Circular Queue is :
3 9 8 4 10

Article is contributed by Rahit Saha