Queue Concept and FIFO Principle in DSA Python - Time & Space Complexity

Time Complexity: Queue Concept and FIFO Principle

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

Understanding Time Complexity

We want to understand how long it takes to add or remove items in a queue.

How does the time change when the queue gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 adds items to the end and removes items from the front of a list to act like a queue.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding to the end (append) and removing from the front (pop at index 0) of the list.
• How many times: Each enqueue or dequeue is done once per operation, but dequeue shifts all remaining items.

How Execution Grows With Input

Adding an item takes about the same time no matter how big the queue is.

Removing an item 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: Removing from front grows linearly with queue size; adding to end stays constant.

Final Time Complexity

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

This means adding is fast and steady, but removing gets slower as the queue grows.

Common Mistake

[X] Wrong: "Both adding and removing items in a queue take the same fast time."

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

Interview Connect

Understanding how queue operations scale helps you choose the right data structure for fast performance.

Self-Check

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