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

Time Complexity: Queue Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how the time taken by queue operations changes as the number of items grows.

How does adding or removing items affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following queue operations using an array.

class Queue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0

    def enqueue(self, item):
        if self.size == len(self.queue):
            raise Exception('Queue is full')
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % len(self.queue)
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise Exception('Queue is empty')
        item = self.queue[self.front]
        self.front = (self.front + 1) % len(self.queue)
        self.size -= 1
        return item
    

This code adds items to the rear and removes from the front using a circular array.

Identify Repeating Operations

Look at what repeats when we add or remove items.

• Primary operation: Assigning or reading one element in the array.
• How many times: Exactly once per enqueue or dequeue call.

How Execution Grows With Input

Each enqueue or dequeue does a fixed amount of work, no matter how many items are in the queue.

Input Size (n)	Approx. Operations
10	1 operation per enqueue or dequeue
100	1 operation per enqueue or dequeue
1000	1 operation per enqueue or dequeue

Pattern observation: The work stays the same per operation, regardless of queue size.

Final Time Complexity

Time Complexity: O(1)

This means each add or remove action takes the same small amount of time, no matter how many items are in the queue.

Common Mistake

[X] Wrong: "Removing an item from the front takes longer as the queue grows because we have to shift elements."

[OK] Correct: This implementation uses a circular array, so no shifting happens. The front index just moves forward, keeping removal time constant.

Interview Connect

Understanding this helps you explain why queues can be efficient and how to implement them well, a skill often valued in coding discussions.

Self-Check

"What if we used a simple array without circular indexing and shifted elements on dequeue? How would the time complexity change?"