VulnTech Stacks: Last In, First Out | DSA with Python

A pile of plates

A stack only lets you touch the top. The last thing you put on is the first thing you take off: LIFO (last in, first out).

Think of it like this: A stack of plates: you put clean plates on top and take plates from the top. Your browser's Back button and the Undo button in an editor work the same way.

A Python list is a great stack

Stack operation	Python	Big-O
push (put on top)	`stack.append(x)`	O(1)
pop (take from top)	`stack.pop()`	O(1)
peek (look at top)	`stack[-1]`	O(1)
is it empty?	`not stack`	O(1)

history = []
for page in ["home", "news", "sports", "scores"]:
    history.append(page)
    print("visit", page, "->", history)

while len(history) > 1:
    left = history.pop()
    print("back from", left, "to", history[-1])

Output

visit home -> ['home']
visit news -> ['home', 'news']
visit sports -> ['home', 'news', 'sports']
visit scores -> ['home', 'news', 'sports', 'scores']
back from scores to sports
back from sports to news
back from news to home

Checking brackets

Are the brackets in {[()()]} correctly matched? Push every opening bracket. Each closing bracket must match the opening bracket on top of the stack:

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack            # nothing left open

for t in ["{[()()]}", "([)]", "((", "print(a[0])"]:
    print(t, balanced(t))

Output

{[()()]} True
([)] False
(( False
print(a[0]) True

Common mistake: Calling pop() on an empty list crashes with IndexError. Check if stack first.