Circular Queue Using Array – Circular Queue in DSA C++ – Circular Queue Operations in Data Structure

A Circular Queue is a type of queue data structure where the last position is connected back to the first position, forming a circle.

Key Features:

1. Circular Structure:

• Unlike a linear queue, the last element of the circular queue connects to the first element.
• Helps in efficient memory utilization by reusing spaces left empty after dequeuing.

2. Front and Rear Pointers:

• Front: Points to the first element of the queue.
• Rear: Points to the last element of the queue.

3. Rear and Empty Conditions:

• The queue is empty when front == -1 (initial state).
• The queue is full when (rear + 1) % size == front.

4. Efficient Use of Space:

• Unlike a linear queue, where dequeuing creates unused spaces, a circular queue reuses these spaces.

Operations in Circular Queue:

1. Enqueue (Insert an element):

• Check if the queue is full: (rear + 1) % size == front.
• If the queue is not full, update rear as (rear + 1) % size and insert the element at the rear index of the circular queue.

2. Dequeue (Remove an element):

• Check if the queue is empty: front == -1.
• If not empty, remove the element pointed by front.
• Update front to (front + 1) % size. If the queue becomes empty, reset front and rear to -1.

3. Peek (Access the front element):

• Return the element at front if the queue is not empty.

4. Is Full / Is Empty:

• Check the respective conditions for full and empty states.

Example:

Queue size = 5

• Initially: front = -1, rear = -1
• Enqueue(1): Insert 1
  • front = 0, rear = 0
  • Queue: [1, , , , ]

• Enqueue(2): Insert 2
  • rear = 1
  • Queue: [1, 2, , , _]

• Enqueue(3), Enqueue(4), Enqueue(5):
  • rear = 4
  • Queue: [1, 2, 3, 4, 5]

• Dequeue(): Remove 1
  • front = 1
  • Queue: [ _ , 2, 3, 4, 5]

• Enqueue(8): Reuse space at index 0.
  • rear = 0
  • Queue: [ 8, 2, 3, 4, 5]

Advantages:

1. Optimized memory usage.
2. Efficient operations as no shifting of elements is needed.

Disadvantages:

1. More complex implementation than linear queues.
2. Requires careful handling of front and rear pointers.

This is why circular queues are widely used in situations like CPU scheduling, buffer management, and handling streaming data.

Here’s the code for implementing a Circular Queue in C++:

#include <iostream>
using namespace std;
int CircularQueue[5], n = 5, x, y, front = -1, rear = -1;
void Insert() 
{
    if ((rear + 1) % n == front) 
    {
        cout << "Queue is full" << endl;
    } 
    else 
    {
        if (front == -1) 
        {
            front = 0;
        }
        cout << "Insert the element in Queue: ";
        cin >> x;
        rear = (rear + 1) % n;
        CircularQueue[rear] = x;
    }
}

int Peek() 
{
    if (front == -1) 
    {
        return 0;
    } 
    else 
    {
        return CircularQueue[front];
    }
}
void Display() 
{
    if (front == -1) 
    {
        cout << "Queue is empty" << endl;
    } 
    else 
    {
        cout << "Queue elements are: " << endl;
        int i = front;
        while (true) 
        {
            cout << CircularQueue[i] << " ";
            if (i == rear) 
            {    
                break;
            }
            i = (i + 1) % n;   
        }
        cout << endl;
    }
}
void Delete() 
{
    if (front == -1) 
    {
        cout << "Queue is empty" << endl;
    } 
    else 
    {
        cout << "Element deleted from Queue is: " << CircularQueue[front] << endl;
        if (front == rear) 
        {
            front = -1;
            rear = -1;
        } 
        else 
        {
            front = (front + 1) % n;
        }
    }
}

int main() 
{
    Insert(); 
    Insert(); 
    Insert(); 
    Insert(); 
    Insert(); 
    Insert();
    y = Peek();
    if (y == 0) 
    {
        cout << "Queue is empty" << endl;
    } 
    else 
    {
        cout << "Front element of the Queue is: " << y << endl;
    }
    Display(); 
    Delete(); 
    Display();
    Insert ();
    Display ();
    Insert ();
    return 0;
}