Стеки: LIFO и трюк со скобками

Цели урока

• Понять принцип LIFO (Last In, First Out)
• Реализовать стек на массиве и связном списке
• Решить задачу проверки сбалансированных скобок
• Понять роль стека вызовов в рекурсии

Предварительные знания

• Связные списки и их операции

• Связные списки

2006 год. Firefox 2.0 выходит с функцией Undo для закрытых вкладок. За кулисами - стек URL-ов. Сегодня Chrome держит стек навигации на каждой вкладке, VS Code держит стек правок на каждом файле, Node.js держит стек вызовов на каждый async-контекст. Одна структура - тысячи применений.

• **VS Code Undo/Redo** - стек правок, Ctrl+Z извлекает последнее изменение
• **Браузерная навигация** - кнопки назад/вперёд - два стека истории
• **TypeScript-компилятор** - проверка вложенности generic-типов через стек
• **React reconciler** - Fiber-алгоритм обходит дерево компонентов через explicit стек

Call stack и рождение структурного программирования

В 1960 году ALGOL-60 стал первым языком с вложенными процедурами и локальными переменными. Это потребовало системного решения для хранения контекста вызовов - так появился call stack как обязательный элемент рантайма. Эдсгер Дейкстра участвовал в разработке ALGOL-60 и формализовал понятие activation record. Шестьдесят лет спустя JavaScript V8, Python CPython и JVM используют ту же модель.

LIFO - Last In, First Out

Каждый раз, когда браузер нажимает «Назад» - он достаёт последний URL из стека истории. Каждый раз, когда TypeScript-компилятор раскрывает вложенные generic-типы - он использует стек. Chrome DevTools показывает call stack при каждой ошибке. LIFO - принцип, который работает повсеместно.

**LIFO** (Last In, First Out) - принцип стека. Последний пришёл - первый ушёл.

Операции: push, pop, peek

У стека всего **3 основные операции**, и все они O(1). Три операции - вся API. V8 JavaScript engine обрабатывает миллионы функциональных вызовов в секунду именно благодаря этой простоте.

• **push(x)** - положить элемент на вершину
• **pop()** - снять и вернуть элемент с вершины
• **peek() / top()** - посмотреть вершину без удаления

**pop() на пустом стеке** - ошибка! В Node.js это может обрушить процесс с unhandled exception. Всегда проверяй isEmpty() перед pop.

Реализация: массив или список?

Стек можно реализовать двумя способами. Оба дают O(1) для всех операций. Разница - в константах и cache behavior. V8 предпочитает array-based: CPU cache locality ускоряет доступ к вершине в разы.

**Что выбрать?** Массив: проще, лучше cache locality, но может потребовать resize. Список: стабильный O(1) без resize, но больше памяти на указатели.

Задача: Проверка скобок

Классическая задача - проверить, что все скобки **сбалансированы**. TypeScript-компилятор делает это на каждом файле. ESLint - тоже. За O(n) одним проходом. Инструмент - стек.

**Алгоритм со стеком:**

1. Встретили открывающую скобку - push в стек
2. Встретили закрывающую - pop и проверить соответствие
3. В конце стек должен быть пустым

Call Stack - стек вызовов

Когда функция вызывает функцию - куда сохраняется контекст? В **стек вызовов**. Каждый Node.js процесс, каждый Python интерпретатор, каждый JVM thread имеют свой стек вызовов. Stack trace в Sentry - это дамп этого стека в момент ошибки.

**Stack Overflow** - переполнение стека. Python: >1000 вызовов по умолчанию. Node.js: ~15000. Глубокая рекурсия без tail-call optimization - прямой путь к crash.

**Отладка**: stack trace в Sentry/Datadog показывает именно стек вызовов в момент ошибки - путь от точки входа до места падения.

Реализуй функцию, которая переворачивает строку с помощью стека: ```python def reverse_string(s): # Используй стек для разворота строки pass # reverse_string("hello") -> "olleh" ```

def reverse_string(s): stack = [] # Кладём все символы в стек for char in s: stack.append(char) # Извлекаем в обратном порядке result = [] while stack: result.append(stack.pop()) return ''.join(result)

Вычисли выражение в обратной польской записи (RPN): ```python def eval_rpn(tokens): # tokens = ["2", "1", "+", "3", "*"] -> (2+1)*3 = 9 # tokens = ["4", "13", "5", "/", "+"] -> 4+(13/5) = 6 pass ```

def eval_rpn(tokens): stack = [] for token in tokens: if token in '+-*/': b = stack.pop() # Второй операнд a = stack.pop() # Первый операнд if token == '+': stack.append(a + b) elif token == '-': stack.append(a - b) elif token == '*': stack.append(a * b) elif token == '/': stack.append(int(a / b)) else: stack.append(int(token)) return stack[0]

Реализуй MinStack - стек с операцией getMin() за O(1): ```python class MinStack: def __init__(self): pass def push(self, val): pass def pop(self): pass def top(self): pass def getMin(self): # O(1)! pass ```

class MinStack: def __init__(self): self.stack = [] # Основной стек self.min_stack = [] # Стек минимумов def push(self, val): self.stack.append(val) # Добавляем в min_stack только если val <= текущему минимуму if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self): val = self.stack.pop() # Если удаляем текущий минимум - удаляем и из min_stack if val == self.min_stack[-1]: self.min_stack.pop() return val def top(self): return self.stack[-1] def getMin(self): return self.min_stack[-1]

Связанные темы

Стек - основа для многих алгоритмов:

• Очереди — FIFO - противоположный принцип (First In, First Out)
• DFS — Поиск в глубину использует стек
• Backtracking — Любую рекурсию можно переписать через явный стек

Ключевые идеи

• **LIFO**: последний вошёл - первый вышел
• **Операции**: push, pop, peek - все O(1)
• **Реализация**: массив (лучше cache) или связный список (стабильный O(1))
• **Применения**: undo, скобки, call stack, DFS, backtracking
• **Stack Overflow**: переполнение при глубокой рекурсии без tail-call

Вопросы для размышления

• Почему стек идеально подходит для проверки скобок?
• Как реализовать Redo (повторить) поверх Undo?
• Можно ли реализовать очередь с помощью двух стеков?

Связанные уроки

• ds-02-linked-lists — Linked stack строится поверх узлов из урока о списках
• ds-04-queues — Очередь - противоположный принцип, реализуется через два стека
• alg-13-dfs — DFS обходит граф через явный стек или системный call stack
• alg-03-amortized — Амортизация объясняет O(1) для array-based stack с resize
• alg-22-backtracking — Backtracking - это явный стек состояний поиска
• ds-05-deque — Deque обобщает стек - push/pop с обоих концов
• comp-12-lr-parsing