The queue
A queue is the stack's mirror: items enter at the back and leave from the front, like a checkout line. First in, first out: FIFO. The operations are enqueue (join the back) and dequeue (serve the front).
Queues run anything that must be handled in arrival order: print jobs, web server requests, messages between programs.
Here is the trap you already know. Using a list as a queue means append at the back (fine, O(1)) but pop(0) at the front, and lesson 2-3 showed pop(0) shifts every remaining item: O(n) per serve, O(n²) to drain the line.
The fix is collections.deque ("deck", double-ended queue). It is built from linked blocks (the doubly linked idea from lesson 4-3), so both ends are O(1): append, popleft, and also appendleft and pop.
A checkout line
Customers join at the back with append and are served from the front with popleft.
from collections import deque queue = deque() for customer in ["ana", "ben", "cai"]: queue.append(customer) print("serving:", queue.popleft()) queue.append("dee") print("serving:", queue.popleft()) print("serving:", queue.popleft()) print("still waiting:", list(queue))
Output
serving: ana
serving: ben
serving: cai
still waiting: ['dee']Service follows arrival order exactly. Ana came first and left first, and Dee joined partway through but waits behind everyone already in line.
That is the difference from the stack in lesson 5-1, where the newcomer would have been served immediately. Same two-operation interface, opposite end for removal, completely different behavior.
Every operation here is O(1), including the popleft that a plain list would have made O(n).
Prefer deque because list.pop(0) is O(n) from shifting while deque.popleft() is O(1).
Serving from a list's front closes the gap by shifting every remaining item, the mechanic from lesson 2-3. Draining 1,000,000 tasks that way costs roughly 10¹² shifts, since each of a million pops moves close to a million items.
A deque's linked-block design, the doubly linked idea from lesson 4-3, makes both ends cheap, so draining the same million tasks is O(n) overall. The difference is a program that finishes against one that appears to hang.
One thing a deque does not give you is priority. If tasks need to be served by importance rather than arrival order, neither a list nor a deque is the answer, and the structure for that is the heap in unit 8.
Simulating a printer
The job list mixes document names with the command PRINT, so the simulation enqueues one and dequeues on the other.
from collections import deque def simulate_printer(jobs): queue = deque() order = [] for job in jobs: if job == "PRINT": if queue: order.append(queue.popleft()) else: queue.append(job) return order jobs = ["essay", "photo", "PRINT", "slides", "PRINT", "PRINT"] print(simulate_printer(jobs))
Output
['essay', 'photo', 'slides']
The inner if queue: guard matters, because a PRINT arriving with nothing queued has to be skipped rather than crash on an empty deque.
Tracing the sequence shows FIFO surviving the interleaving. Essay and photo queue up, the first PRINT serves essay, slides joins behind photo, and the last two PRINT commands serve photo then slides.
Slides printed last despite arriving before two of the print commands, which is the whole point. Arrival order into the queue decides service order, and the timing of the requests to print does not reorder anything.
The back button needs a stack, and the printer needs a queue.
Back must return to the page visited most recently, which is LIFO, so the newest entry leaves first. Printing must respect who submitted first, which is FIFO, so the oldest entry leaves first.
The question that decides it every time is short: which item must come out next, the newest or the oldest? Newest means stack, oldest means queue, and no other property of the problem needs examining.
Applying that test to the earlier examples confirms them. Undo wants the newest edit, so stack. Bracket matching wants the most recent opener, so stack. A web server handling requests wants the oldest, so queue.