Python practice

Python stack practice questions

7 problems, ordered from easiest. They run in your browser, and 1 is free.

On this page11 sections

The idea in a minute
A pile where you only touch the top
When do you need one?
The classic: do the brackets match?
Undo
Values waiting for their answer: next greater element
A stack is also how recursion works
Stack or queue?
Questions people ask
Now try it yourself
More Python topics

A stack is a pile where you only touch the top, the last thing in is the first thing out. In Python a plain list does the job.

You will use it for matching brackets, undo, and a value that waits for a later answer, and see why it is also how recursion works inside Python.

A pile where you only touch the top

Think of plates stacked in a canteen. You put a clean plate on top, and you take a plate from the top. Never from the middle. The last plate you put on is the first one you take off. That rule is called last in, first out, and a stack is exactly that.

Python does not need a special type. A plain list is a stack: append puts something on top, pop takes the top off.

PythonPush, pop, peek

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack)
print(stack.pop())
print(stack.pop())
print(stack)
print(stack[-1])

['a', 'b', 'c']
c
b
['a']
a

stack[-1] looks at the top without removing it. That is the peek. Everything below is hidden until you pop what is above it.

When do you need one?

A stack fits whenever the most recent unfinished thing is the one you deal with next. Brackets waiting to be closed. Functions waiting to return. Edits you may want to undo. Browser pages you may go back to. If you ever feel "I need to remember what came before, and the latest first", it is a stack.

The classic: do the brackets match?

{[()]} is fine. ([)] is not, even though each type is closed. The rule: every closer must match the most recent opener that is still open. Most recent unfinished thing, so a stack.

Watch the stack catch a mismatch

Step 1 / 5

1def balanced(s):
2    stack, pair = [], {")": "(", "]": "[", "}": "{"}
3    for ch in s:
4        if ch in "([{":
5            stack.append(ch)
6        elif not stack or stack.pop() != pair[ch]:
7            return False
8    return not stack
9 
10print(balanced("{[()]}"), balanced("([)]"))

The stack

stack = []

Line 10

Trace the second call, balanced("([)]"). The stack starts empty.

PythonCheck that brackets match

def balanced(s):
    stack, pair = [], {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != pair[ch]:
            return False
    return not stack

print(balanced("{[()]}"), balanced("([)]"))

True False

Opener: push it. Closer: pop the top and check that it is the matching opener. If the stack is empty when a closer arrives, or the top is the wrong kind, return False. When the string ends, the stack must be empty, or something never closed.

PythonEdge cases: empty, only openers, extra closer

def balanced(s):
    stack, pair = [], {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != pair[ch]:
            return False
    return not stack

for text in ["", "()", "((", "())", "{[()]}", "([)]"]:
    print(repr(text), balanced(text))

'' True
'()' True
'((' False
'())' False
'{[()]}' True
'([)]' False

Watch outThe two end conditions

An extra closer ((), or a closer with nothing to match, is caught inside the loop. Leftover openers (((, are only caught by return not stack at the end. Forgetting that last line is the most common bug.

Undo

Every edit goes on the stack. Undo pops the last one.

PythonA tiny text editor

text = ""
history = []

def type_text(s):
    global text
    history.append(text)
    text += s

def undo():
    global text
    if history:
        text = history.pop()

type_text("Hello")
type_text(", world")
print(text)
undo()
print(text)
undo()
print(repr(text))
undo()
print(repr(text))

Hello, world
Hello
''
''

Each action saves the previous state before it changes anything. The last line shows an empty history is safe, because undo checks if history first.

Values waiting for their answer: next greater element

For each temperature, how many days until a warmer one? The brute-force approach scans ahead from every day. A stack does it in one pass. The idea: keep the days that are still waiting for a warmer day. When a warmer day arrives, it answers everyone on the stack who is colder.

PythonDays until a warmer day

temps = [30, 25, 28, 35, 27]
answer = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
    while stack and temps[stack[-1]] < t:
        j = stack.pop()
        answer[j] = i - j
    stack.append(i)
print(answer)

[3, 1, 1, 0, 0]

We push indexes, not temperatures, because we need to know how far away each day was. Day 3 (35) is warmer than everything waiting before it, so it answers days 0, 1 and 2 in one go. Day 4 (27) is waiting, and nothing warmer ever arrives, so it stays 0.

A stack is also how recursion works

When a function calls itself, Python keeps a stack of calls that are waiting. That is why deep recursion has a limit, and why you can turn any recursion into a loop with your own stack.

PythonSum a nested list with a stack instead of recursion

nested = [1, [2, 3], [4, [5]]]
total = 0
stack = [nested]
while stack:
    item = stack.pop()
    if isinstance(item, list):
        stack.extend(item)
    else:
        total += item
print(total)

Same answer as the recursive version in the recursion topic (15), and no recursion limit to worry about.

Stack or queue?

	Stack	Queue
Rule	Last in, first out	First in, first out
Real life	Pile of plates, undo	People in a line
Python	list: append and pop	collections.deque: append and popleft
Good for	Brackets, undo, depth first	Order of arrival, breadth first

RememberDo not pop from the front of a list

list.pop(0) is slow, because every other item shifts. If you need to take from the front, use deque.

Questions people ask

Why not just use a loop?

When the answer to one item depends on an earlier item that is still unfinished, a plain loop has nowhere to keep it. The stack is that place.

What happens if I pop an empty list?

IndexError: pop from empty list. Always check if stack first, or write the condition so it cannot happen.

What goes on the stack, values or indexes?

Whichever you need later. If the answer needs positions (days until, distances), push indexes. If you only need the values, push values.

Keep this checklist handy

Check that the stack is not empty before you pop it.
At the end, a leftover item on the stack usually means something never closed.
Push what is waiting, not everything. Keep the stack as small as the question needs.

Now try it yourself

7 stacks problems. They run right here in your browser, and you can start anywhere.

Warm up

One idea at a time. Do these in order.

1Valid ParenthesesFree

Getting comfortable

Two ideas together, or a trap to spot.

Want a guided order across every topic? Open the practice sheets or the Python hub.