Circular Queue Implementation Using Array in DSA Go

Mental Model

A circular queue uses a fixed-size array where the end connects back to the start, so we reuse empty spaces efficiently.

Analogy: Imagine a round table with seats numbered in a circle. When you reach the last seat, you go back to the first seat to sit if it's empty.

Front and Rear pointers moving in a circle:

[0] -> [1] -> [2] -> [3] -> [4]
 ↑                       ↑
Front                   Rear

Empty slots wrap around after the last index.

Dry Run Walkthrough

Input: Create circular queue of size 5, enqueue 3 elements (10, 20, 30), dequeue 1 element, enqueue 2 elements (40, 50), then enqueue 1 more element (60) to test full condition.

Goal: Show how front and rear pointers move circularly and how the queue handles full and empty states.

Step 1: Enqueue 10 at rear

Queue: [10] -> [ ] -> [ ] -> [ ] -> [ ]
Front=0, Rear=0

Why: First element added, front and rear both point to index 0

Step 2: Enqueue 20 at rear

Queue: [10] -> [20] -> [ ] -> [ ] -> [ ]
Front=0, Rear=1

Why: Rear moves forward to index 1 to add new element

Step 3: Enqueue 30 at rear

Queue: [10] -> [20] -> [30] -> [ ] -> [ ]
Front=0, Rear=2

Why: Rear moves forward to index 2 to add new element

Step 4: Dequeue element at front (10)

Queue: [ ] -> [20] -> [30] -> [ ] -> [ ]
Front=1, Rear=2

Why: Front moves forward to index 1, removing first element

Step 5: Enqueue 40 at rear

Queue: [ ] -> [20] -> [30] -> [40] -> [ ]
Front=1, Rear=3

Why: Rear moves forward to index 3 to add new element

Step 6: Enqueue 50 at rear

Queue: [ ] -> [20] -> [30] -> [40] -> [50]
Front=1, Rear=4

Why: Rear moves forward to index 4 to add new element

Step 7: Enqueue 60 at rear (wrap around to index 0)

Queue: [60] -> [20] -> [30] -> [40] -> [50]
Front=1, Rear=0

Why: Rear wraps around to index 0 due to circular nature

Step 8: Attempt to enqueue 70 (queue full)

Queue full, cannot enqueue 70
Queue: [60] -> [20] -> [30] -> [40] -> [50]
Front=1, Rear=0

Why: Rear next position equals front, indicating full queue

Result:

Final queue state:
[60] -> [20] -> [30] -> [40] -> [50]
Front=1, Rear=0
Queue is full, cannot add more elements

Annotated Code

DSA Go

package main

import (
	"errors"
	"fmt"
)

type CircularQueue struct {
	data        []int
	front       int
	rear        int
	size        int
	capacity    int
}

func NewCircularQueue(capacity int) *CircularQueue {
	return &CircularQueue{
		data:     make([]int, capacity),
		front:    -1,
		rear:     -1,
		size:     0,
		capacity: capacity,
	}
}

func (q *CircularQueue) IsFull() bool {
	return q.size == q.capacity
}

func (q *CircularQueue) IsEmpty() bool {
	return q.size == 0
}

func (q *CircularQueue) Enqueue(value int) error {
	if q.IsFull() {
		return errors.New("Queue is full")
	}
	if q.IsEmpty() {
		q.front = 0
	}
	q.rear = (q.rear + 1) % q.capacity // move rear circularly
	q.data[q.rear] = value
	q.size++
	return nil
}

func (q *CircularQueue) Dequeue() (int, error) {
	if q.IsEmpty() {
		return 0, errors.New("Queue is empty")
	}
	value := q.data[q.front]
	q.front = (q.front + 1) % q.capacity // move front circularly
	q.size--
	if q.size == 0 {
		q.front = -1
		q.rear = -1
	}
	return value, nil
}

func (q *CircularQueue) String() string {
	if q.IsEmpty() {
		return "Queue is empty"
	}
	result := ""
	index := q.front
	for i := 0; i < q.size; i++ {
		result += fmt.Sprintf("%d", q.data[index])
		if i != q.size-1 {
			result += " -> "
		}
		index = (index + 1) % q.capacity
	}
	result += " -> null"
	return result
}

func main() {
	q := NewCircularQueue(5)
	_ = q.Enqueue(10) // step 1
	_ = q.Enqueue(20) // step 2
	_ = q.Enqueue(30) // step 3
	_, _ = q.Dequeue() // step 4
	_ = q.Enqueue(40) // step 5
	_ = q.Enqueue(50) // step 6
	err := q.Enqueue(60) // step 7
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println(q.String())
	err = q.Enqueue(70) // step 8
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println(q.String())
}

if q.IsFull() { return errors.New("Queue is full") }

Check if queue is full before adding new element

if q.IsEmpty() { q.front = 0 }

Initialize front pointer when first element is enqueued

q.rear = (q.rear + 1) % q.capacity

Move rear pointer circularly to next position

q.size++

Increase size after enqueue

if q.IsEmpty() { return 0, errors.New("Queue is empty") }

Check if queue is empty before dequeue

value := q.data[q.front]

Retrieve value at front pointer

q.front = (q.front + 1) % q.capacity

Move front pointer circularly to next position

q.size--

Decrease size after dequeue

if q.size == 0 { q.front = -1; q.rear = -1 }

Reset pointers when queue becomes empty

Output

Queue is full

60 -> 20 -> 30 -> 40 -> 50 -> null

Queue is full

60 -> 20 -> 30 -> 40 -> 50 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because pointers move in constant time without shifting elements

Space: O(n) where n is the capacity of the queue because we use a fixed-size array

vs Alternative: Compared to a normal queue using array where dequeue causes O(n) shifts, circular queue avoids shifting by wrapping pointers, making operations efficient

Edge Cases

Enqueue on full queue

Returns error "Queue is full" and does not add element

DSA Go

if q.IsFull() { return errors.New("Queue is full") }

Dequeue on empty queue

Returns error "Queue is empty" and no element is removed

DSA Go

if q.IsEmpty() { return 0, errors.New("Queue is empty") }

Enqueue first element

Front pointer is set to 0 to start queue

DSA Go

if q.IsEmpty() { q.front = 0 }

When to Use This Pattern

When you need a fixed-size queue that efficiently reuses space without shifting elements, use the circular queue pattern because it wraps pointers around the array.

Common Mistakes

Mistake: Not wrapping rear or front pointers using modulo, causing index out of range errors
Fix: Always update pointers with modulo operation: (pointer + 1) % capacity

Mistake: Not resetting front and rear to -1 when queue becomes empty, causing incorrect empty checks
Fix: Reset front and rear to -1 when size becomes zero after dequeue

Summary

Implements a queue using a fixed-size array where front and rear pointers wrap around to reuse space.

Use when you want a queue with fixed capacity that avoids costly shifting of elements.

The key insight is to move front and rear pointers circularly using modulo to efficiently manage 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