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.
Code exercise · python
Run this checkout line. Customers join at the back with append and get served from the front with popleft, in exactly the order they arrived. Every operation here is O(1).
Quiz
You need a queue for 1,000,000 tasks. Why prefer `deque` over a plain list?
Code exercise · python
Your turn: simulate a printer. `jobs` mixes document names (enqueue them) with the command "PRINT" (dequeue one document into `order`, or do nothing if the queue is empty). Return the list of printed documents in print order.
Quiz
A browser's BACK button vs a printer's job line. Which structure serves each?