Data Structures & Algorithms
Stacks and Queues
A stack only allows adding and removing items from one end, so the last item added is always the first one removed, a discipline called LIFO. A queue only allows adding at one end and removing from the other, so the first item added is always the first one removed, called FIFO. Both are usually implemented on top of an array or a linked list; the discipline of where you're allowed to add and remove, not the underlying storage, is what actually defines them.
Why it matters
- The call stack, which every function call relies on, is a literal stack
- Understanding push and pop as a stack is what makes recursion, and errors from runaway recursion, make sense.
- Undo and redo, browser back buttons, and matching-brackets logic are naturally stack problems
- Each of these is most-recent-thing-first, which is exactly what a stack models directly.
- Task scheduling, breadth-first traversal, and request or print queues are naturally queue problems
- Each of these is whoever-got-here-first-goes-first, which a queue models directly and a stack would get backwards.
- Picking the wrong one produces a silently wrong result, not a crash
- Using a stack where arrival order actually matters does not raise an error, it just processes things in the wrong order, which can be far harder to notice than a crash.
Stack: last in, first out
A stack supports push, adding to the top, and pop, removing from the top, so the most recently added item is always the first one to come back out. Python's list works as a stack directly: append is push, and pop with no argument removes and returns the last element, both O(1), since neither requires shifting any other elements. A classic use is checking that brackets in an expression are balanced: push every opening bracket, and when a closing bracket appears, it must match whatever is currently on top of the stack.
def is_balanced(expr):
stack = []
pairs = {')': '(', ']': '['}
for ch in expr:
if ch in '([':
stack.append(ch)
elif ch in ')]':
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(is_balanced('([])')) # TrueQueue: first in, first out
A queue supports enqueue, adding at the back, and dequeue, removing from the front, so items come out in the same order they went in. A plain Python list is a poor queue: removing from the front is O(n), because every remaining element has to shift over by one to fill the gap. collections.deque exists for exactly this reason - it supports O(1) additions and removals at both ends, which makes it the right structure for a queue in Python rather than a plain list.
from collections import deque
line = deque()
line.append('ticket 1')
line.append('ticket 2')
print(line.popleft()) # ticket 1 - first in, first out
print(line.popleft()) # ticket 2Mistakes people make here
- Using a plain Python list as a queue, removing from the front
- Removing from the front of a list is O(n) per call, because every remaining element shifts left by one position - a queue implemented this way degrades badly as it grows. collections.deque avoids this entirely.
- Mixing up which end is which
- It is easy to write logic that pops from the wrong end of a stack or dequeues from the wrong end of a queue, especially once the code is a few lines away from the actual push and pop calls - the bug produces the wrong order, not an error.
- Popping from an empty stack or queue without checking first
- Calling pop on an empty structure raises an error; code that assumes there is always something left to remove needs to check first or handle the exception.
- Assuming a stack or queue is the right structure just because a problem involves a list of items
- Neither restriction is required by every list-like problem - reaching for one out of habit, when the problem actually needs access to the middle or arbitrary positions, forces awkward workarounds instead of just using a plain list or array.
Strengths and trade-offs
Where it is strong
- The restricted interface is exactly what makes them predictable - you cannot accidentally read or remove from the middle, so there is less to reason about.
- They model common real processes directly: undo history is a stack, a print queue is a queue, with no translation needed between the concept and the code.
- Both support O(1) operations at their ends when backed by the right structure, such as a deque, or a list used only from one end.
The trade-offs
- The same restriction that makes them predictable also makes them useless the moment a problem needs access to something in the middle.
- An array-backed queue that removes from the front is O(n) per operation unless it is specifically designed for it, such as with a circular buffer or a deque.
- Recursion uses the call stack implicitly, so deep recursion can hit a real stack-size limit and crash, even though the code itself never mentions a stack.
Who needs this
Anyone writing algorithms involving parsing, matching, or traversal, and useful background for understanding why a runaway recursive function crashes with an error about the call stack.
Questions about stacks and queues
- What's a real-world example of a stack versus a queue?
- A stack of plates: you take from the top, the one you set down most recently. A line at a ticket counter: whoever arrived first is served first. The plates example is LIFO; the ticket line is FIFO.
- Why is Python's list a bad queue but a fine stack?
- Because append and pop from the end are both O(1), fine for stack behavior. But removing from the front is O(n), since every remaining element has to shift, bad for queue behavior. collections.deque is O(1) at both ends and is the right choice for a queue.
- What does 'stack overflow' actually mean?
- Every function call pushes a frame onto the call stack, and returning pops it off. Recursion that never reaches its base case keeps pushing frames without ever popping them, until the call stack exceeds its size limit and the program is forced to stop - that error condition is literally called a stack overflow.
- Is a deque a stack, a queue, or both?
- Both, effectively - it supports O(1) additions and removals at either end, so it can be used as a stack, working from one end only, or a queue, adding at one end and removing at the other, depending on which methods you call.