Circular Queue Implementation Using Array in DSA C - Execution Trace

Concept Flow - Circular Queue Implementation Using Array

Initialize front = -1, rear = -1

↓

Enqueue Operation

↓

Check if queue is full?

↓

Reject enqueue

↓

If empty, set front=0

↓

Insert element at rear

↓

Update rear = (rear + 1) % size

↓

Dequeue Operation

↓

Check if queue is empty?

↓

Reject dequeue

↓

Remove element at front

↓

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

↓

Repeat operations as needed

This flow shows how a circular queue uses front and rear pointers to enqueue and dequeue elements in a fixed-size array, wrapping around when reaching the end.

Execution Sample

DSA C

int size = 5;
int queue[5];
int front = -1, rear = -1;
// Enqueue 10, 20, 30
// Dequeue one element
// Enqueue 40, 50, 60

This code enqueues three elements, dequeues one, then enqueues three more to show circular behavior.

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 (was -1), rear=0	10 inserted at index 0
3	Enqueue 20	0	1	[10, 20, _, _, _]	rear=1	20 inserted at index 1
4	Enqueue 30	0	2	[10, 20, 30, _, _]	rear=2	30 inserted at index 2
5	Dequeue	1	2	[10, 20, 30, _, _]	front=1	10 removed from index 0
6	Enqueue 40	1	3	[10, 20, 30, 40, _]	rear=3	40 inserted at index 3
7	Enqueue 50	1	4	[10, 20, 30, 40, 50]	rear=4	50 inserted at index 4
8	Enqueue 60 (wrap)	1	0	[60, 20, 30, 40, 50]	rear=0 (wrap)	60 inserted at index 0 (wrap)
9	Queue Full Check	1	0	[60, 20, 30, 40, 50]	front=1, rear=0	Queue is full, next enqueue rejected
10	Dequeue	2	0	[60, 20, 30, 40, 50]	front=2	20 removed from index 1
11	Dequeue	3	0	[60, 20, 30, 40, 50]	front=3	30 removed from index 2
12	Dequeue	4	0	[60, 20, 30, 40, 50]	front=4	40 removed from index 3
13	Dequeue	0	0	[60, 20, 30, 40, 50]	front=0	50 removed from index 4
14	Dequeue last element	-1	-1	[60, 20, 30, 40, 50]	front=-1, rear=-1	60 removed from index 0, queue empty
15	Queue Empty Check	-1	-1	[60, 20, 30, 40, 50]	front=-1, rear=-1	Queue is empty, dequeue rejected

💡 Execution stops as queue is full at step 9 and empty at step 15, no further enqueue or dequeue possible.

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 9	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14	After Step 15
front	-1	0	0	0	1	1	1	1	1	2	3	4	0	-1	-1
rear	-1	0	1	2	2	3	4	0	0	0	0	0	0	-1	-1

Key Moments - 3 Insights

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

Because the queue is circular, rear uses modulo operation (rear + 1) % size to wrap around. See step 8 in execution_table where rear moves from 4 to 0.

Why do we reset front and rear to -1 after removing the last element?

When front equals rear and we dequeue, the queue becomes empty. Resetting front and rear to -1 marks the empty state. See step 14 in execution_table.

How do we know the queue is full?

Queue is full when the next rear position equals front. At step 9, rear=0 and front=1, so next enqueue is rejected because (rear + 1) % size == front.

Visual Quiz - 3 Questions

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

A 4

B 0

C 1

D 3

💡 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 14

B Step 13

C Step 12

D Step 15

💡 Hint

Look at front and rear values resetting to -1 in variable_tracker and execution_table.

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

A Element is added at rear=1

B front pointer moves forward

C Queue is full, enqueue rejected

D Queue becomes empty

💡 Hint

See 'Queue Full Check' operation and 'Visual State' at step 9 in execution_table.

Concept Snapshot

Circular Queue uses a fixed-size array with front and rear pointers.
Enqueue adds at rear, dequeue removes from front.
Pointers wrap around using modulo to reuse space.
Queue is empty when front and rear are -1.
Queue is full when next rear equals front.
Reset pointers when queue becomes empty after dequeue.

Full Transcript

This visualization shows how a circular queue works using an array. We start with front and rear pointers at -1, meaning the queue is empty. When we enqueue, if the queue is empty, front is set to 0. Rear moves forward to add elements. When rear reaches the end of the array, it wraps around to 0 using modulo operation. Dequeue removes elements from front and moves front forward similarly. When the last element is removed, front and rear reset to -1 to mark empty queue. The queue is full when the next rear position equals front, preventing further enqueue. This step-by-step trace helps understand how circular queues efficiently use array space by wrapping pointers.

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 automatically sorts the elements in the queue

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

C. It increases the maximum size of the queue beyond the array length

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 the 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

   A circular queue connects the end of the array back to the front, allowing reuse of empty slots freed by dequeuing, thus using space efficiently.

3. Final Answer:

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

4. Quick Check:

   Circular queue reuses space = Advantage [OK]

Hint: Circular queue reuses space freed by dequeue [OK]

Common Mistakes:

• Thinking circular queue increases array size
• Believing it sorts elements automatically
• 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 indices?

easy

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

B. front == rear

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

D. rear == n - 1

Solution

1. Step 1: Recall circular queue full condition

   The queue is full when the next position of rear (circularly) is front, meaning no space to insert new element.

2. Step 2: Express condition mathematically

   This condition is: front == (rear + 1) % n, where % is modulo operator to wrap around.

3. Final Answer:

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

4. Quick Check:

   Full if front is next to rear circularly = Condition B [OK]

Hint: Full when front is just after rear modulo array size [OK]

Common Mistakes:

• Using rear == (front + 1) % n (wrong direction)
• Checking front == rear (means empty, not full)
• Checking rear == n - 1 (linear queue 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), enqueue(60)
What will be the values of front and rear?

medium

A. front = 1, rear = 0

B. front = 0, rear = 4

C. front = 1, rear = 3

D. front = 2, rear = 1

Solution

1. Step 1: Trace enqueue and dequeue operations

   Start: front = -1, rear = -1
   enqueue(10): front=0, rear=0
   enqueue(20): rear=1
   enqueue(30): rear=2
   dequeue(): front=1 (removed 10)
   enqueue(40): rear=3
   enqueue(50): rear=4
   enqueue(60): rear wraps to 0 (circular)

2. Step 2: Final front and rear values

   After last enqueue, front=1, rear=0

3. Final Answer:

   front = 1, rear = 0 -> Option A

4. Quick Check:

   After wrap, rear=0 and front moved to 1 [OK]

Hint: Track front/rear step-by-step with wrap-around [OK]

Common Mistakes:

• Not updating front after dequeue
• Forgetting rear wraps to 0 after reaching end
• Mixing front and rear indices

4. Given the following code snippet for dequeue operation in a circular queue, identify the error:

int dequeue() {
  if (front == -1) {
    printf("Queue is empty\n");
    return -1;
  }
  int data = queue[front];
  if (front == rear) {
    front = rear = -1;
  } else {
    front = front + 1;
  }
  return data;
}

medium

A. front should be updated as (front + 1) % size to wrap around

B. rear should be incremented instead of front

C. The check for empty queue is incorrect

D. Data should be returned after updating front

Solution

1. Step 1: Understand circular queue front update

   In circular queue, front index must wrap around using modulo when incremented to stay within array bounds.

2. Step 2: Identify error in front update

   Code uses front = front + 1; which can go beyond array size. Correct is front = (front + 1) % size.

3. Final Answer:

   front should be updated as (front + 1) % size to wrap around -> Option A

4. Quick Check:

   Use modulo for front increment in circular queue [OK]

Hint: Use modulo when incrementing front or rear [OK]

Common Mistakes:

• Incrementing front without modulo wrap
• Confusing front and rear updates
• Returning data before updating front

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

hard

A. 5 -> 10 -> 15 -> 20 -> 25 -> 30 -> null

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

C. 10 -> 15 -> 20 -> 25 -> 30 -> null

D. 20 -> 25 -> 30 -> 35 -> 5 -> null

Solution

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

   Start front = -1, rear = -1
   enqueue(5): front=0, rear=0, queue=[5]
   enqueue(10): rear=1, queue=[5,10]
   enqueue(15): rear=2, queue=[5,10,15]
   dequeue(): front=1 (removed 5)
   dequeue(): front=2 (removed 10)
   enqueue(20): rear=3, queue=[5,10,15,20]
   enqueue(25): rear=4, queue=[5,10,15,20,25]
   enqueue(30): rear=5, queue=[5,10,15,20,25,30]
   enqueue(35): rear wraps to 0, queue=[35,10,15,20,25,30]

2. Step 2: Identify current front and rear and queue content

   front=2, rear=0
   Queue elements from front to rear circularly: 15 (index 2), 20 (3), 25 (4), 30 (5), 35 (0)

3. Final Answer:

   15 -> 20 -> 25 -> 30 -> 35 -> null -> Option B

4. Quick Check:

   Queue content from front to rear matches 15 -> 20 -> 25 -> 30 -> 35 -> null [OK]

Hint: Track front and rear indices carefully with wrap-around [OK]

Common Mistakes:

• Ignoring wrap-around when rear reaches end
• Listing elements linearly without circular order
• Forgetting to update front after dequeues