Why Circular Queue Implementation Using Array in DSA Go?

The Big Idea

What if your queue could magically reuse empty spots without moving anything?

The Scenario

Imagine you have a small parking lot with limited spaces arranged in a circle. Cars come in and leave, but if you only allow cars to park in a straight line without reusing empty spots at the start, the lot fills up quickly even if some spots are free.

The Problem

Using a simple queue with a fixed array means once the end is reached, you cannot add more cars even if there are empty spots at the beginning. This wastes space and causes delays because you have to move cars around or reset the queue manually.

The Solution

A circular queue treats the array as a circle, so when you reach the end, you wrap around to the beginning if there is space. This way, you use all available spots efficiently without shifting elements.

Before vs After

✗ Before

queue := make([]int, 5)
front, rear := 0, -1
// Enqueue
rear++
queue[rear] = 10
// Cannot enqueue after rear reaches end even if front > 0

✓ After

queue := make([]int, 5)
front, rear := 0, -1
// Enqueue with wrap-around
rear = (rear + 1) % len(queue)
queue[rear] = 10
// Can enqueue if space available anywhere

What It Enables

It enables efficient use of fixed-size storage by reusing freed spaces, making queues faster and more memory-friendly.

Real Life Example

Network routers use circular queues to manage packets efficiently, ensuring no space is wasted when packets arrive and leave continuously.

Key Takeaways

Circular queue reuses empty spaces by wrapping around.

Prevents wasted space in fixed-size arrays.

Improves performance in continuous enqueue-dequeue scenarios.

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