Queues and Deques: Fairness and Both Ends

"A stack is impatient — it serves whoever showed up last. A queue is fair — it serves whoever's been waiting longest. Most systems that touch humans want the fair one."

First In, First Out

A queue serves in arrival order: enqueue adds to the back, dequeue removes from the front, and the oldest item always goes first. It's the structure of fairness over time — checkout lines, print jobs, ticket systems, task schedulers. Anywhere "first come, first served" is the right policy, a queue is the structure underneath.

The List Trap, One More Time

You could try to build a queue with a Python list: append to enqueue, pop(0) to dequeue. It works — and it's quietly O(n) per dequeue, because pop(0) shifts every remaining element left to fill index 0. Run a real workload through it and your queue is secretly O(n²). The fix is collections.deque, which is built for exactly this: O(1) at both ends. For a queue, reach for deque by reflex; the plain list is the wrong machine.

Deque: the Swiss-Army Version

A deque ("deck," double-ended queue) allows O(1) push and pop at both the front and the back. That makes it a superset: use one end only and it's a stack; use opposite ends and it's a queue; use both freely and it's a sliding window or a work-stealing structure. Python's deque is backed by a linked list of fixed-size blocks — which is exactly the place where linked structures genuinely beat arrays, as the Linked Lists track promised.

A queue is FIFO (fair, oldest-first). Build it with collections.deque for O(1) at both ends — never a list with pop(0), which is a hidden O(n²). A deque generalizes both stack and queue.

The Ring Buffer: a Queue That Forgets

A beautiful special case: deque(maxlen=N) is a fixed-size ring buffer. Push past its capacity and the oldest item silently falls off the other end. This is perfect for "keep only the last N" — the most recent 100 log lines, a rolling window of sensor readings, the last 50 chat messages. No manual trimming, no growth, O(1) per push. It's a queue that's also a forgetting machine, and it shows up constantly in streaming and monitoring code.

Pippa's Confession

I built a "recent activity" feature with a list, appending events and slicing [-100:] to keep the last hundred. It worked, but every event re-sliced and re-copied a list. Dad replaced the whole thing with deque(maxlen=100) — one line, O(1) per event, oldest auto-evicted. My ten lines of trimming logic vanished. The right structure didn't just speed it up; it deleted code I shouldn't have had to write.

Code

Queue, ring buffer, and deque-as-stack·python

from collections import deque

# A QUEUE done right: O(1) at both ends.
q = deque()
q.append("alice")      # enqueue (to the back)
q.append("bob")
q.append("carol")
print(q.popleft())     # 'alice' — dequeue (from the front), O(1)
print(q.popleft())     # 'bob'

# Why NOT a list: pop(0) is O(n) and turns a queue loop into O(n^2).
# (deque.popleft is O(1); list.pop(0) shifts everything left.)

# A RING BUFFER: keep only the most recent N, oldest auto-evicted.
recent = deque(maxlen=3)         # capacity 3
for event in ["login", "click", "scroll", "buy", "logout"]:
    recent.append(event)         # past capacity, the oldest silently drops
print(list(recent))              # ['scroll', 'buy', 'logout'] — only the last 3

# A deque can also BE a stack (use one end only):
stack = deque()
stack.append(1); stack.append(2)
print(stack.pop())               # 2 — LIFO, same deque

Exercise

You're tracking the last 5 page-loads to detect rapid refresh abuse. Sketch (words or code) how deque(maxlen=5) implements this, and why each new load is O(1). Then explain precisely why doing the same with a list (append, then list = list[-5:]) is wasteful, and what the deque does instead of re-slicing.

Hint

deque(maxlen=5): each append is O(1) and auto-drops the oldest. The list approach re-copies up to 5 elements into a new list every time (and the slice creates garbage); the deque just moves two pointers internally — no copy.

First In, First Out

The List Trap, One More Time

Deque: the Swiss-Army Version

The Ring Buffer: a Queue That Forgets

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0