Circular Queue Implementation Using Array in DSA Python - Execution Trace

Concept Flow - Circular Queue Implementation Using Array

Initialize queue with fixed size

↓

Enqueue: Check if queue is full?

Yes→Reject enqueue

No↓

Add element at rear index

↓

Update rear index (rear = (rear + 1) % size)

↓

Increment count

↓

Dequeue: Check if queue is empty?

Yes→Reject dequeue

No↓

Remove element at front index

↓

Update front index (front = (front + 1) % size)

↓

Decrement count

↓

Repeat enqueue/dequeue as needed

This flow shows how a circular queue uses a fixed-size array with front and rear pointers that wrap around using modulo to reuse space.

Execution Sample

DSA Python

size = 5
queue = [None]*size
front = 0
rear = 0
count = 0

# Enqueue 10
if count < size:
  queue[rear] = 10
  rear = (rear + 1) % size
  count += 1

# Enqueue 20
if count < size:
  queue[rear] = 20
  rear = (rear + 1) % size
  count += 1

# Dequeue
if count > 0:
  removed = queue[front]
  queue[front] = None
  front = (front + 1) % size
  count -= 1

This code enqueues two elements (10, 20) and then dequeues one element from a circular queue of size 5.

Execution Table

Step	Operation	front	rear	count	Queue State	Explanation
0	Initialize queue	0	0	0	[None, None, None, None, None]	Queue is empty, front and rear at 0
1	Enqueue 10	0	1	1	[10, None, None, None, None]	10 added at index 0, rear moves to 1
2	Enqueue 20	0	2	2	[10, 20, None, None, None]	20 added at index 1, rear moves to 2
3	Dequeue	1	2	1	[None, 20, None, None, None]	10 removed from index 0, front moves to 1
4	Enqueue 30	1	3	2	[None, 20, 30, None, None]	30 added at index 2, rear moves to 3
5	Enqueue 40	1	4	3	[None, 20, 30, 40, None]	40 added at index 3, rear moves to 4
6	Enqueue 50	1	0	4	[None, 20, 30, 40, 50]	50 added at index 4, rear wraps to 0
7	Enqueue 60	1	0	4	[None, 20, 30, 40, 50]	Queue full, enqueue rejected
8	Dequeue	2	0	3	[None, None, 30, 40, 50]	20 removed from index 1, front moves to 2
9	Enqueue 60	2	1	4	[60, None, 30, 40, 50]	60 added at index 0, rear moves to 1
10	Dequeue	3	1	3	[60, None, None, 40, 50]	30 removed from index 2, front moves to 3
11	Dequeue	4	1	2	[60, None, None, None, 50]	40 removed from index 3, front moves to 4
12	Dequeue	0	1	1	[60, None, None, None, None]	50 removed from index 4, front wraps to 0
13	Dequeue	1	1	0	[None, None, None, None, None]	60 removed from index 0, front moves to 1, queue empty
14	Dequeue	1	1	0	[None, None, None, None, None]	Queue empty, dequeue rejected

💡 Execution stops after last dequeue attempt when queue is empty (count=0).

Variable Tracker

Variable	Start	After Step 1	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
front	0	0	0	1	1	1	1	1	2	2	3	4	0	1	1
rear	0	1	2	2	3	4	0	0	0	1	1	1	1	1	1
count	0	1	2	1	2	3	4	4	3	4	3	2	1	0	0

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, rear uses modulo operation (rear = (rear + 1) % size) to wrap around. See step 6 where rear moves from 4 to 0.

Why can't we enqueue when count equals the size even if there is None space in the array?

Count tracks the number of elements. When count == size, the queue is full, so enqueue is rejected (step 7). The circular queue reuses space by wrapping pointers, not by shifting elements.

What happens when we dequeue from an empty queue?

Dequeue is rejected because count is 0 (step 14). The code checks count > 0 before dequeueing to avoid errors.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the value of rear and why?

A rear is 0 because it wrapped around after reaching the end

B rear is 5 because it moved forward by one

C rear is 4 because it did not move

D rear is 1 because it reset to the start

💡 Hint

Check the 'rear' column at step 6 and the explanation about wrapping.

At which step does the queue become full for the first time?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at the 'count' column and queue state to see when count equals size.

If we dequeue at step 14, what will be the front pointer value?

A 1

B 0

C Cannot dequeue, front stays the same

D 2

💡 Hint

See step 14 where dequeue is rejected because queue is empty.

Concept Snapshot

Circular Queue using array:
- Fixed size array with front, rear pointers
- Enqueue at rear, then rear = (rear + 1) % size
- Dequeue at front, then front = (front + 1) % size
- Track count to check full (count == size) or empty (count == 0)
- Wrap pointers to reuse space without shifting elements

Full Transcript

A circular queue uses a fixed-size array and two pointers: front and rear. Enqueue adds an element at rear and moves rear forward using modulo to wrap around. Dequeue removes an element from front and moves front forward similarly. A count variable tracks how many elements are in the queue to detect full or empty states. This avoids shifting elements and efficiently uses space. The execution table shows enqueue and dequeue steps, pointer movements, and queue state changes. Key moments clarify pointer wrapping, full queue detection, and empty queue handling.

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 efficiently uses the available space by reusing freed slots.

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

C. It automatically sorts the elements in the queue.

D. It eliminates the need for front and rear pointers.

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 is space at the front.

2. Step 2: Circular queue reuses space

   Circular queue connects the end of the array back to the front, allowing reuse of freed slots and efficient space usage.

3. Final Answer:

   It efficiently uses the available space by reusing freed slots. -> Option A

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space unlike linear queue [OK]

Common Mistakes:

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

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

easy

A. if rear == max_size - 1

B. if rear == front

C. if front == -1

D. if (rear + 1) % max_size == front

Solution

1. Step 1: Understand full condition in circular queue

   The queue is full when the next position of rear (circularly) is front.

2. Step 2: Use modulo for circular increment

   Using modulo operator, (rear + 1) % max_size gives the next position circularly.

3. Final Answer:

   if (rear + 1) % max_size == front -> Option D

4. Quick Check:

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

Hint: Full when next rear equals front using modulo [OK]

Common Mistakes:

• Checking rear == front means full (actually empty)
• Using rear == max_size - 1 ignores circular wrap
• Checking front == -1 means empty, not full

3. Consider this circular queue code snippet with max_size = 5:

front = 0
rear = 3
queue = [10, 20, 30, 40, None]

# Enqueue operation
rear = (rear + 1) % 5
queue[rear] = 50

# Dequeue operation
front = (front + 1) % 5

print(queue)

What will be the printed output?

medium

A. [10, 20, 30, 40, 50] with front=1 and rear=4

B. [10, 20, 30, 40, None]

C. [10, 20, 30, 40, 50]

D. [10, 20, 30, 40, 50] with front=0 and rear=4

Solution

1. Step 1: Perform enqueue operation

   rear moves from 3 to (3+1)%5 = 4; queue[4] = 50; queue becomes [10, 20, 30, 40, 50]

2. Step 2: Perform dequeue operation

   front moves from 0 to (0+1)%5 = 1; front=1, rear=4

3. Final Answer:

   [10, 20, 30, 40, 50] with front=1 and rear=4 -> Option A

4. Quick Check:

   Enqueue rear=4, Dequeue front=1 [OK]

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

Common Mistakes:

• Ignoring front and rear pointer updates
• Assuming queue content changes on dequeue
• Confusing front and rear positions

4. The following code snippet for dequeue operation in a circular queue has a bug:

def dequeue(queue, front, rear, max_size):
    if front == -1:
        return None, front, rear  # Queue empty
    data = queue[front]
    if front == rear:
        front = rear = -1
    else:
        front = (front + 1) % max_size
    return data, front, rear

# Initial state
queue = [10, 20, 30, 40, 50]
front = 0
rear = 4

# Dequeue call
value, front, rear = dequeue(queue, front, rear, 5)
print(value, front, rear)

What is the bug in this code?

medium

A. The condition to check empty queue should be rear == -1, not front == -1.

B. The function does not update the queue after dequeue.

C. The function does not handle the case when queue is full.

D. The function incorrectly resets front and rear to -1 when queue becomes empty.

Solution

1. Step 1: Check queue update after dequeue

   The dequeue operation removes the element logically by moving front, but the queue array still holds the old value.

2. Step 2: Identify missing update

   To avoid stale data, the dequeued position should be cleared or updated (e.g., set to None) after dequeue.

3. Final Answer:

   The function does not update the queue after dequeue. -> Option B

4. Quick Check:

   Queue array update after dequeue [OK]

Hint: Dequeue should clear or update the dequeued slot [OK]

Common Mistakes:

• Checking only front for empty queue
• Not resetting pointers correctly after last dequeue
• Ignoring queue full condition in dequeue

5. You have a circular queue of size 6 (indices 0 to 5). Initially, front = 4 and rear = 2. The queue array is:
[70, 80, 90, None, 40, 50]

Which of the following sequences of operations will correctly enqueue 100 and dequeue two elements, updating front and rear properly?

hard

A. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6

B. Enqueue: rear = (rear + 2) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6

C. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6

D. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 2) % 6

Solution

1. Step 1: Enqueue operation

   rear = (2 + 1) % 6 = 3; queue[3] = 100; queue becomes [70, 80, 90, 100, 40, 50]

2. Step 2: Dequeue two elements

   front moves twice: front = (4 + 1) % 6 = 5, then front = (5 + 1) % 6 = 0

3. Final Answer:

   Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6 -> Option C

4. Quick Check:

   One enqueue + two dequeues update pointers correctly [OK]

Hint: Increment pointers modulo size for each enqueue/dequeue [OK]

Common Mistakes:

• Incrementing rear or front by more than 1 at once
• Not using modulo for circular wrap
• Dequeueing fewer or more times than asked