Circular Queue Implementation Using Array in DSA C++

Mental Model

A circular queue uses an array where the end connects back to the start, so we reuse empty spaces efficiently.

Analogy: Imagine a round table with seats numbered in a circle. When you reach the last seat, you go back to the first seat to sit if it's empty.

Front -> [ ] [ ] [ ] [ ] [ ] ← Rear
Index -> 0   1   2   3   4

Dry Run Walkthrough

Input: Create circular queue of size 5, enqueue 3 elements (10, 20, 30), dequeue 1 element, enqueue 2 elements (40, 50), enqueue 1 element (60) to test wrap-around

Goal: Show how elements wrap around in the array and how front and rear pointers move

Step 1: Enqueue 10

Front=0, Rear=0, Array=[10, _, _, _, _]

Why: First element goes to index 0, front and rear both point here

Step 2: Enqueue 20

Front=0, Rear=1, Array=[10, 20, _, _, _]

Why: Rear moves forward to index 1 to add next element

Step 3: Enqueue 30

Front=0, Rear=2, Array=[10, 20, 30, _, _]

Why: Rear moves forward to index 2 to add next element

Step 4: Dequeue one element (10)

Front=1, Rear=2, Array=[10, 20, 30, _, _]

Why: Front moves forward to index 1, element 10 is removed logically

Step 5: Enqueue 40

Front=1, Rear=3, Array=[10, 20, 30, 40, _]

Why: Rear moves forward to index 3 to add new element

Step 6: Enqueue 50

Front=1, Rear=4, Array=[10, 20, 30, 40, 50]

Why: Rear moves forward to index 4 to add new element

Step 7: Enqueue 60 (wrap-around)

Front=1, Rear=0, Array=[60, 20, 30, 40, 50]

Why: Rear wraps to index 0 because array end reached, reusing space

Result:

Front=1, Rear=0, Array=[60, 20, 30, 40, 50]
Queue order: 20 -> 30 -> 40 -> 50 -> 60 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

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

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

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is full\n";
            return;
        }
        if (isEmpty()) {
            front = 0; // first element added
        }
        rear = (rear + 1) % size; // move rear forward circularly
        arr[rear] = value;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty\n";
            return;
        }
        if (front == rear) {
            front = rear = -1; // queue becomes empty
        } else {
            front = (front + 1) % size; // move front forward circularly
        }
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty\n";
            return;
        }
        int i = front;
        while (true) {
            cout << arr[i] << " -> ";
            if (i == rear) break;
            i = (i + 1) % size;
        }
        cout << "null\n";
    }
};

int main() {
    CircularQueue q(5);
    q.enqueue(10); // step 1
    q.enqueue(20); // step 2
    q.enqueue(30); // step 3
    q.dequeue();   // step 4
    q.enqueue(40); // step 5
    q.enqueue(50); // step 6
    q.enqueue(60); // step 7 wrap-around
    q.display();
    return 0;
}

if (isFull()) { return; }

check if queue is full before adding

if (isEmpty()) { front = 0; }

initialize front when first element added

rear = (rear + 1) % size;

move rear pointer forward circularly

arr[rear] = value;

store new element at rear

if (front == rear) { front = rear = -1; } else { front = (front + 1) % size; }

move front pointer forward circularly or reset if queue empty

while (true) { print arr[i]; if (i == rear) break; i = (i + 1) % size; }

iterate from front to rear circularly to display queue

Output

20 -> 30 -> 40 -> 50 -> 60 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because pointers move in constant time without shifting elements

Space: O(n) because we use a fixed-size array of size n to store elements

vs Alternative: Compared to a normal queue using array that shifts elements on dequeue (O(n)), circular queue avoids shifting by wrapping pointers, making operations efficient

Edge Cases

Enqueue when queue is full

Prints 'Queue is full' and does not add element

DSA C++

if (isFull()) { cout << "Queue is full\n"; return; }

Dequeue when queue is empty

Prints 'Queue is empty' and does nothing

DSA C++

if (isEmpty()) { cout << "Queue is empty\n"; return; }

Dequeue last element

Resets front and rear to -1 to mark queue empty

DSA C++

if (front == rear) { front = rear = -1; }

When to Use This Pattern

When you need a fixed-size queue that efficiently reuses space without shifting elements, use a circular queue with modulo arithmetic to wrap pointers.

Common Mistakes

Mistake: Not wrapping rear or front pointers using modulo, causing index out of bounds
Fix: Always update pointers as (pointer + 1) % size to wrap around

Mistake: Not resetting front and rear to -1 when queue becomes empty after dequeue
Fix: Check if front == rear before dequeue and reset both to -1

Summary

Implements a queue using a fixed-size array where front and rear wrap around to reuse space.

Use when you want efficient enqueue and dequeue in a fixed-size buffer without shifting elements.

The key is to move front and rear pointers circularly using modulo to reuse array slots.

Practice

1. What is the main advantage of using a circular queue over a simple linear queue when implemented using an array?

easy

A. It eliminates the need for front and rear pointers

B. It allows storing different data types in the same queue

C. It automatically sorts the elements in the queue

D. It efficiently uses the array space by reusing freed slots

Solution

1. Step 1: Understand linear queue limitation

   In a linear queue using an array, once rear reaches the end, no more elements can be added even if there are empty slots at the front.

2. Step 2: Circular queue advantage

   Circular queue connects the end of the array back to the front, allowing reuse of empty slots freed by dequeuing.

3. Final Answer:

   It efficiently uses the array space by reusing freed slots -> Option D

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space freed by dequeued elements [OK]

Common Mistakes:

• Thinking circular queue sorts elements
• Believing circular queue removes need for pointers
• Assuming it supports multiple data types inherently

2. Which of the following is the correct condition to check if a circular queue is full when using an array of size n with front and rear pointers?

easy

A. front == (rear + 1) % n

B. rear == n - 1

C. front == rear

D. rear == (front + 1) % n

Solution

1. Step 1: Understand full condition in circular queue

   In circular queue, queue is full when next position of rear is front, i.e., (rear + 1) modulo n equals front.

2. Step 2: Match condition with options

   front == (rear + 1) % n matches this condition: front == (rear + 1) % n.

3. Final Answer:

   front == (rear + 1) % n -> Option A

4. Quick Check:

   Full condition = front == (rear + 1) % n [OK]

Hint: Full when front is next to rear in circular manner [OK]

Common Mistakes:

• Using rear == n - 1 which is for linear queue
• Confusing front == rear as full (actually empty)
• Swapping front and rear in condition

3. Consider a circular queue of size 5 (indices 0 to 4). Initially, front = -1 and rear = -1. After the following operations:
enqueue(10); enqueue(20); enqueue(30); dequeue(); enqueue(40); enqueue(50); dequeue(); enqueue(60);
What will be the values of front and rear?

medium

A. front = 2, rear = 1

B. front = 2, rear = 0

C. front = 3, rear = 0

D. front = 1, rear = 4

Solution

1. Step 1: Trace each operation and update pointers

   Start: front = -1, rear = -1
   enqueue(10): front=0, rear=0
   enqueue(20): rear=1
   enqueue(30): rear=2
   dequeue(): front=1
   enqueue(40): rear=3
   enqueue(50): rear=4
   dequeue(): front=2
   enqueue(60): rear=(4+1)%5=0

2. Step 2: Final pointer values

   front = 2, rear = 0 which corresponds to front = 2, rear = 0.

3. Final Answer:

   front = 2, rear = 0 -> Option B

4. Quick Check:

   Trace pointers carefully [OK]

Hint: Track front and rear after each enqueue/dequeue [OK]

Common Mistakes:

• Not updating rear circularly after last index
• Confusing front and rear updates on dequeue
• Ignoring initial front = -1 condition

4. The following code snippet is part of a circular queue implementation. Identify the bug:

void enqueue(int value) {
  if ((rear + 1) % size == front) {
    cout << "Queue is full" << endl;
    return;
  }
  if (front == -1) front = 0;
  rear = (rear + 1) % size;
  arr[rear] = value;
}

medium

A. No bug, code is correct

B. The front pointer should be updated after rear

C. The initial check for empty queue should be before full check

D. The condition to check full queue is incorrect

Solution

1. Step 1: Analyze full queue condition

   The condition (rear + 1) % size == front correctly checks if queue is full in circular queue.

2. Step 2: Check front pointer update and enqueue steps

   If queue is empty (front == -1), front is set to 0 before inserting.
   rear is updated circularly and value inserted at arr[rear].

3. Final Answer:

   No bug, code is correct -> Option A

4. Quick Check:

   Full check and pointers update are correct [OK]

Hint: Full check uses modulo; front updated only if empty [OK]

Common Mistakes:

• Misplacing front update after rear
• Incorrect full condition without modulo
• Checking empty after full condition

5. You have a circular queue of size 6. After performing the following operations:
enqueue(5); enqueue(10); enqueue(15); dequeue(); dequeue(); enqueue(20); enqueue(25); enqueue(30); enqueue(35);
What will be the sequence of elements in the queue from front to rear?

hard

A. 20 -> 25 -> 30 -> 35

B. 10 -> 15 -> 20 -> 25 -> 30 -> 35

C. 15 -> 20 -> 25 -> 30 -> 35

D. 5 -> 10 -> 15 -> 20 -> 25 -> 30

Solution

1. Step 1: Trace each operation and queue content

   Start empty.
   enqueue(5): queue = [5]
   enqueue(10): queue = [5,10]
   enqueue(15): queue = [5,10,15]
   dequeue(): removes 5, queue = [10,15]
   dequeue(): removes 10, queue = [15]
   enqueue(20): queue = [15,20]
   enqueue(25): queue = [15,20,25]
   enqueue(30): queue = [15,20,25,30]
   enqueue(35): queue = [15,20,25,30,35]

2. Step 2: Check queue size and elements

   Queue size is 6, current elements are 5.
   From front to rear: 15 -> 20 -> 25 -> 30 -> 35

3. Final Answer:

   15 -> 20 -> 25 -> 30 -> 35 -> Option C

4. Quick Check:

   After dequeues, front moves; final elements start from 15 [OK]

Hint: Remove dequeued elements, then list remaining from front to rear [OK]

Common Mistakes:

• Forgetting to remove dequeued elements
• Listing elements before dequeue operations
• Assuming queue is full and ignoring last enqueue