Data Structures — Queues (FIFO)

By the end of this lesson you can:

• Build a Queue class with enqueue, dequeue, peek, size.
• Understand why a plain list makes a slow queue — and why collections.deque is the right tool.
• Apply queues to print spoolers and task scheduling.
• Implement a simple BFS using a queue.

Stand at the back. People in front of you get served first. New people join the back. That's a queue. FIFO — first in, first out.

enqueue A    →  [A]               (joined the back)
enqueue B    →  [A, B]
enqueue C    →  [A, B, C]
dequeue      →  returns A;  [B, C]   (A leaves the front)
dequeue      →  returns B;  [C]
peek         →  returns C            (look at front)

The naïve list version (and why it's wrong)

# DON'T do this for production queues
class SlowQueue:
    def __init__(self):
        self._items = []
    def enqueue(self, item):
        self._items.append(item)         # O(1) — fast
    def dequeue(self):
        return self._items.pop(0)        # O(n) — SLOW! shifts everything left

# A million enqueues and dequeues = a trillion total operations

list.pop(0) has to shift every other element left by one slot. That makes the queue O(n) per dequeue — quadratic across many operations. For tiny queues it's fine; for production it's a hidden disaster.

The right answer · collections.deque

from collections import deque

q = deque()
q.append("A")               # enqueue — O(1)
q.append("B")
q.append("C")
print(q.popleft())          # dequeue — O(1)!  returns "A"
print(q[0])                 # peek — O(1)
print(len(q))               # size — O(1)

deque (double-ended queue) is a doubly-linked list under the hood. Both ends are O(1). It's the standard Python queue.

A wrapper class for clarity

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)

    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def peek(self):
        if not self._items:
            raise IndexError("peek into empty queue")
        return self._items[0]

    def __len__(self):
        return len(self._items)

    def is_empty(self):
        return len(self._items) == 0

    def __repr__(self):
        return f"Queue(front → {list(self._items)})"

Application 1 · Print spooler

Multiple users send print jobs to a shared printer. The printer can only process one at a time. Jobs are processed in order received — perfect FIFO.

printer_queue = Queue()
printer_queue.enqueue(("Aisyah",  "report.pdf",  3))
printer_queue.enqueue(("Wei Jie", "essay.docx",  10))
printer_queue.enqueue(("Priya",   "photo.png",   1))

while not printer_queue.is_empty():
    user, file, pages = printer_queue.dequeue()
    print(f"Printing {file} for {user} ({pages} pages)")

Application 2 · Task scheduler

A program processes tasks one at a time. New tasks join the back; the worker pulls from the front.

tasks = Queue()
def schedule(task):
    tasks.enqueue(task)

def worker():
    while not tasks.is_empty():
        task = tasks.dequeue()
        print(f"Doing: {task}")

Application 3 · Breadth-first search

BFS uses a queue to explore graph nodes level by level. Compare to depth-first (which uses a stack — explicit or via recursion).

def bfs(graph, start):
    """Visit every reachable node, breadth-first."""
    visited = set()
    q = deque([start])
    while q:
        node = q.popleft()
        if node in visited:
            continue
        visited.add(node)
        print(f"  visit {node}")
        for neighbour in graph[node]:
            q.append(neighbour)
    return visited


graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [], "E": ["F"], "F": [],
}
bfs(graph, "A")
# visit A
# visit B
# visit C
# visit D
# visit E
# visit F

BFS is the standard way to find shortest paths in unweighted graphs, "degrees of separation", level-by-level explorations.

Simulate a bus stop. Passengers arrive at random times; the bus picks up the front 5 every 10 minutes. Save as bus_stop.py:

# bus_stop.py — FIFO queue simulation

from collections import deque
import random


def simulate(minutes=60, arrival_rate=0.8, bus_capacity=5, bus_interval=10):
    """One passenger arrives with arrival_rate probability each minute.
       A bus comes every bus_interval minutes and takes the front N."""

    queue = deque()
    served = 0
    max_queue = 0

    for minute in range(minutes):
        # Possibly add a passenger
        if random.random() < arrival_rate:
            arrived_at = minute
            queue.append(arrived_at)

        max_queue = max(max_queue, len(queue))

        # Bus?
        if (minute + 1) % bus_interval == 0:
            taking = min(bus_capacity, len(queue))
            for _ in range(taking):
                queue.popleft()
            served += taking
            print(f"  min {minute + 1:>3}: bus takes {taking}; "
                  f"queue length now {len(queue)}")

    print(f"\n=== Summary ===")
    print(f"Total served:      {served}")
    print(f"Max queue length:  {max_queue}")
    print(f"Still waiting:     {len(queue)}")


random.seed(42)
simulate()

Sample output

  min  10: bus takes 5; queue length now 4
  min  20: bus takes 5; queue length now 3
  min  30: bus takes 5; queue length now 2
  min  40: bus takes 5; queue length now 5
  min  50: bus takes 5; queue length now 3
  min  60: bus takes 5; queue length now 2

=== Summary ===
Total served:      30
Max queue length:  9
Still waiting:     2

Read the diff

One deque models the entire queue. Per-minute simulation: arrival (sometimes); bus (every 10 mins) takes up to capacity. The data structure naturally enforces FIFO — first arrivals get on first.

A queue is FIFO — add at the back, remove from the front. Both operations O(1) when implemented with collections.deque. Don't use a Python list with pop(0) — that's O(n) and turns linear work into quadratic. Queues power schedulers, print spoolers, BFS, simulation. Whenever you see "process in the order arrived", reach for a queue.