Circular queue in Data Structures Theory - Step-by-Step Execution

Concept Flow - Circular queue

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)

↓

Dequeue: Check if queue is empty?

Yes→Reject dequeue

No↓

Remove element at front index

↓

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

↓

Repeat enqueue/dequeue as needed

A circular queue uses a fixed-size array with front and rear pointers that wrap around to reuse empty space, avoiding wasted slots.

Execution Sample

Data Structures Theory

size = 5
queue = [None]*size
front = 0
rear = 0
count = 0
# Enqueue 3 elements
for x in [10,20,30]:
  if count < size:
    queue[rear] = x
    rear = (rear + 1) % size
    count += 1

This code enqueues three elements into an empty circular queue of size 5.

Analysis Table

Step	Operation	front	rear	count	Queue State	Action
1	Initialize queue	0	0	0	[None, None, None, None, None]	Queue is empty
2	Enqueue 10	0	1	1	[10, None, None, None, None]	Added 10 at index 0
3	Enqueue 20	0	2	2	[10, 20, None, None, None]	Added 20 at index 1
4	Enqueue 30	0	3	3	[10, 20, 30, None, None]	Added 30 at index 2
5	Dequeue	1	3	2	[10, 20, 30, None, None]	Removed 10 from index 0
6	Enqueue 40	1	4	3	[10, 20, 30, 40, None]	Added 40 at index 3
7	Enqueue 50	1	0	4	[10, 20, 30, 40, 50]	Added 50 at index 4 (wrap around)
8	Enqueue 60	1	0	4	[10, 20, 30, 40, 50]	Queue full, cannot enqueue 60
9	Dequeue	2	0	3	[10, 20, 30, 40, 50]	Removed 20 from index 1
10	Enqueue 60	2	1	4	[60, 20, 30, 40, 50]	Added 60 at index 0 (wrap around)
11	Dequeue	3	1	3	[60, 20, 30, 40, 50]	Removed 30 from index 2
12	Dequeue	4	1	2	[60, 20, 30, 40, 50]	Removed 40 from index 3
13	Dequeue	0	1	1	[60, 20, 30, 40, 50]	Removed 50 from index 4 (wrap around)
14	Dequeue	1	1	0	[60, 20, 30, 40, 50]	Removed 60 from index 0
15	Dequeue	1	1	0	[60, 20, 30, 40, 50]	Queue empty, cannot dequeue
16	End	1	1	0	[60, 20, 30, 40, 50]	No more operations

💡 Queue is empty at step 15, no more dequeues possible

State 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	0	0	0	0	1	1	1	1	2	2	3	4	0	1	1
rear	0	1	2	3	3	4	0	0	0	1	1	1	1	1	1
count	0	1	2	3	2	3	4	4	3	4	3	2	1	0	0

Key Insights - 3 Insights

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

Because the queue is circular, the rear index uses modulo operation (rear = (rear + 1) % size) to wrap around and reuse empty slots at the start of the array, as shown in steps 7 and 10.

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

Count tracks the number of elements. When count equals size, the queue is full, so enqueue is rejected (step 8), even if the array has None values from previous dequeues, because those slots are logically occupied or waiting to be overwritten.

Why does the front index move forward after a dequeue?

After removing the element at front, front moves forward using modulo to point to the next element, as in step 5 and onwards, ensuring the queue correctly tracks the current front.

Visual Quiz - 3 Questions

Look at the execution table at step 7. What is the rear index value after enqueueing 50?

A 0

B 4

C 3

D 1

💡 Hint

Check the 'rear' column at step 7 in the execution_table.

At which step does the queue become full, preventing further enqueues?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look for the step where enqueue is rejected due to full queue in the 'Action' column.

According to variable_tracker, what is the count value after step 10?

A 3

B 2

C 4

D 1

💡 Hint

Refer to the 'count' row and 'After Step 10' column in variable_tracker.

Concept Snapshot

Circular Queue:
- Fixed size array with front and rear pointers
- rear and front wrap around using modulo
- Enqueue adds at rear if not full
- Dequeue removes from front if not empty
- Count tracks number of elements
- Efficient use of space by reusing slots

Full Transcript

A circular queue is a data structure that uses a fixed-size array and two pointers, front and rear, to manage elements. The rear pointer moves forward when adding elements, and the front pointer moves forward when removing elements. Both pointers wrap around to the start of the array when they reach the end, using modulo arithmetic. This wrapping allows the queue to reuse empty spaces created by dequeues, avoiding wasted space. The count variable keeps track of how many elements are currently in the queue, preventing overflows and underflows. Enqueue operations add elements at the rear if the queue is not full, while dequeue operations remove elements from the front if the queue is not empty. This structure is efficient for fixed-size buffering scenarios.

Practice

1. What is the main advantage of a circular queue compared to a regular linear queue?

easy

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

B. It efficiently reuses empty space by connecting the end to the start.

C. It automatically sorts elements while enqueuing.

D. It requires shifting elements after every dequeue operation.

Solution

1. Step 1: Understand the structure of a circular queue

   A circular queue connects the last position back to the first, forming a circle.

2. Step 2: Identify the advantage over a linear queue

   This connection allows the queue to reuse spaces freed by dequeued elements without shifting.

3. Final Answer:

   It efficiently reuses empty space by connecting the end to the start. -> Option B

4. Quick Check:

   Circular queue = space reuse [OK]

Hint: Circular queue wraps around to reuse space [OK]

Common Mistakes:

• Thinking it sorts elements automatically
• Believing it stores multiple data types
• Assuming it shifts elements after dequeue

2. Which of the following is the correct way to update the rear pointer in a circular queue after an enqueue operation?

easy

A. rear = (rear + 1) % size

B. rear = rear + 1

C. rear = rear - 1

D. rear = size - rear

Solution

1. Step 1: Recall how circular queue pointers move

   In a circular queue, pointers wrap around using modulo arithmetic to stay within bounds.

2. Step 2: Apply modulo to update rear pointer

   After enqueue, rear moves to (rear + 1) modulo the queue size to wrap if needed.

3. Final Answer:

   rear = (rear + 1) % size -> Option A

4. Quick Check:

   Rear update uses modulo [OK]

Hint: Use modulo (%) to wrap rear pointer [OK]

Common Mistakes:

• Incrementing rear without modulo
• Decrementing rear after enqueue
• Using subtraction instead of modulo

3. Consider a circular queue of size 5 with front = 3 and rear = 1. Which of the following statements is true about the queue state?

medium

A. The queue is empty.

B. The queue is full.

C. The queue has 3 elements.

D. The queue has 4 elements.

Solution

1. Step 1: Understand front and rear positions in circular queue

   Front at 3 and rear at 1 means rear has wrapped around past front.

2. Step 2: Calculate number of elements using formula

   Number of elements = (rear - front + size) % size = (1 - 3 + 5) % 5 = 3 % 5 = 3.

3. Final Answer:

   The queue has 3 elements. -> Option C

4. Quick Check:

   Elements count = 3 [OK]

Hint: Use (rear - front + size) % size to count elements [OK]

Common Mistakes:

• Confusing full and empty conditions
• Ignoring modulo in calculation
• Assuming rear < front means empty

4. Given this code snippet for dequeue in a circular queue, what is the error?

if front == -1:
    print("Queue is empty")
else:
    data = queue[front]
    if front == rear:
        front = rear = -1
    else:
        front = (front + 1) % size

medium

A. The code does not return or use the dequeued data.

B. The front pointer update should use rear instead of front.

C. The condition to check empty queue is incorrect.

D. The rear pointer should be incremented after dequeue.

Solution

1. Step 1: Analyze the dequeue operation steps

   The code checks if queue is empty, retrieves data, updates pointers correctly.

2. Step 2: Identify missing usage of dequeued data

   Though data is assigned, it is neither returned nor used, so the operation loses the dequeued value.

3. Final Answer:

   The code does not return or use the dequeued data. -> Option A

4. Quick Check:

   Dequeue must return data [OK]

Hint: Always return dequeued element [OK]

Common Mistakes:

• Not returning dequeued value
• Incorrect pointer updates
• Incrementing rear on dequeue

5. You have a circular queue of size 6. Initially, front = 0 and rear = 4. You perform two dequeue operations followed by three enqueue operations. What will be the final positions of front and rear?

hard

A. front = 1, rear = 2

B. front = 2, rear = 0

C. front = 0, rear = 5

D. front = 2, rear = 1

Solution

1. Step 1: Update front after two dequeues

   Each dequeue moves front by 1 modulo size: front = (0 + 2) % 6 = 2.

2. Step 2: Update rear after three enqueues

   Each enqueue moves rear by 1 modulo size: rear = (4 + 3) % 6 = 7 % 6 = 1.

3. Final Answer:

   front = 2, rear = 1 -> Option D

4. Quick Check:

   Front and rear updated with modulo [OK]

Hint: Add operations to pointers using modulo size [OK]

Common Mistakes:

• Not using modulo for pointer wrap-around
• Mixing front and rear updates
• Forgetting to update pointers after each operation