Circular Queue Implementation Using Array in DSA Go - Execution Trace

Concept Flow - Circular Queue Implementation Using Array

Initialize queue with fixed size

↓

Enqueue operation

↓

Check if queue is full?

Yes→Reject enqueue

No↓

Add element at rear

↓

Update rear pointer (wrap if needed)

↓

Increment count

↓

Dequeue operation

↓

Check if queue is empty?

Yes→Reject dequeue

No↓

Remove element at front

↓

Update front pointer (wrap if needed)

↓

Decrement count

↓

Queue ready for next operation

This flow shows how elements are added and removed in a circular queue using an array, with pointers wrapping around when reaching the array end.

Execution Sample

DSA Go

queue := NewCircularQueue(3)
queue.Enqueue(10)
queue.Enqueue(20)
queue.Dequeue()
queue.Enqueue(30)
queue.Enqueue(40)

This code creates a circular queue of size 3, adds two elements, removes one, then adds two more, showing wrap-around behavior.

Execution Table

Step	Operation	Front	Rear	Count	Queue Array State	Visual State
1	Initialize queue size=3	0	-1	0	[_, _, _]	Empty queue
2	Enqueue 10	0	0	1	[10, _, _]	10 added at index 0
3	Enqueue 20	0	1	2	[10, 20, _]	20 added at index 1
4	Dequeue	1	1	1	[10, 20, _]	10 removed from index 0, front moves to 1
5	Enqueue 30	1	2	2	[10, 20, 30]	30 added at index 2
6	Enqueue 40	1	0	3	[40, 20, 30]	40 added at index 0 (wrap-around)
7	Attempt Enqueue 50	1	0	3	[40, 20, 30]	Queue full, enqueue rejected

💡 Step 7 stops enqueue because queue is full (count == size)

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
Front	0	0	0	1	1	1	1
Rear	-1	0	1	1	2	0	0
Count	0	1	2	1	2	3	3
Queue Array	[_, _, _]	[10, _, _]	[10, 20, _]	[10, 20, _]	[10, 20, 30]	[40, 20, 30]	[40, 20, 30]

Key Moments - 3 Insights

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

Because the queue is circular, when rear reaches the last index (2), it wraps to 0 to use free space at the start, as shown in Step 6 in execution_table.

Why can't we enqueue when count equals the queue size?

Count tracks how many elements are in the queue. When count equals size (3), the queue is full, so enqueue is rejected as in Step 7.

Why does front move forward after dequeue but the old value remains in the array?

Dequeue moves front pointer forward to logically remove the element. The old value stays in the array but is ignored. This is shown in Step 4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6. What is the rear pointer value after enqueueing 40?

A 2

B 1

C 0

D -1

💡 Hint

Check the 'Rear' column at Step 6 in execution_table.

At which step does the queue become full?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at the 'Count' and 'Queue Array State' columns in execution_table.

If we dequeue one more time after Step 6, what will be the front pointer value?

A 2

B 1

C 0

D 3

💡 Hint

Refer to how front pointer moves after dequeue in Step 4.

Concept Snapshot

Circular Queue using array:
- Fixed size array with front, rear pointers
- Enqueue adds at rear, rear moves forward (wraps to 0 if end reached)
- Dequeue removes from front, front moves forward (wraps similarly)
- Count tracks number of elements
- Queue full when count == size, empty when count == 0

Full Transcript

This visual trace shows how a circular queue works using an array. We start with an empty queue of size 3. Enqueue adds elements at the rear pointer, which moves forward and wraps to the start when reaching the array end. Dequeue removes elements from the front pointer, which also moves forward and wraps. The count variable tracks how many elements are in the queue. When count equals the size, the queue is full and no more enqueues are allowed. The array may still hold old values after dequeue, but they are ignored. This wrap-around behavior efficiently uses the array space.

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

C. It automatically sorts the elements in the queue.

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

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 dequeued elements.

3. Final Answer:

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

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space freed by dequeues [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 way to check if a circular queue is full when using an array of size n with front and rear indices?

easy

A. if front == -1

B. if rear == front

C. if rear == n - 1

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

Solution

1. Step 1: Understand full condition in circular queue

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

2. Step 2: Apply modulo for circular increment

   Using modulo n ensures wrap-around, so (rear + 1) % n == front means full.

3. Final Answer:

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

4. Quick Check:

   Full condition uses modulo wrap [OK]

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

Common Mistakes:

• Checking rear == front means empty, not full
• Using rear == n - 1 ignores circular wrap
• Confusing front == -1 as full condition

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 = 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 (removes 10)
   enqueue(40): rear=3
   enqueue(50): rear=4
   enqueue(60): rear=(4+1)%5=0 (wraps around)

2. Step 2: Final front and rear values

   front = 1, rear = 0 after last enqueue.

3. Final Answer:

   front = 1, rear = 0 -> Option A

4. Quick Check:

   Wrap-around rear = 0, front moved after dequeue [OK]

Hint: Track front/rear changes step-by-step with modulo [OK]

Common Mistakes:

• Not wrapping rear index after reaching end
• Forgetting to update front after dequeue
• Assuming front stays at -1 after first enqueue

4. Given the following Go code snippet for a circular queue, what is the bug that causes incorrect enqueue operation?

func enqueue(q []int, front *int, rear *int, n int, value int) {
    if (*rear+1)%n == *front {
        fmt.Println("Queue is full")
        return
    }
    if *front == -1 {
        *front = 0
    }
    *rear = (*rear + 1) % n
    q[*rear] = value
}

medium

A. The check for full queue is incorrect; it should be rear == front.

B. The queue slice q is passed by value, so changes to q are not saved.

C. The front pointer is not updated when queue is empty.

D. The rear index is incremented before checking if queue is full.

Solution

1. Step 1: Check handling of empty queue

   The code updates front to 0 only if front == -1, handling the initial empty state correctly.

2. Step 2: Issue after full dequeues

   After dequeuing all elements, dequeue updates front = (front + 1) % n, making (*rear + 1) % n == *front true, falsely detecting full. Enqueue fails to update/reset front for subsequent empty states.

3. Final Answer:

   The front pointer is not updated when queue is empty. -> Option C

4. Quick Check:

   Handle non-initial empty by resetting front [OK]

Hint: Reset front when queue empty after dequeues [OK]

Common Mistakes:

• Confusing full condition with rear == front
• Overlooking empty queue handling after dequeues
• Thinking slice passing causes the issue

5. You have a circular queue implemented using an array of size 6. Initially, front = 4 and rear = 2. Which of the following sequences of operations will cause the queue to become full?

hard

A. dequeue, enqueue, enqueue, enqueue

B. enqueue, dequeue, enqueue, dequeue

C. dequeue, dequeue, enqueue, enqueue

D. dequeue, enqueue, dequeue

Solution

1. Step 1: Understand initial state and full condition

   Array size n=6, front=4, rear=2 (5 elements occupied, 1 free). Full: (rear + 1) % 6 == front.

2. Step 2: Simulate each option

   Only D causes final full state:
   dequeue: front=5, rear=2 (4 elem)
   enqueue: rear=3 (5 elem)
   enqueue: rear=4 (6 elem, now full since (4+1)%6=5==front)
   enqueue: full detected, no change. Final: front=5, rear=4 full.
   Others end not full.

3. Final Answer:

   dequeue, enqueue, enqueue, enqueue -> Option A

4. Quick Check:

   Simulate steps to check final full condition [OK]

Hint: Simulate front/rear moves to check full condition [OK]

Common Mistakes:

• Assuming enqueue always fills queue immediately
• Ignoring circular wrap in index calculations
• Not updating front on dequeue