Queues, Deques & Up-Next
Queue three tracks in Tunebox and they play in the order you queued them: first in,
first out. That structure is a queue. The obvious Python version, a list you
pop(0) from, gets slower with every track waiting in line, so this lesson replaces
it with collections.deque, which adds and removes at either end in O(1).
First in, first out
A queue has two ends. Enqueue adds at the back and dequeue removes from the front, so whatever has waited longest is served next. That's FIFO, the opposite of a stack.
The answer is right. The problem is what pop(0) has to do to produce it.
Why list.pop(0) is O(n)
A list's items sit in consecutive slots, and slot 0 must always hold the first item. Remove it and every remaining item moves one slot to the left:
queue = ["A", "B", "C"]
first = queue.pop(0)
print(queue.index("C"))With 100,000 tracks waiting, one dequeue moves 99,999 items. Serving the whole queue that way moves about n²/2 items, around five billion here.
Coming from Java/JS: JS
array.shift()has the same O(n) cost, and so does Java'sArrayList.remove(0). Java's fix isArrayDequewithofferandpoll. Python's fix comes next.
collections.deque: O(1) at both ends
A deque (said "deck", short for double-ended queue) is built for exactly this. It stores items in a chain of fixed-size blocks, a linked list of small arrays, so neither end ever has to shift anything:
The four method names pair up. append and pop work on the right end, and
appendleft and popleft work on the left:
from collections import deque
q = deque(["B"])
q.append("C")
q.appendleft("A")
q.pop()
print(list(q))Mix the two ends up and you've built a stack by accident:
Tracks should play in the order they were queued, printing ['A', 'B', 'C']. It prints them backwards.
❓ Cross-question — "So why not use a deque for everything?" Fast ends come at the cost of a slow middle.
q[i]is O(n) near the middle of a deque, where a list is O(1), and a deque can't be sliced. Use a list when you index into it and a deque when you work at the ends.
An empty deque raises IndexError on popleft(), just as an empty list does on
pop(), which is why queue loops are written while q:.
The up-next loop
Queues are most useful when serving one item can add more items. Here, playing Intro adds a Chorus behind whatever is already waiting. Step through it and watch the order:
Chorus was added while Verse was already waiting, so Verse plays first. Nothing jumps the line in a queue.
Ring buffers
Tunebox shows your last three plays. A ring buffer stores them in a fixed-size
array. A start index marks the oldest item, a new item overwrites the oldest once
the array is full, and every index wraps around with % capacity. Nothing ever
shifts or grows:
In everyday Python you won't write that class, because deque(maxlen=n) behaves
the same way:
from collections import deque
recent = deque(maxlen=3)
for track in ["A", "B", "C", "D", "E"]:
recent.append(track)
print(list(recent))What it costs
| operation | list | deque |
|---|---|---|
add at the back: append |
O(1) amortized | O(1) |
remove from the front: pop(0) / popleft() |
O(n) | O(1) |
add at the front: insert(0, x) / appendleft |
O(n) | O(1) |
remove from the back: pop() |
O(1) | O(1) |
read q[0] or q[-1] |
O(1) | O(1) |
read q[i] in the middle |
O(1) | O(n) |
length: len(q) |
O(1) | O(1) |
Idioms & real-world patterns
q = deque(items)andwhile q: item = q.popleft()is the queue loop you'll write most often.deque(maxlen=n)keeps the last n of anything: recent plays, log lines, a moving window.q.rotate(k)moves k items from the back to the front, and a negative k goes the other way. It's a one-line way to take turns.- For threads, use
queue.Queue, which adds locking around the same idea. Async code usesasyncio.Queue. - Where queues live: print spoolers, web-server request backlogs, job queues such as SQS and Celery, network packet buffers, and breadth-first search.
⚡ Advanced — the monotonic deque: sliding-window maximum
Tunebox's volume normaliser needs the loudest level in every window of k
consecutive tracks. Rescanning each window costs O(n·k). Instead, keep a deque of
indices whose levels decrease from front to back:
- a new level removes every smaller-or-equal level from the back, because those can never be the loudest while the new one is still in the window;
- an index that has slid out of the window is dropped from the front;
- after both steps, the front is always the loudest level in the current window.
Each index enters the deque once and leaves at most once, so this is O(n) whatever
k is. It's the queue version of the monotonic stack from the last lesson, and the
extra front end is what lets old items expire.
⚡ Advanced — a preview: queues drive breadth-first search
"Fans of this track also like..." is a graph. Finding everything within a few hops of a track means exploring the nearest tracks first, and a queue guarantees that: everything one hop away is served before anything two hops away. Section 5 builds this properly. Here's the basic loop:
Swap popleft() for pop() and the same loop explores depth-first, the stack
version.
🎯 Your turn
Build up_next(queue, ops), Tunebox's up-next queue. Start from queue (front
first) and replay each op:
["add", title]enqueuestitleat the back.["next", title]is "play next": it putstitleat the front.["play"]dequeues the front track, and does nothing if the queue is empty.
Return what's still waiting, front first:
up_next(["A", "B"], [["add", "C"], ["play"]])→["B", "C"]up_next(["A", "B"], [["next", "X"], ["add", "Z"]])→["X", "A", "B", "Z"]
Hint: start with q = deque(queue), use append, appendleft and popleft, and
finish with return list(q).
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅