Circular Queue Implementation Using Array in DSA Python

Mental Model

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

Analogy: Imagine a round table where people sit in seats numbered 0 to n-1. When you reach the last seat, you go back to the first seat to fill it if empty.

Front -> [ ] -> [ ] -> [ ] -> [ ] -> [ ] ← Rear
Indexes: 0     1     2     3     4

Dry Run Walkthrough

Input: Create circular queue of size 5, enqueue 3 elements (10, 20, 30), dequeue 1 element, enqueue 2 elements (40, 50), enqueue 1 element (60) to test wrap-around

Goal: Show how elements wrap around in the array and how front and rear pointers move

Step 1: Enqueue 10

Front=0, Rear=0, Array=[10, _, _, _, _]

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

Step 2: Enqueue 20

Front=0, Rear=1, Array=[10, 20, _, _, _]

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

Step 3: Enqueue 30

Front=0, Rear=2, Array=[10, 20, 30, _, _]

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

Step 4: Dequeue one element (10)

Front=1, Rear=2, Array=[10, 20, 30, _, _]

Why: Front moves forward to index 1, element 10 is removed logically

Step 5: Enqueue 40

Front=1, Rear=3, Array=[10, 20, 30, 40, _]

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

Step 6: Enqueue 50

Front=1, Rear=4, Array=[10, 20, 30, 40, 50]

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

Step 7: Enqueue 60 (wrap-around)

Front=1, Rear=0, Array=[60, 20, 30, 40, 50]

Why: Rear wraps around to index 0 to reuse empty space

Result:

Front=1, Rear=0, Array=[60, 20, 30, 40, 50]
Queue elements in order: 20 -> 30 -> 40 -> 50 -> 60 -> null

Annotated Code

DSA Python

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = -1
        self.rear = -1

    def is_full(self):
        return (self.rear + 1) % self.size == self.front

    def is_empty(self):
        return self.front == -1

    def enqueue(self, value):
        if self.is_full():
            print("Queue is full")
            return
        if self.is_empty():
            self.front = 0
            self.rear = 0
            self.queue[self.rear] = value
            return
        self.rear = (self.rear + 1) % self.size  # move rear forward circularly
        self.queue[self.rear] = value

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        value = self.queue[self.front]
        if self.front == self.rear:  # only one element
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.size  # move front forward circularly
        return value

    def display(self):
        if self.is_empty():
            print("Queue is empty")
            return
        i = self.front
        elements = []
        while True:
            elements.append(str(self.queue[i]))
            if i == self.rear:
                break
            i = (i + 1) % self.size
        print(" -> ".join(elements) + " -> null")

# Driver code to run the dry run example
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.dequeue()
cq.enqueue(40)
cq.enqueue(50)
cq.enqueue(60)  # This should wrap around
cq.display()

if self.is_full():

check if queue is full to prevent overflow

if self.is_empty():

initialize front and rear when queue was empty

self.rear = (self.rear + 1) % self.size # move rear forward circularly

advance rear pointer circularly to next position

if self.is_empty():

check if queue is empty before dequeue

if self.front == self.rear: # only one element

reset front and rear when last element is dequeued

self.front = (self.front + 1) % self.size # move front forward circularly

advance front pointer circularly after dequeue

while True:

iterate from front to rear circularly to display elements

Output

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

Complexity Analysis

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

Space: O(n) for storing n elements in the fixed-size array

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

Edge Cases

Enqueue when queue is full

Prints 'Queue is full' and does not add element

DSA Python

if self.is_full():

Dequeue when queue is empty

Prints 'Queue is empty' and returns None

DSA Python

if self.is_empty():

Dequeue last element

Resets front and rear to -1 indicating empty queue

DSA Python

if self.front == self.rear:

When to Use This Pattern

When you need a fixed-size queue that efficiently reuses space without shifting elements, use the circular queue pattern to manage wrap-around indexing.

Common Mistakes

Mistake: Not wrapping rear or front pointers using modulo, causing index out of range errors
Fix: Always update pointers using (pointer + 1) % size to wrap around

Mistake: Not handling empty queue initialization properly, causing incorrect front/rear values
Fix: Set front and rear to 0 when first element is enqueued

Summary

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

Use when you want a queue with fixed capacity and efficient enqueue/dequeue without shifting elements.

The key is to move front and rear pointers circularly using modulo to manage wrap-around.

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

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

C. It automatically sorts the elements in the queue.

D. It eliminates the need for front and rear pointers.

Solution

1. Step 1: Understand linear queue limitation

   In a linear queue using an array, once rear reaches the end, no more elements can be added even if there is space at the front.

2. Step 2: Circular queue reuses space

   Circular queue connects the end of the array back to the front, allowing reuse of freed slots and efficient space usage.

3. Final Answer:

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

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space unlike linear queue [OK]

Common Mistakes:

• Thinking circular queue sorts elements
• Believing circular queue removes need for pointers
• Assuming it stores multiple data types automatically

2. Which of the following is the correct way to check if a circular queue is full when using an array of size max_size with front and rear pointers?

easy

A. if rear == max_size - 1

B. if rear == front

C. if front == -1

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

Solution

1. Step 1: Understand full condition in circular queue

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

2. Step 2: Use modulo for circular increment

   Using modulo operator, (rear + 1) % max_size gives the next position circularly.

3. Final Answer:

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

4. Quick Check:

   Full condition = (rear + 1) % max_size == front [OK]

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

Common Mistakes:

• Checking rear == front means full (actually empty)
• Using rear == max_size - 1 ignores circular wrap
• Checking front == -1 means empty, not full

3. Consider this circular queue code snippet with max_size = 5:

front = 0
rear = 3
queue = [10, 20, 30, 40, None]

# Enqueue operation
rear = (rear + 1) % 5
queue[rear] = 50

# Dequeue operation
front = (front + 1) % 5

print(queue)

What will be the printed output?

medium

A. [10, 20, 30, 40, 50] with front=1 and rear=4

B. [10, 20, 30, 40, None]

C. [10, 20, 30, 40, 50]

D. [10, 20, 30, 40, 50] with front=0 and rear=4

Solution

1. Step 1: Perform enqueue operation

   rear moves from 3 to (3+1)%5 = 4; queue[4] = 50; queue becomes [10, 20, 30, 40, 50]

2. Step 2: Perform dequeue operation

   front moves from 0 to (0+1)%5 = 1; front=1, rear=4

3. Final Answer:

   [10, 20, 30, 40, 50] with front=1 and rear=4 -> Option A

4. Quick Check:

   Enqueue rear=4, Dequeue front=1 [OK]

Hint: Track front and rear updates carefully after enqueue/dequeue [OK]

Common Mistakes:

• Ignoring front and rear pointer updates
• Assuming queue content changes on dequeue
• Confusing front and rear positions

4. The following code snippet for dequeue operation in a circular queue has a bug:

def dequeue(queue, front, rear, max_size):
    if front == -1:
        return None, front, rear  # Queue empty
    data = queue[front]
    if front == rear:
        front = rear = -1
    else:
        front = (front + 1) % max_size
    return data, front, rear

# Initial state
queue = [10, 20, 30, 40, 50]
front = 0
rear = 4

# Dequeue call
value, front, rear = dequeue(queue, front, rear, 5)
print(value, front, rear)

What is the bug in this code?

medium

A. The condition to check empty queue should be rear == -1, not front == -1.

B. The function does not update the queue after dequeue.

C. The function does not handle the case when queue is full.

D. The function incorrectly resets front and rear to -1 when queue becomes empty.

Solution

1. Step 1: Check queue update after dequeue

   The dequeue operation removes the element logically by moving front, but the queue array still holds the old value.

2. Step 2: Identify missing update

   To avoid stale data, the dequeued position should be cleared or updated (e.g., set to None) after dequeue.

3. Final Answer:

   The function does not update the queue after dequeue. -> Option B

4. Quick Check:

   Queue array update after dequeue [OK]

Hint: Dequeue should clear or update the dequeued slot [OK]

Common Mistakes:

• Checking only front for empty queue
• Not resetting pointers correctly after last dequeue
• Ignoring queue full condition in dequeue

5. You have a circular queue of size 6 (indices 0 to 5). Initially, front = 4 and rear = 2. The queue array is:
[70, 80, 90, None, 40, 50]

Which of the following sequences of operations will correctly enqueue 100 and dequeue two elements, updating front and rear properly?

hard

A. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6

B. Enqueue: rear = (rear + 2) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6

C. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6

D. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 2) % 6

Solution

1. Step 1: Enqueue operation

   rear = (2 + 1) % 6 = 3; queue[3] = 100; queue becomes [70, 80, 90, 100, 40, 50]

2. Step 2: Dequeue two elements

   front moves twice: front = (4 + 1) % 6 = 5, then front = (5 + 1) % 6 = 0

3. Final Answer:

   Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6 -> Option C

4. Quick Check:

   One enqueue + two dequeues update pointers correctly [OK]

Hint: Increment pointers modulo size for each enqueue/dequeue [OK]

Common Mistakes:

• Incrementing rear or front by more than 1 at once
• Not using modulo for circular wrap
• Dequeueing fewer or more times than asked