Two rules for taking things out
Many programs need a place to put things for later. Often it does not matter which thing comes out next, as long as there is a clear rule. Two rules cover most cases, and each has its own data structure.
- A stack hands back the item added most recently.
- A queue hands back the item that has been waiting longest.
That is the whole difference. Give both the same items and watch what comes out.
Stack
Add and remove at the same end. Last in, first out.
Came out
Queue
Add at one end, remove from the other. First in, first out.
Came out
Start. Two empty containers. Both will be given the same items in the same order, and asked to hand one back at the same moments.
Stack: last in, first out
Think of a stack of plates. You put a plate on top and you take a plate from the top. The plate at the bottom was the first one there and will be the last to leave.
A stack has two operations.
- Push: put an item on top.
- Pop: take the top item off.
Both touch only one end, so both are instant however tall the stack is.
stack = []
stack.append("A") # push
stack.append("B")
stack.pop() # "B": the most recentA plain list or array works as a stack, as long as you add and remove at the end.
Where stacks appear
- Undo. Each action is pushed. Undo pops the most recent one.
- The back button. Pages you visit are pushed. Back pops.
- Function calls. The call stack is one: the most recently called function is the first to return.
- Matching brackets. Push each opening bracket, and pop when a closing one arrives. If they do not match, the code is wrong.
- Depth-first search. See Graph Traversal.
Example
Checking brackets
Is ( [ ] { } ) balanced? Read left to right.
( push. [ push. ] matches the top [: pop. { push. } matches: pop. ) matches the remaining (: pop.
The stack is empty at the end, so it is balanced. In ( [ ) ], the ) arrives when the top is [. Mismatch.
Queue: first in, first out
A queue is a line at a shop. New people join at the back. The person at the front is served next. It is fair: nobody is overtaken.
- Enqueue: add an item at the back.
- Dequeue: take the item from the front.
from collections import deque
queue = deque()
queue.append("A") # enqueue
queue.append("B")
queue.popleft() # "A": the one that waited longestWhere queues appear
- Work waiting to be done. Print jobs, emails to send, tasks for a thread pool.
- Messages between systems. See Queues and Backpressure.
- Breadth-first search, which explores nearest things first.
- Anything where order of arrival should be respected.
Side by side
| Stack | Queue | |
|---|---|---|
| Rule | Last in, first out | First in, first out |
| Add | At the top | At the back |
| Remove | From the top | From the front |
| Picture | A pile of plates | A line of people |
| Good for | Undoing, backtracking, nesting | Fairness, processing in order |
Two relatives
- A deque (double-ended queue) allows adding and removing at both ends. It can act as either.
- A priority queue ignores arrival order and always hands back the most important item. It is usually built with a heap.
Key takeaways
- A stack returns the most recently added item: last in, first out.
- A queue returns the item that has waited longest: first in, first out.
- Both add and remove in one step, because they only ever touch the ends.
- Stacks suit undo, nested structures and going deep. Queues suit fairness and going wide.
- A plain array makes a good stack and a poor queue.