A stack is a list you only touch from one end
A stack is last-in, first-out. The last thing you push is the first thing you pop. Think of a stack of plates: you take from the top, not the bottom.
In Python, a plain list already is a stack. append pushes, pop pops, both from the end, both O(1):
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
top = stack.pop() # 3
That is the whole API. The reason stacks matter is not the data structure, it is the pattern: any time you need to remember "what was I doing before this?" and unwind it in reverse order, you want a stack. Nested brackets, undo history, the call stack itself, parsing, evaluating expressions. When you see nesting, think stack.
Matching parentheses
This is the canonical stack interview question, and it shows the pattern cleanly. You are given a string of brackets and asked whether they are balanced.
def is_balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
Every opening bracket goes on the stack. Every closing bracket must match whatever is on top. If the stack is empty when you hit a closer, or the top is the wrong type, it is unbalanced. At the end the stack must be empty, otherwise you left something open. One pass, O(n) time, O(n) space. Notice you never search backward through the string. The stack remembers for you.
Monotonic stacks: the trick that looks like magic
Some problems ask, for each element, "what is the next element bigger than me?" The brute force is a nested loop, O(nĀ²). A monotonic stack gets you to O(n), and it feels like cheating the first time you see it.
The idea: keep a stack of indices whose values are waiting for their answer. When a new element arrives, it resolves everyone on the stack it is bigger than.
def next_warmer_day(temps):
result = [0] * len(temps)
stack = [] # indices of days still waiting
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
prev = stack.pop()
result[prev] = i - prev
stack.append(i)
return result
Given [73, 74, 75, 71, 69, 72, 76, 73] this returns how many days until a warmer temperature for each day. Each index is pushed once and popped at most once, so despite the inner while, the total work is O(n). The stack stays monotonically decreasing. Whenever that would be violated, you pop, and each pop resolves an answer. Next-greater, next-smaller, largest-rectangle-in-histogram, daily-temperatures all use this shape. Learn to recognize it.
A queue is a stack's opposite, and a list is the wrong tool
A queue is first-in, first-out. The first thing you enqueue is the first thing you dequeue. A checkout line. You need queues for anything that processes items in arrival order, most importantly breadth-first search.
Here is the trap. You might reach for a list and dequeue from the front:
queue = []
queue.append(x) # enqueue: O(1), fine
queue.pop(0) # dequeue from front: O(n), a trap
list.pop(0) is O(n). Removing the first element forces Python to shift every remaining element down one slot. Do that n times and your "queue" is quietly O(nĀ²). On a small input you will never notice. On a BFS over 100,000 nodes it will time out, and you will not know why.
Use collections.deque. A deque (double-ended queue) gives you O(1) at both ends:
from collections import deque
queue = deque()
queue.append(x) # enqueue at the right: O(1)
queue.popleft() # dequeue from the left: O(1)
deque is also your stack-plus-queue Swiss army knife. append/pop for a stack, append/popleft for a queue, appendleft and extendleft when you need the other side. It is implemented as a doubly linked list of blocks, so both ends are cheap. The one thing it is bad at is random indexing in the middle, which you almost never need for a queue.
BFS: the reason queues earn their keep
Breadth-first search explores a graph level by level: all your neighbors, then all their neighbors. That "process in the order you discovered them" is exactly FIFO, so BFS is a queue with a visited set.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
Two rules keep this correct and fast. Mark a node visited when you enqueue it, not when you dequeue it, or you will add the same node several times before it is processed. And always popleft, never pop, or you have accidentally written depth-first search. Because BFS visits nodes in order of distance from the start, it finds the shortest path in an unweighted graph for free, which is why it shows up constantly in interviews.
What to actually remember
Stack, LIFO, use a plain list, and reach for it whenever a problem nests or unwinds. Monotonic stack for next-greater-style questions, O(n) instead of O(nĀ²). Queue, FIFO, use deque and never list.pop(0), because that one line turns a linear algorithm quadratic. BFS is a queue plus a visited set, and it hands you shortest paths on unweighted graphs.
If you want more reps on the Python side of this, the DSA with Python course drills these patterns interactively, and Advanced Python Programming goes deeper on collections internals. The data structures here are small. The patterns they unlock are not.