Why queues follow FIFO principle in Data Structures Theory - Performance Analysis

Time Complexity: Why queues follow FIFO principle

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

Understanding Time Complexity

We want to understand how the order of operations in a queue affects its performance.

Specifically, why does a queue process items in the order they arrive?

Scenario Under Consideration

Analyze the time complexity of adding and removing items in a queue.

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

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

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

This code adds items to the back and removes from the front, following FIFO.

Identify Repeating Operations

Look at the main actions repeated when using the queue.

• Primary operation: Adding to the end and removing from the front of the list.
• How many times: Each enqueue or dequeue happens once per item processed.

How Execution Grows With Input

As more items enter the queue, each enqueue is quick, but dequeue can take longer because it shifts items.

Input Size (n)	Approx. Operations for dequeue
10	10 shifts
100	100 shifts
1000	1000 shifts

Removing from the front causes work proportional to the number of items left.

Final Time Complexity

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

This means adding is fast, but removing takes longer as the queue grows.

Common Mistake

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

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

Interview Connect

Understanding how queues work and their time costs helps you explain data structure choices clearly in interviews.

Self-Check

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