Circular Queue Implementation Using Array in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a circular queue?

A circular queue is a type of queue where the last position is connected back to the first position to make a circle. It helps use space efficiently by reusing empty spots after dequeue operations.

beginner

How do you check if a circular queue is full?

The queue is full when the next position of rear is equal to front. In formula: (rear + 1) % size == front.

beginner

What happens when you enqueue in a circular queue?

You add the new element at the rear index, then move rear to the next position using (rear + 1) % size to wrap around if needed.

beginner

How do you dequeue from a circular queue?

You remove the element at the front index, then move front to the next position using (front + 1) % size to wrap around if needed.

beginner

Why use a circular queue instead of a normal queue with an array?

A normal queue wastes space after some dequeues because front moves forward. Circular queue reuses empty spaces by wrapping around, making better use of the array.

What condition shows a circular queue is empty?

A front == (rear + 1) % size

B front == 0

C rear == size - 1

D front == rear

The queue is empty when front and rear point to the same position.

If rear = 4, size = 5, what is the next rear position after enqueue?

A 0

B 5

C 4

D 1

Next rear is (4 + 1) % 5 = 0, wrapping around to start.

What is the main advantage of a circular queue over a linear queue?

A Reuses empty spaces after dequeue

B Uses linked list

C No need for front pointer

D Faster enqueue

Circular queue reuses spaces freed by dequeue, unlike linear queue.

Which operation moves the front pointer in a circular queue?

A Peek

B Enqueue

C Dequeue

D IsFull check

Dequeue removes element at front and moves front pointer.

What does (rear + 1) % size == front mean in a circular queue?

A Queue is empty

B Queue is full

C Queue has one element

D Queue is half full

This condition means the queue is full and no more elements can be added.

Explain how enqueue and dequeue operations work in a circular queue using an array.

Think about how the pointers move in a circle.

Describe why a circular queue is more space efficient than a normal linear queue implemented with an array.

Imagine a line of chairs where people leave and new people come in.

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