Circular Queue Implementation Using Array in DSA Java

Mental Model

A circular queue uses an array where the end connects back to the start, so we can 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
Indexes: 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), then enqueue 1 element (60) to test wrap-around.

Goal: Show how elements wrap around in the array and how front and rear pointers move in a circular queue.

Step 1: Enqueue 10

front=0, rear=0, array=[10, null, null, null, null]

Why: Start inserting at index 0, both front and rear point here.

Step 2: Enqueue 20

front=0, rear=1, array=[10, 20, null, null, null]

Why: Move rear forward to index 1 to insert next element.

Step 3: Enqueue 30

front=0, rear=2, array=[10, 20, 30, null, null]

Why: Rear moves to index 2 for next insertion.

Step 4: Dequeue (remove 10)

front=1, rear=2, array=[10, 20, 30, null, null]

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, null]

Why: Rear moves to index 3 to insert 40.

Step 6: Enqueue 50

front=1, rear=4, array=[10, 20, 30, 40, 50]

Why: Rear moves to index 4 to insert 50.

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, inserts 60.

Step 8: Queue is full now, next enqueue would fail

front=1, rear=0, array=[60, 20, 30, 40, 50]

Why: Rear + 1 mod size equals front means queue is full.

Result:

front=1, rear=0, array=[60, 20, 30, 40, 50]

Annotated Code

DSA Java

public class CircularQueue {
    private int[] arr;
    private int front, rear, size, capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
        front = -1;
        rear = -1;
        size = 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue " + value);
            return;
        }
        if (isEmpty()) {
            front = 0;
        }
        rear = (rear + 1) % capacity; // move rear circularly
        arr[rear] = value;
        size++;
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return -1;
        }
        int result = arr[front];
        front = (front + 1) % capacity; // move front circularly
        size--;
        if (size == 0) { // reset pointers when queue becomes empty
            front = -1;
            rear = -1;
        }
        return result;
    }

    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return;
        }
        System.out.print("Queue elements: ");
        int count = 0;
        int i = front;
        while (count < size) {
            System.out.print(arr[i] + " ");
            i = (i + 1) % capacity;
            count++;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue(5);
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.printQueue();

        queue.dequeue();
        queue.printQueue();

        queue.enqueue(40);
        queue.enqueue(50);
        queue.printQueue();

        queue.enqueue(60); // wrap-around enqueue
        queue.printQueue();

        queue.enqueue(70); // should fail - queue full
    }
}

rear = (rear + 1) % capacity; // move rear circularly

advance rear pointer circularly to next index for insertion

front = (front + 1) % capacity; // move front circularly

advance front pointer circularly to next index for removal

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

reset pointers when queue becomes empty

while (count < size) { System.out.print(arr[i] + " "); i = (i + 1) % capacity; count++; }

iterate circularly from front to rear to print elements

Output

Queue elements: 10 20 30 

Queue elements: 20 30 

Queue elements: 20 30 40 50 

Queue elements: 20 30 40 50 60 

Queue is full. Cannot enqueue 70

Complexity Analysis

Time: O(1) for enqueue and dequeue because we use pointers to directly access positions without shifting elements.

Space: O(n) because we use a fixed-size array of capacity 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 O(1).

Edge Cases

Enqueue when queue is full

Enqueue is rejected with a message, no overwrite occurs.

DSA Java

if (isFull()) { System.out.println("Queue is full. Cannot enqueue " + value); return; }

Dequeue when queue is empty

Dequeue returns -1 and prints a message indicating empty queue.

DSA Java

if (isEmpty()) { System.out.println("Queue is empty. Cannot dequeue."); return -1; }

Queue becomes empty after dequeue

Front and rear pointers reset to -1 to indicate empty queue.

DSA Java

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

When to Use This Pattern

When you see a fixed-size queue where elements need to be reused efficiently without shifting, reach for the circular queue pattern because it uses wrap-around pointers to save time and space.

Common Mistakes

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

Mistake: Not resetting front and rear to -1 when queue becomes empty, causing incorrect empty checks.
Fix: Reset front and rear to -1 when size reaches zero after dequeue.

Summary

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

Use when you want a queue with fixed capacity that efficiently uses all array slots without shifting elements.

The key insight is to treat the array as circular by moving pointers with modulo arithmetic to wrap around.

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 allows storing different data types in the same queue.

B. It efficiently utilizes the array space by reusing empty slots after dequeue operations.

C. It automatically sorts the elements in the queue.

D. It uses less memory than a linear queue.

Solution

1. Step 1: Understand linear queue limitation

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

2. Step 2: Circular queue advantage

   A circular queue connects the end of the array back to the front, allowing reuse of empty slots and efficient space usage.

3. Final Answer:

   It efficiently utilizes the array space by reusing empty slots after dequeue operations. -> Option B

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space after dequeue, unlike linear queue [OK]

Common Mistakes:

• Thinking circular queue sorts elements
• Believing circular queue uses less memory
• Confusing data type flexibility with queue type

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 == (front + 1) % n

C. front == rear

D. rear == n - 1

Solution

1. Step 1: Understand circular queue full condition

   In a circular queue, the queue is full when the next position of rear (rear + 1 modulo n) is equal to front.

2. Step 2: Apply modulo for wrap-around

   Using modulo ensures the rear wraps to the start of the array, so full condition is front == (rear + 1) % n.

3. Final Answer:

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

4. Quick Check:

   Full if next rear equals front [OK]

Hint: Full when front is just ahead of rear in circular manner [OK]

Common Mistakes:

• Using rear == (front + 1) % n (wrong direction)
• Checking front == rear (means empty, not full)
• Ignoring modulo wrap-around

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

medium

A. front = 2, rear = 1

B. front = 0, rear = 4

C. front = 1, rear = 3

D. front = 1, rear = 0

Solution

1. Step 1: Trace each operation step-by-step

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

2. Step 2: Final front and rear values

   After last enqueue, front=1, rear=0

3. Final Answer:

   front = 1, rear = 0 -> Option D

4. Quick Check:

   Wrap rear with modulo, front moves on dequeue [OK]

Hint: Update rear with modulo; front moves on dequeue [OK]

Common Mistakes:

• Not wrapping rear index after reaching array end
• Not updating front after dequeue
• Confusing initial front and rear values

4. Given the following snippet of a circular queue enqueue method, identify the bug:

void enqueue(int value) {
  if ((rear + 1) % size == front) {
    System.out.println("Queue is full");
    return;
  }
  if (front == -1) front = 0;
  rear = (rear + 1) % size;
  queue[rear] = value;
}

medium

A. The front pointer should be updated after enqueue.

B. The condition to check full queue is incorrect.

C. The rear pointer is updated before inserting the value.

D. The method does not handle empty queue initialization.

Solution

1. Step 1: Identify standard enqueue order

   In standard circular queue implementations (wasting one slot to distinguish empty/full), the value is inserted at the current rear first: queue[rear] = value; then rear = (rear + 1) % size.

2. Step 2: Problem with given code

   This code updates rear first, then inserts. This causes false positives in the full check after dequeue operations make the queue empty, as front == (old rear + 1) % size, matching the full condition.

3. Final Answer:

   The rear pointer is updated before inserting the value. -> Option C

4. Quick Check:

   Standard order: insert then increment rear [OK]

Hint: Check pointer updates order carefully in enqueue method [OK]

Common Mistakes:

• Confusing front and rear updates
• Misunderstanding full condition logic
• Ignoring initial empty queue setup

5. You have a circular queue of size 6. After performing several enqueue and dequeue operations, the front is at index 4 and rear is at index 2. Which of the following statements is true about the queue's current state?

hard

A. The queue has elements from index 4 to 5 and 0 to 2.

B. The queue is full.

C. The queue is empty.

D. The queue has elements only between indices 2 and 4.

Solution

1. Step 1: Understand circular queue indexing

   With front at 4 and rear at 2 in a size 6 queue, the queue wraps around the end of the array.

2. Step 2: Identify occupied indices

   Elements are from front (4) to end (5), then from start (0) to rear (2), so indices 4,5,0,1,2 hold elements.

3. Final Answer:

   The queue has elements from index 4 to 5 and 0 to 2. -> Option A

4. Quick Check:

   Wrap-around means elements split across array ends [OK]

Hint: Front > rear means queue wraps around array end [OK]

Common Mistakes:

• Assuming front > rear means empty queue
• Thinking queue is full when front > rear
• Ignoring wrap-around in circular queue