Стеки и валидные скобки

Стек — это «последним пришёл, первым вышел», и он идеально решает задачи с вложенностью.

Стек — структура данных с дисциплиной LIFO (last in, first out): добавляем и забираем элементы только с одного конца.

Принцип LIFO

Представьте стопку тарелок: кладёте сверху, берёте тоже сверху. В Python стек — это обычный list: append кладёт, pop забирает последний. Обе операции — O(1).

stack = []
stack.append("A")
stack.append("B")
stack.append("C")
print("верхушка:", stack[-1])
print("снимаем:", stack.pop())
print("снимаем:", stack.pop())
print("осталось:", stack)

Вывод:

верхушка: C
снимаем: C
снимаем: B
осталось: ['A']

Классическая задача: валидные скобки

Дана строка из символов (), [], {}. Проверить, что все скобки корректно закрыты и вложены. Открывающую кладём на стек; при закрывающей проверяем, что сверху лежит парная открывающая.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

print(is_valid("()[]{}"))
print(is_valid("([{}])"))
print(is_valid("(]"))
print(is_valid("((("))

Вывод:

True
True
False
False

Как работает под капотом

Стек идеально отражает вложенность: последняя открытая скобка должна закрыться первой — ровно дисциплина LIFO. Когда встречаем закрывающую, на верхушке обязана быть её пара. Два условия провала: стек пуст (закрывающая без открывающей) или верхушка не парная. В конце стек должен быть пуст — иначе остались незакрытые скобки. Один проход — O(n) время, стек хранит до n символов — O(n) память.

Частые ошибки

Забыть финальную проверку len(stack) == 0 — строка ((( ошибочно пройдёт.
Не обработать pop из пустого стека — это исключение; сначала проверяйте if not stack.
Сравнивать сами символы, а не пары — путаница в типах скобок.

Итог

Стек — LIFO, операции push/pop за O(1).
Любая вложенность (скобки, теги, выражения) естественно ложится на стек.
Не забывайте проверять пустоту стека при pop и в конце.