---
title: "Стек (LIFO)"
url: https://algopath.pro/ru/patterns/stack
language: ru
summary: "Стек всегда отдаёт самый свежий положенный элемент первым. Поэтому он подходит всему, что закрывается в обратном порядке."
updated: 2026-08-24
---

# Стек (LIFO)

Стек всегда отдаёт самый свежий положенный элемент первым. Поэтому он подходит всему, что закрывается в обратном порядке.

## Стек (LIFO): как это работает?

У стека два действия: положить и снять. Последнее положенное возвращается первым.

Массива для него вполне достаточно. Вставка пишет в конец, снятие читает и укорачивает.

Кладите всё, что открывается. Это может быть скобка, каталог или отложенное вычисление.

Снимайте всё, что закрывается. Потом проверьте, что снятое соответствует закрывающему элементу.

Пустой стек при снятии значит, что вход испорчен. Непустой стек в конце значит, что что-то не закрыли.

Ничего ниже вершины никогда не читается. Именно это ограничение и держит O(1) на операцию.

- `стек = []` Проверяем строку ([]). Пока ничего не открыто.
- `стек = ['(']` Открывающая круглая скобка положена в стек.
- `стек = ['(', '[']` Квадратная скобка ложится сверху.
- `стек = ['(']` Закрывающая квадратная снимает свою пару.
- `стек = []` Закрывающая круглая снимает последнюю. Пустой стек значит верно.

## Стек (LIFO): когда применять?

- корректные скобки / сбалансированные скобки
- сопоставить самую недавнюю открывающую с ближайшей закрывающей
- отмена, откат к последнему состоянию, вложенная структура
- вычислить выражение с вложенными операторами
- обработать в порядке, обратном порядку поступления

## Стек (LIFO): с чем путают?

- **Монотонный стек** - Там стек упорядочен, и каждое снятие отвечает на вопрос. Обычный стек помнит лишь то, что открыто.
- **Рекурсия** - Каждый рекурсивный вызов и так лежит на стеке. Свой стек снимает ограничение по глубине.
- **Обход графа BFS / DFS** - Очередь даёт обход в ширину, стек даёт обход в глубину. Тот же обход, другой контейнер.
- **Монотонная дек-очередь (максимум/минимум окна)** - Дек читается и подрезается с обоих концов. Стек трогает только вершину.

## Стек (LIFO): сложность по времени и памяти

Каждая вставка и снятие стоят O(1), значит n операций дают O(n). Память в худшем случае O(n).

## Стек (LIFO): разбор примера

### Упростить путь к файлу

Дан абсолютный путь, в котором бывают точки и двойные точки. Верните кратчайший путь с тем же смыслом.

Двойная точка поднимает на каталог вверх, одиночная ничего не меняет.

Разбейте путь по слешам и идите по частям подряд.

Кладите настоящее имя, снимайте на двойной точке, пропускайте пустые части и одиночные точки. В конце склейте стек.

```javascript
function simplifyPath(path) {
    const stack = [];

    for (const part of path.split("/")) {
        if (part === "" || part === ".") continue;

        if (part === "..") {
            stack.pop(); // popping an empty stack is a no-op at the root
        } else {
            stack.push(part);
        }
    }

    return "/" + stack.join("/");
}
```

## Стек (LIFO): частые ошибки

- **Снимают, не проверив на пустоту** Снятие с пустого стека молча возвращает undefined. Проверьте размер, прежде чем верить значению.
- **Не смотрят, что осталось в конце** Непустой стек означает, что что-то не закрыли. Проверьте его после цикла.
- **Берут shift вместо pop** shift берёт с начала, а это уже очередь. Смысл всего цикла при этом переворачивается.
- **Кладут значения, когда нужны позиции** Многие такие задачи спрашивают, как далеко назад что-то было. Кладите индекс и читайте значение по нему.

## Стек (LIFO): задачи с собеседований

- **Правильные скобки** Кладите открывающую, снимайте и сверяйте на закрывающей.
- **Минимальный стек** Второй стек текущих минимумов отвечает за O(1).
- **Обратная польская запись** Кладите числа, снимайте два на каждой операции.
- **Упрощение пути** Кладите каталог, снимайте на двойной точке.
- **Простой калькулятор** Кладите текущий результат перед открывающей скобкой.
- **Декодирование строки** Кладите число повторов и текст перед каждой скобкой.
- **Сравнение строк с забоем** Каждый забой снимает последний сохранённый символ.

## JavaScript

```javascript
function isValid(s) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };
    for (const ch of s) {
        if (ch in pairs) {
            if (stack.pop() !== pairs[ch]) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.length === 0;
}
```

## Python

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

## PHP

```php
function isValid(string $s): bool {
    $stack = [];
    $pairs = [')' => '(', ']' => '[', '}' => '{'];
    foreach (str_split($s) as $ch) {
        if (isset($pairs[$ch])) {
            if (array_pop($stack) !== $pairs[$ch]) return false;
        } else {
            $stack[] = $ch;
        }
    }
    return count($stack) === 0;
}
```