Some structures are defined by the rule for taking things out rather than how they're stored.
A stack is like a pile of plates: you add to the top (push) and take from the top (pop), so the last thing in is the first thing out (LIFO). Undo works like this: each action is pushed, and undo pops the newest. So does the call stack, which tracks which function called which.
stack = []
stack.append("type A")
stack.append("type B")
stack.append("bold")
print(stack.pop())
print(stack)bold ['type A', 'type B']
A queue is like a line at a shop: you join at the back (enqueue) and leave from the front (dequeue), so the first in is the first out (FIFO). Print jobs, messages waiting to be sent and turns in a game all queue up this way.
A Python list makes a good stack, since adding and removing at the end are quick. It makes a poor queue, because removing from the front shifts everything. Use collections.deque instead, which is quick at both ends.
from collections import deque
line = deque()
line.append("Ana")
line.append("Ben")
line.append("Cy")
print(line.popleft())Ana
The undo button should undo your most recent change. Which fits?
| Stack (LIFO) | push to the top, pop from the top. Python: list append() / pop(). |
|---|---|
| Queue (FIFO) | Join at the back, leave from the front. Python: deque append() / popleft(). |
| Peek | Look at the next item without removing it: stack[-1], queue[0]. |
| Call stack | The stack of functions waiting for the one they called. |