Circular Queue Implementation Using Array in DSA Java - Execution Trace

Concept Flow - Circular Queue Implementation Using Array

Start

↓

Check if queue is full?

|Yes↓

Reject enqueue

No↓

Insert element at rear

↓

Update rear pointer (circular)

↓

Check if queue is empty?

|Yes↓

Reject dequeue

No↓

Remove element at front

↓

Update front pointer (circular)

↓

Repeat operations or End

The circular queue uses front and rear pointers that wrap around the array to reuse empty spaces. Enqueue inserts at rear if not full; dequeue removes from front if not empty.

Execution Sample

DSA Java

int[] queue = new int[5];
int front = -1, rear = -1;
// Enqueue 10
// Enqueue 20
// Dequeue
// Enqueue 30

This code enqueues 10 and 20, dequeues one element, then enqueues 30 in a circular queue of size 5.

Execution Table

Step	Operation	Front	Rear	Queue Array	Pointer Changes	Visual State
1	Initialize queue	-1	-1	[_, _, _, _, _]	front = -1, rear = -1	Empty queue
2	Enqueue 10	0	0	[10, _, _, _, _]	front = 0 (from -1), rear = 0 (from -1)	10 -> _ -> _ -> _ -> _
3	Enqueue 20	0	1	[10, 20, _, _, _]	rear = 1	10 -> 20 -> _ -> _ -> _
4	Dequeue	1	1	[10, 20, _, _, _]	front = 1	10 (removed), front at 1, rear at 1 Queue: 20 -> _ -> _ -> _ -> _
5	Enqueue 30	1	2	[10, 20, 30, _, _]	rear = 2	20 -> 30 -> _ -> _ -> _
6	Enqueue 40	1	3	[10, 20, 30, 40, _]	rear = 3	20 -> 30 -> 40 -> _ -> _
7	Enqueue 50	1	4	[10, 20, 30, 40, 50]	rear = 4	20 -> 30 -> 40 -> 50 -> _
8	Enqueue 60 (wrap)	1	0	[60, 20, 30, 40, 50]	rear = 0 (wrap around)	20 -> 30 -> 40 -> 50 -> 60 (rear wraps)
9	Queue full check	1	0	[60, 20, 30, 40, 50]	No pointer change	Queue is full, cannot enqueue more
10	Dequeue	2	0	[60, 20, 30, 40, 50]	front = 2	30 -> 40 -> 50 -> 60 -> _
11	Dequeue	3	0	[60, 20, 30, 40, 50]	front = 3	40 -> 50 -> 60 -> _ -> _
12	Dequeue	4	0	[60, 20, 30, 40, 50]	front = 4	50 -> 60 -> _ -> _ -> _
13	Dequeue	0	0	[60, 20, 30, 40, 50]	front = 0 (wrap around)	60 -> _ -> _ -> _ -> _
14	Dequeue	-1	-1	[60, 20, 30, 40, 50]	front = -1, rear = -1 (queue empty)	Queue empty
15	Dequeue on empty	-1	-1	[60, 20, 30, 40, 50]	No pointer change	Cannot dequeue, queue empty

💡 Execution stops after dequeue on empty queue is rejected.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14
front	-1	0	0	1	1	1	1	1	2	3	4	0	-1
rear	-1	0	1	1	2	3	4	0	0	0	0	0	-1
queue array	[_,_,_,_,_]	[10,_,_,_,_]	[10,20,_,_,_]	[10,20,_,_,_]	[10,20,30,_,_]	[10,20,30,40,_]	[10,20,30,40,50]	[60,20,30,40,50]	[60,20,30,40,50]	[60,20,30,40,50]	[60,20,30,40,50]	[60,20,30,40,50]	[60,20,30,40,50]

Key Moments - 3 Insights

Why does the rear pointer wrap back to 0 after reaching the end of the array?

Because the queue is circular, when rear reaches the last index, it wraps to 0 to reuse empty space at the start. See step 8 in execution_table where rear changes from 4 to 0.

Why do front and rear become -1 after dequeuing the last element?

When the last element is dequeued, the queue becomes empty, so both front and rear reset to -1 to indicate empty state. See step 14 in execution_table.

Why can't we enqueue when the queue is full even if there are empty slots in the array?

Because in circular queue, full condition is when next rear position equals front. Even if some array slots look empty, they are logically occupied. See step 9 where enqueue is rejected.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the value of rear pointer after enqueueing 60?

A 0

B 5

C 4

D -1

💡 Hint

Check the 'Rear' column at step 8 in execution_table.

At which step does the queue become empty again after multiple dequeues?

A Step 12

B Step 14

C Step 10

D Step 9

💡 Hint

Look for front and rear both being -1 in execution_table.

If we try to enqueue at step 9, what happens?

A rear pointer moves forward

B enqueue is rejected because queue is full

C front pointer moves forward

D queue array resets

💡 Hint

Step 9 in execution_table shows queue full check and no pointer change.

Concept Snapshot

Circular Queue uses an array with front and rear pointers.
Enqueue adds at rear if not full; rear wraps to 0 after end.
Dequeue removes from front if not empty; front wraps similarly.
Queue is empty when front and rear are -1.
Queue is full when next rear equals front.
Pointers update circularly to reuse space.

Full Transcript

This visual execution traces a circular queue implemented using an array. The queue starts empty with front and rear pointers at -1. Enqueue operations add elements at the rear pointer, which moves forward and wraps around the array end to reuse space. Dequeue operations remove elements from the front pointer, which also moves forward circularly. The queue is full when the next rear position equals the front pointer, preventing further enqueues. When the last element is dequeued, both pointers reset to -1 indicating an empty queue. The execution table shows step-by-step pointer updates, queue array states, and visual queue contents. Key moments clarify why pointers wrap and how full and empty states are detected. The quiz tests understanding of pointer positions and queue states at various steps.

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