Stacks and queues
Some data only needs to come back out in a fixed order. A stack is a pile: the last thing you put on is the first thing you take off. A queue is a line: the first thing in is the first thing out. Step through seven lines of Python and watch letter blocks pile up and leave a stack, join and leave a queue, and see why Python uses a list for one and a deque for the other.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01You push "red", then "green", then "blue" onto an empty stack. What does one pop give back?
A stack is last in, first out. "blue" went on last, so it is on top and comes off first.
02Print jobs "a", "b" and "c" are sent in that order to a printer queue. Which prints first?
A queue is first in, first out: the job that joined first leaves the front first.
03In Python, which pair of calls uses a list as a stack?
append() adds at the end and pop() removes from the end, so the end of the list is the top of the stack. Both are fast.
04Why does Python's documentation suggest collections.deque instead of a list for a queue?
A list keeps its items packed from the start, so removing the first one shifts all the rest (O(n)). A deque is built to add and remove at both ends in about the same short time (O(1)).
05Which of these is a stack at work?
Undo reverses the latest change first: last in, first out. The other three take the oldest item first, which is a queue.
Glossary
- Stack
- A collection where you add and remove items only at one end, the top: last in, first out (LIFO).
- Push and pop
- Push adds an item to the top of a stack; pop removes the top item and hands it back. In Python: list.append() and list.pop().
- Queue
- A collection where items join at the back and leave from the front: first in, first out (FIFO).
- Enqueue and dequeue
- Enqueue adds an item at the back of a queue; dequeue removes the item at the front. With a deque: append() and popleft().
- deque
- Python's double-ended queue, from the collections module. Adding or removing at either end is fast.
- Call stack
- The stack Python keeps of the functions currently running: a call pushes a frame, a return pops it.
- O(n) and O(1)
- Ways of saying how work grows: O(n) grows with the number of items n; O(1) stays about the same however many items there are.
Notes and sources
- The drawing keeps each queue item in its own slot. A Python deque really works like that: it is a chain of fixed-size blocks with a moving front, so popleft() never shifts the other items. A list is one packed row, which is why list.pop(0) has to shift them.
- To look at the top of a stack without removing it, read stack[-1]; for the front of a deque, read q[0]. Popping an empty list or deque raises IndexError.
- When a Python error is printed, the "Traceback (most recent call last)" lines are the call stack at that moment, oldest call first.
- O(n) ("order n") means the work grows in step with the number of items n; O(1) means it stays about the same however many items there are.
- For queues shared between threads, Python also has queue.Queue, a first-in, first-out queue that handles the locking for you.
- Python tutorial: Using lists as stacks
- Python tutorial: Using lists as queues
- Python library: collections.deque
- Python wiki: Time complexity of list and deque operations
- Python library: inspect, the interpreter stack
- Python library: queue, a synchronized queue class
- Sedgewick and Wayne, Algorithms 4th ed.: Bags, queues and stacks
- Sedgewick and Wayne, Algorithms 4th ed.: Undirected graphs (breadth-first search)
Quiz Unlocks after the last step.