Circular Queue Implementation Using Array in DSA Python - Time & Space Complexity

Time Complexity: Circular Queue Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how fast operations run in a circular queue using an array.

Specifically, how the time to add or remove items changes as the queue grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

    def enqueue(self, value):
        if (self.rear + 1) % self.size == self.front:
            return "Queue is full"
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = value

    def dequeue(self):
        if self.front == -1:
            return "Queue is empty"
        data = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        return data

This code adds (enqueue) and removes (dequeue) items in a circular queue using an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single-step index update and assignment in enqueue and dequeue.
• How many times: Each enqueue or dequeue runs once per call, no loops inside.

How Execution Grows With Input

Each enqueue or dequeue does a fixed number of steps regardless of queue size.

Input Size (n)	Approx. Operations
10	5-6 steps per operation
100	5-6 steps per operation
1000	5-6 steps per operation

Pattern observation: The number of steps stays about the same no matter how big the queue is.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes the same short time no matter how many items are in the queue.

Common Mistake

[X] Wrong: "Because the queue uses an array, enqueue or dequeue must check many elements, so it takes longer as the queue grows."

[OK] Correct: The circular queue uses index math to jump directly to the right spot, so it does not scan or loop through elements.

Interview Connect

Understanding constant time operations in data structures like circular queues shows you can design efficient systems that handle data smoothly.

Self-Check

"What if we changed the circular queue to a normal queue using a list that shifts elements on dequeue? How would the time complexity change?"