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

One kind of queue data structure is a circular queue, in which the final position is joined to the starting position in a circle.

Key Features:

1. The Circular Structure:

• Unlike a linear queue, the last element of the circular queue connects to the first element.
• Reusing empty spaces after dequeuing aids in effective memory use.

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. Effective Space Utilization:

• A circular queue reuses the unused spaces created by dequeuing, in contrast to a linear queue.

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 (take out 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): At index 0, reuse space.
  • rear = 0
  • Queue: [ 8, 2, 3, 4, 5]

Advantages:

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

Disadvantages:

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

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

Circular Queue Implementation using 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 << "The 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 << "The 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 << "The Queue is empty" << endl;
    } 
    else 
    {
        cout << "Front element of the Queue is: " << y << endl;
    }
    Display(); 
    Delete(); 
    Display();
    Insert ();
    Display ();
    Insert ();
    return 0;
}