Topic 3

Circular Queue (Array)

Efficient Array Storage

The Problem with Simple Array Queue: When we dequeue elements, the spaces at the front of the array become empty, but the rear pointer keeps moving forward until it hits the end. We get a "Queue is Full" error even if there is space at the front!

The Solution: Circular Queue uses the modulo operator (% size) to wrap the rear (and front) pointers back to the beginning of the array, reusing empty spaces.

Circular Array (Wrapped)

front↓

rear↓

🧠

Modulo is the magic: (rear + 1) % size wraps 4 back to 0 when size is 5.

⚠️

isFull Condition: (rear + 1) % size == front means the rear is right behind the front.

📝

First Enqueue: If front == -1, it must be set to 0 when the first item is added!

📝

Dequeue: If front == rear (only 1 element left), reset both to -1. Else, front = (front + 1) % size;

circular-queue

#include <iostream>
using namespace std;

class CircularQueue {
private:
    int* arr;
    int front, rear, size;

public:
    CircularQueue(int s) {
        size = s;
        arr = new int[size];
        front = rear = -1;
    }

    bool isFull() {
        return (rear + 1) % size == front;
    }

    bool isEmpty() {
        return front == -1;
    }

    // Enqueue
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is Full!" << endl;
            return;
        }
        if (front == -1) front = 0;   // First element
        rear = (rear + 1) % size;
        arr[rear] = value;
        cout << value << " enqueued to queue" << endl;
    }

    // Dequeue
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is Empty!" << endl;
            return;
        }
        cout << arr[front] << " dequeued from queue" << endl;
        if (front == rear)             // Last element removed
            front = rear = -1;
        else
            front = (front + 1) % size;
    }

    // Display
    void display() {
        if (isEmpty()) {
            cout << "Queue is Empty!" << endl;
            return;
        }
        cout << "Queue elements: ";
        int i = front;
        while (true) {
            cout << arr[i] << " ";
            if (i == rear) break;
            i = (i + 1) % size;
        }
        cout << endl;
    }

    ~CircularQueue() {
        delete[] arr;
    }
};

int main() {
    CircularQueue q(5);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);
    q.enqueue(50);
    q.display();          // 10 20 30 40 50

    q.dequeue();
    q.dequeue();
    q.display();          // 30 40 50

    q.enqueue(60);        // Wraps around!
    q.enqueue(70);
    q.display();          // 30 40 50 60 70

    return 0;
}