Circular queue in Data Structures Theory - Time & Space Complexity

Time Complexity: Circular queue

O(1)

Understanding Time Complexity

Analyzing time complexity helps us understand how fast operations run in a circular queue as it grows.

We want to know how the time to add or remove items changes when the queue size changes.

Scenario Under Consideration

Analyze the time complexity of the enqueue and dequeue operations in a circular queue.

class CircularQueue:
    def __init__(self, size):
        self.queue = [None] * (size + 1)
        self.head = 0
        self.tail = 0
        self.size = size + 1

    def enqueue(self, item):
        if (self.tail + 1) % self.size == self.head:
            return False  # Queue is full
        self.queue[self.tail] = item
        self.tail = (self.tail + 1) % self.size
        return True

    def dequeue(self):
        if self.head == self.tail:
            return None  # Queue is empty
        item = self.queue[self.head]
        self.head = (self.head + 1) % self.size
        return item
    

This code adds (enqueue) and removes (dequeue) items in a circular queue using fixed-size storage.

Identify Repeating Operations

Look for loops or repeated steps inside enqueue and dequeue.

• Primary operation: Single-step index update and assignment.
• 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
100	5-6 steps
1000	5-6 steps

Pattern observation: The number of steps stays 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 the queue size.

Common Mistake

[X] Wrong: "Enqueue or dequeue takes longer as the queue grows because it has to move many items."

[OK] Correct: Circular queue uses fixed positions and index updates, so it never shifts items and always works in constant time.

Interview Connect

Understanding constant time operations in circular queues shows you know how to efficiently manage fixed-size buffers, a useful skill in many real-world systems.

Self-Check

"What if we changed the circular queue to a dynamic array that resizes when full? How would the time complexity of enqueue change then?"