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.