Circular Queue Implementation Using Array in DSA C++ - Execution Trace

Concept Flow - Circular Queue Implementation Using Array

Initialize front = -1, rear = -1

↓

Check if queue is full?

↓

Reject enqueue

↓

Update rear (circular)

↓

If front == -1, set front = 0

↓

Queue updated

↓

Check if queue is empty?

↓

Reject dequeue

↓

Update front (circular)

↓

If front passes rear, reset front and rear to -1

↓

Queue updated

This flow shows how a circular queue uses front and rear pointers to enqueue and dequeue elements in a circular manner within a fixed-size array.

Execution Sample

DSA C++

int queue[5];
int front = -1, rear = -1;

// Enqueue 10
// Enqueue 20
// Dequeue
// Enqueue 30
// Enqueue 40

This code enqueues two elements, dequeues one, then enqueues two more in a circular queue of size 5.

Execution Table

Step	Operation	front	rear	Queue State	Pointer Changes	Visual State
1	Initialize queue	-1	-1	[_, _, _, _, _]	front = -1, rear = -1	Empty queue
2	Enqueue 10	0	0	[10, _, _, _, _]	rear: -1 -> 0, front: -1 -> 0	10 -> _ -> _ -> _ -> _ (circular)
3	Enqueue 20	0	1	[10, 20, _, _, _]	rear: 0 -> 1	10 -> 20 -> _ -> _ -> _ (circular)
4	Dequeue	1	1	[10, 20, _, _, _]	front: 0 -> 1	10 (removed), front at index 1, queue: 20 -> _ -> _ -> _ (circular)
5	Enqueue 30	1	2	[10, 20, 30, _, _]	rear: 1 -> 2	20 -> 30 -> _ -> _ -> 10 (old) (circular)
6	Enqueue 40	1	3	[10, 20, 30, 40, _]	rear: 2 -> 3	20 -> 30 -> 40 -> _ -> 10 (old) (circular)
7	Final State	1	3	[10, 20, 30, 40, _]	No pointer change	Queue contains 20 (front) -> 30 -> 40 -> _ -> 10 (old) circularly

💡 No more operations; queue is partially filled with front=1 and rear=3.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
front	-1	0	0	1	1	1	1
rear	-1	0	1	1	2	3	3
queue	[_, _, _, _, _]	[10, _, _, _, _]	[10, 20, _, _, _]	[10, 20, _, _, _]	[10, 20, 30, _, _]	[10, 20, 30, 40, _]	[10, 20, 30, 40, _]

Key Moments - 3 Insights

Why does front move forward after dequeue but rear moves forward after enqueue?

Because front points to the element to remove next, so after dequeue it moves forward (see Step 4). Rear points to where to add new element, so after enqueue it moves forward (see Steps 2,3,5,6).

Why do front and rear wrap around the array?

Because the queue is circular, when rear or front reach the end of the array, they wrap to 0 to reuse space (circular update shown in Steps 5 and 6).

Why is front set to 0 when first element is enqueued?

Initially front is -1 meaning empty queue. When first element is enqueued (Step 2), front is set to 0 to point to the first element.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of rear after Step 3?

A 0

B 1

C -1

D 2

💡 Hint

Check the 'rear' column in the execution_table row for Step 3.

At which step does front move from 0 to 1?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'front' column changes in execution_table between steps.

If we enqueue one more element after Step 6, what will rear be?

A 4

B 0

C 3

D 1

💡 Hint

Rear moves forward circularly; after 3 it moves to 4 (see pattern in execution_table).

Concept Snapshot

Circular Queue using array:
- Use front and rear pointers
- Enqueue: rear = (rear + 1) % size
- Dequeue: front = (front + 1) % size
- Empty when front == -1
- Full when (rear + 1) % size == front
- Wrap pointers to reuse space

Full Transcript

This visual trace shows how a circular queue works using an array. We start with front and rear at -1 meaning empty. When we enqueue, rear moves forward circularly and front is set to 0 if queue was empty. When we dequeue, front moves forward circularly. The queue wraps around the array to reuse space. The execution table tracks front, rear, and queue state after each operation. Key moments clarify pointer movements and circular wrap. The quiz tests understanding of pointer values at 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 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