Стек — это коллекция LIFO (Last-In, First-Out): последний добавленный элемент удаляется первым. Вы обращаетесь только к вершине.
Операции
text
push(3) push(7) pop()->7 peek()->3
[ 3 ] [ 7 ] [ 3 ] [ 3 ]
[ 3 ] top
top
Пример
python
stack = []
stack.append('a') # push
stack.append('b') # push
top = stack[-1] # peek -> 'b'
stack.pop() # pop -> 'b'
Все операции имеют сложность O(1), если стек поддерживается динамическим массивом или связным списком.
| Операция | Время |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
Основное применение
- Function call stack — отслеживает активные вызовы и локальные переменные.
- Undo/redo — push для каждого действия; pop для отмены.
- Expression evaluation / parsing — сопоставление скобок, преобразование инфиксной нотации в постфиксную.
- Backtracking & DFS — сохранение информации о том, куда вернуться.
Почему это важно
Стек моделирует принцип "делай последнее первым", который встречается везде — от рекурсии до кнопки "назад" в браузере.
Умение сразу распознать паттерн LIFO подсказывает использование стека, нередко превращая запутанную задачу в несколько чистых операций push/pop.