Stacks and Queues
Two structures built on the same idea, restricted access, that show up everywhere from function calls to task scheduling
Introduction
Arrays and linked lists let you insert and remove anywhere. Stacks and queues deliberately take that freedom away. A stack only lets you add or remove from one end, the "top". A queue only lets you add at one end and remove from the other. That restriction isn't a limitation, it's the whole point: it models exactly how undo history, browser back-buttons, function calls, and task scheduling actually behave, and both structures can be built directly on top of what you already know from Lessons 2 and 3.
What is a Stack? (LIFO)
A stack is Last In, First Out (LIFO). The last item pushed on is always the first one popped off, like a stack of plates: you can only take from the top.
Stack (LIFO)
Figure 1: Only the top element can be added or removed
A Python list is already a great stack: append and pop (with no argument) both operate on the end. Lesson 2 already established append is O(1) amortized and pop from the end is a plain O(1), no shifting either way.
class Stack:
def __init__(self) -> None:
self._items: list[int] = []
def push(self, value: int) -> None:
# O(1) amortized: the same append() from Lesson 2
self._items.append(value)
def pop(self) -> int:
# O(1): removing from the end needs no shifting
if not self._items:
raise IndexError("pop from an empty stack")
return self._items.pop()
def peek(self) -> int:
if not self._items:
raise IndexError("peek from an empty stack")
return self._items[-1]
def is_empty(self) -> bool:
return len(self._items) == 0stack = Stack() stack.push(1) stack.push(2) stack.push(3) print(stack.peek()) print(stack.pop()) print(stack.pop()) print(stack.is_empty())
Expected Output:
3 3 2 False
Practical Pattern: Balanced Parentheses
Checking whether brackets are balanced is the textbook stack problem, and it shows up for real in parsers, compilers, and code editors. Every opening bracket goes on the stack; every closing bracket must match whatever is currently on top.
def is_balanced(expression: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for char in expression:
if char in "([{":
stack.append(char)
elif char in ")]}":
# An unmatched closer, or one that doesn't match the last opener
if not stack or stack.pop() != pairs[char]:
return False
# Balanced only if every opener eventually found its closer
return not stackprint(is_balanced("(a[b]{c})"))
print(is_balanced("(a[b)]"))
print(is_balanced("((("))Expected Output:
True False False
Why a Stack, Specifically?
The most recently opened bracket must be the next one closed. That's LIFO by definition, which is exactly why a stack, not a queue, is the right tool here.
What is a Queue? (FIFO)
A queue is First In, First Out (FIFO). Whoever joined first gets served first, like a checkout line.
Queue (FIFO)
Figure 2: Items leave from the front and join at the back
enqueue(x) adds x to the back, dequeue() removes and returns whatever is at the front.
Implementing a Queue: List vs Deque
A stack maps perfectly onto a Python list because both of its operations touch the end. A queue removes from the opposite end it adds to, and that's exactly the O(n) trap from Lesson 2.
❌ Naive: list.pop(0) shifts everything
class SlowQueue:
def __init__(self) -> None:
self._items: list[int] = []
def enqueue(self, value: int) -> None:
self._items.append(value) # O(1)
def dequeue(self) -> int:
# O(n): every remaining element must shift one position to the left,
# this is the exact O(n) trap Lesson 2 warned about
return self._items.pop(0)✅ Efficient: collections.deque
from collections import deque
class Queue:
def __init__(self) -> None:
self._items: deque[str] = deque()
def enqueue(self, value: str) -> None:
self._items.append(value) # O(1)
def dequeue(self) -> str:
# O(1): deque tracks both ends directly, nothing needs to shift
return self._items.popleft()
def is_empty(self) -> bool:
return len(self._items) == 0queue = Queue()
queue.enqueue("first")
queue.enqueue("second")
queue.enqueue("third")
print(queue.dequeue())
print(queue.dequeue())
print(queue.is_empty())Expected Output:
first second False
This is the deque from Lessons 2 and 3, backed by linked blocks with O(1) operations at both ends, which is exactly what a correct queue needs.
Complexity at a Glance
| Structure | Add | Remove | Peek |
|---|---|---|---|
Stack (list) | O(1) amortized | O(1) | O(1) |
Naive queue (list) | O(1) amortized | O(n) | O(1) |
Queue (deque) | O(1) | O(1) | O(1) |
The lesson here generalizes: it's never the operation itself that's slow, it's whichever end of the underlying structure that operation has to touch.
Bonus: Building a Queue from Two Stacks
A classic interview exercise: implement a FIFO queue using only two LIFO stacks, no deque allowed. The trick is to let one stack absorb new items and only reverse them into a second stack when the front is actually needed:
class TwoStackQueue:
def __init__(self) -> None:
self._in_stack: list[int] = []
self._out_stack: list[int] = []
def enqueue(self, value: int) -> None:
# O(1): always just push onto the "in" stack
self._in_stack.append(value)
def dequeue(self) -> int:
if not self._out_stack:
# Only pay the O(n) transfer when the "out" stack runs dry,
# this flips the order back to FIFO
while self._in_stack:
self._out_stack.append(self._in_stack.pop())
return self._out_stack.pop()q = TwoStackQueue() q.enqueue(1) q.enqueue(2) print(q.dequeue()) # 1, the first one in q.enqueue(3) print(q.dequeue()) # 2 print(q.dequeue()) # 3
Expected Output:
1 2 3
Each value is pushed and popped from _in_stack once, and pushed and popped from _out_stack once, over its entire lifetime, at most 4 operations total no matter how many times dequeue is called in between. Spread across all the calls that benefit from an already-loaded _out_stack, the amortized cost per operation is O(1), the same amortized reasoning from Lesson 2's dynamic array resizing.
Key Takeaways
- Stacks are LIFO - push and pop both happen at the same end, and a Python list handles this natively in O(1)
- Queues are FIFO - items leave from the opposite end they entered, which a plain list handles badly
list.pop(0)is O(n) - always reach forcollections.dequewhen you need real queue behavior- Stacks power bracket matching, undo history, and function call stacks - anywhere "most recent first" applies
- Restricting access is a design choice - giving up flexibility is what makes both structures fast and predictable