Lists as Stacks

Concepts covered: Stack & Queue

A stack hands back items in the reverse of the order they arrived: the last item in is the first item out. A Python list does this with 2 methods that both work at the right-hand end. append(x) pushes x onto the top, and pop() with no argument removes the top item and returns it. Neither method moves the other items, so a push or a pop stays fast however tall the stack gets.

stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("after pushes:", stack)

item = stack.pop()
print("popped:", item)
print("now:", stack)

item = stack.pop()
print("popped:", item)
print("now:", stack)

after pushes: ['first', 'second', 'third']
popped: third
now: ['first', 'second']
popped: second
now: ['first']

An empty list is falsy, so while stack: runs until the stack is drained and if stack: guards a pop. Without the guard, popping an empty stack raises an IndexError.

stack = ["a"]
print(stack.pop())
try:
    stack.pop()
except IndexError as err:
    print("IndexError:", err)

Output:

a
IndexError: pop from empty list

Undo is a stack

Undo needs the most recent change first, which is the order a stack returns. Before each edit, push the current value. Undoing pops the last saved value and restores it. Rolling back a sequence of applied schema changes has the same shape: each applied change is pushed, and a rollback pops them newest first.

history = []
text = ""

history.append(text)
text = "Hello"
print("after edit 1:", text)

history.append(text)
text = "Hello World"
print("after edit 2:", text)

text = history.pop()
print("after undo:", text)
print("history:", history)

after edit 1: Hello
after edit 2: Hello World
after undo: Hello
history: ['']

Matching brackets

Checking that brackets nest correctly in a config string or a SQL expression is a stack problem. Push each opening bracket. When a closing bracket arrives, the top of the stack must be its partner, and anything else means the brackets cross. At the end, an empty stack means every opener was closed. The PAIRS lookup maps each closer to its opener, the same dict-based dispatch you have written before.

PAIRS = {")": "(", "]": "[", "}": "{"}

def is_balanced(s):
    stack = []
    for char in s:
        if char in "([{":
            stack.append(char)
        elif char in ")]}":
            if not stack or stack.pop() != PAIRS[char]:
                return False
    return len(stack) == 0

print(is_balanced("([)]"))

False

On "([)]", the function pushes ( and then [. When ) arrives, [ is on top, so the function returns False at the third character without reading the last. The not stack test in the same condition catches a closer with nothing open, like "())". It short-circuits before pop() could raise.

Walking nested data without recursion

A recursive function keeps its unfinished work on Python's call stack. Holding that work in a list instead avoids the recursion limit on deeply nested input. Pop an item; if it is a list, push its children; otherwise record it. Pushing the children in reversed order puts the first child on top, so values come out in reading order.

nested = [1, [2, [3, 4]], 5]

stack = [nested]
found = []
while stack:
    item = stack.pop()
    if isinstance(item, list):
        for child in reversed(item):
            stack.append(child)
    else:
        found.append(item)
print(found)

Output:

[1, 2, 3, 4, 5]

Why a list makes a poor queue

A queue is first-in first-out, and pop(0) gives that order from a list, but removing slot 0 shifts every remaining item one slot to the left, so each call does work proportional to the list's length. pop() at the end shifts nothing. Python has a structure built for removing from the front, covered in a later lesson; until then, keep lists for stacks.

• 999,999
• 0

What does this program print?

stack = []
for token in ["a", "b", "POP", "c", "POP", "POP"]:
    if token == "POP":
        print(stack.pop(), end=" ")
    else:
        stack.append(token)
print(stack)

• a b c []
• c b a []
• b c a ['a']
• b c a []

About this lesson

This section is part of the Lists: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.