Queue operations (enqueue, dequeue) in Data Structures Theory - Time & Space Complexity

Time Complexity: Queue operations (enqueue, dequeue)

O(n) for dequeue, O(1) for enqueue

Understanding Time Complexity

When working with queues, it is important to know how the time to add or remove items changes as the queue grows.

We want to understand how fast enqueue and dequeue operations run as the number of items increases.

Scenario Under Consideration

Analyze the time complexity of the following queue operations.

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)  # Add to end

    def dequeue(self):
        return self.items.pop(0)  # Remove from front

This code shows a simple queue using a list where items are added at the end and removed from the front.

Identify Repeating Operations

Look at the main actions that repeat when the queue changes.

• Primary operation: Adding an item at the end (enqueue) and removing an item from the front (dequeue).
• How many times: Each operation happens once per enqueue or dequeue call, but dequeue involves shifting all remaining items.

How Execution Grows With Input

Adding an item at the end stays quick no matter the queue size. Removing from the front takes longer as the queue grows because all other items move forward.

Input Size (n)	Approx. Operations for dequeue
10	9 moves
100	99 moves
1000	999 moves

Pattern observation: Dequeue operation time grows linearly with the number of items, while enqueue stays constant.

Final Time Complexity

Time Complexity: O(n) for dequeue, O(1) for enqueue

This means adding items is fast and steady, but removing items takes longer as the queue gets bigger.

Common Mistake

[X] Wrong: "Both enqueue and dequeue always take the same constant time."

[OK] Correct: Removing from the front of a list requires shifting all other items, so it takes longer as the queue grows.

Interview Connect

Understanding how queue operations scale helps you explain data structure choices clearly and shows you know what happens behind the scenes.

Self-Check

"What if we used a linked list instead of a list for the queue? How would the time complexity of dequeue change?"