Queues and FIFO

The Line That Everyone Respects

Imagine a busy ticket counter at a train station. Passengers arrive and join the back of the line. The ticket agent serves the person at the front first. No matter how long you have been waiting, the rule is clear: first come, first served. Nobody cuts in line (or at least, nobody is supposed to).

This is a queue. The first person to arrive is the first person to leave — First In, First Out, or FIFO.

You interact with queues constantly in real life and in software. A print spooler queues your documents. An operating system queues tasks waiting for CPU time. A web server queues incoming requests when traffic spikes. Even the packets traveling across the internet wait in queues inside routers.

The FIFO Principle — Formal Definition

Queue: An ordered collection of elements where insertions happen at one end (the rear) and removals happen at the other end (the front). The first element inserted is the first element removed.

Contrast this with a stack. A stack adds and removes from the same end. A queue adds at the back and removes from the front. Two different ends, two completely different behaviors.

Why NOT a Regular Python List?

You might think: "I can just use a Python list and call list.append() to add and list.pop(0) to remove from the front." That works — but it is slow.

Removing from the front of a Python list (pop(0)) is O(n) because every remaining element must shift one position to the left to fill the gap. For a queue with a million items, that is a million shifts every single dequeue operation.

Python's collections.deque (double-ended queue) is built for exactly this purpose. It uses a doubly linked list internally, making both append() (add to back) and popleft() (remove from front) run in O(1).

Always use collections.deque for queue operations in Python. The performance difference is enormous at scale.

Implementation: Queue Class

from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()        # Internal deque handles all the heavy lifting

    def enqueue(self, item):
        self._data.append(item)     # Add to the BACK of the queue — O(1)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        return self._data.popleft() # Remove from the FRONT of the queue — O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek at empty queue")
        return self._data[0]        # Look at the front without removing — O(1)

    def size(self):
        return len(self._data)      # Number of elements currently in the queue

    def is_empty(self):
        return len(self._data) == 0 # True if the queue has no elements

Seeing the Queue in Action

q = Queue()

# Customers arriving at a ticket counter
q.enqueue("Alice")
q.enqueue("Bob")
q.enqueue("Charlie")

print("Queue size:", q.size())     # 3
print("Next to be served:", q.peek())  # Alice — she arrived first

print(q.dequeue(), "served")      # Alice served  → queue: [Bob, Charlie]
print(q.dequeue(), "served")      # Bob served    → queue: [Charlie]

q.enqueue("Diana")                # Diana joins the back
print("Queue size:", q.size())    # 2

while not q.is_empty():
    print(q.dequeue(), "served")

Output:

Queue size: 3
Next to be served: Alice
Alice served
Bob served
Queue size: 2
Charlie served
Diana served

Alice arrived first, Alice leaves first. Diana arrived last, Diana leaves last. Perfect FIFO order.

Core Operations: Big O Summary

All core operations run in constant time. This is what makes queues so efficient.

Queues Power BFS — A Preview

One of the most important algorithms in computer science — Breadth-First Search (BFS) — relies entirely on a queue. BFS explores a graph or tree level by level, always visiting the closest nodes before the farther ones.

The reason is simple: you add newly discovered nodes to the back of the queue and process nodes from the front. Nodes discovered earlier get processed earlier — FIFO ensures you always explore layer by layer.

We will cover BFS in full detail in the graph traversal lesson, but remember this connection: BFS = queue. DFS = stack.

Real-World Applications

Queue vs Stack: The Core Difference

Bonus: Using deque Directly

If you do not need the class wrapper, deque alone is perfectly fine for queue operations:

from collections import deque

q = deque()
q.append("Task 1")       # enqueue
q.append("Task 2")
q.append("Task 3")

while q:
    print("Processing:", q.popleft())  # dequeue — FIFO order

Output:

Processing: Task 1
Processing: Task 2
Processing: Task 3

Clean, readable, and O(1) for every operation.

Key Takeaway

A queue enforces fairness through order: whoever arrives first gets served first. This FIFO discipline makes queues the natural choice for any problem involving waiting, scheduling, or level-by-level exploration. In Python, always reach for collections.deque rather than a list when you need true queue behavior — the performance difference is not theoretical; it is dramatic at scale.