Что такое стек и для чего он используется?

Question

IT Interview Practice · Accepted Answer

**Стек** — это коллекция **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.

Операции

Пример

Основное применение

Почему это важно

Похожие вопросы