Arrays, Lists, Stacks and Queues

Четыре базовых способа хранить последовательность. Отличаются не тем, что умеют, а тем, что у них дёшево, а что дорого.

Ключевые тезисы

Массив даёт доступ по индексу за константу, но вставка в середину линейна.
наоборот: вставка за константу, доступ по индексу — за линию.
и очередь — не структуры, а дисциплины доступа: LIFO и FIFO поверх массива или списка.
Поверх этих дисциплин строится отдельный приём — и дек: ближайший больший элемент и максимум в окне за один проход.

Какую задачу решает

Массив, список, и очередь хранят одно и то же — последовательность элементов. Выбор между ними никогда не про то, что структура «умеет»: умеют все всё. Выбор про цену: какая операция стоит константу, а какая — проход по всей длине.

и очередь стоят в этом ряду особняком. Это не структуры, а дисциплины доступа — правило, в каком порядке элементы забираются обратно. Стек отдаёт последний положенный и потому точно повторяет устройство вложенности: скобки, вызовы функций, отмена действий. Очередь отдаёт первый и задаёт обработку по слоям, на которой держится .

Отдельного разговора заслуживают два приёма поверх этих дисциплин — и дек. Первый за один проход находит для каждой позиции ближайший больший элемент, второй даёт максимум в без логарифма. Оба выглядят как трюки и оба на самом деле следуют из одного наблюдения: элемент, который уже никогда не станет ответом, можно выбросить сразу.

Ближайший больший за один проход

Есть ряд ежедневных значений метрики, и для каждого дня нужно знать, через сколько дней она впервые превысила текущий уровень. Наивно — для каждого дня идти вперёд до первого большего: на ровном ряде это квадрат. переворачивает задачу: в стеке лежат дни, для которых ответ ещё не найден, и значения по ним убывают. Приходит новый день — он сразу закрывает все дни в стеке, где значение меньше, и каждый из них снимается навсегда. Каждый день кладётся один раз и снимается один раз, поэтому вложенный while внутри цикла не делает решение квадратичным — и это ровно то место, которое стоит проговорить вслух на собеседовании.

Подробный разбор

4 подтемы — объяснения, формулы, примеры и интерактивные графики.

Выбор между массивом и списком — не вопрос вкуса и не вопрос того, что структура «умеет». Обе хранят последовательность и обе позволяют всё. Разница в том, какая операция стоит константу, а какая — проход по всей длине.

Операция	Массив		Дек
Доступ по индексу	$O (1)$	$O (n)$	$O (1)$
Вставка в конец	$O (1)$ амортизированно	$O (1)$	$O (1)$
Вставка в начало	$O (n)$	$O (1)$	$O (1)$
Вставка в середину	$O (n)$	$O (1)$ при известном узле	$O (n)$
Память на элемент	только значение	значение и ссылки	значение
Обход	последовательный, дружит с кешем	прыжки по памяти	последовательный

На практике

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

— не структура, а дисциплина доступа: положили сверху, сняли сверху. Она в точности повторяет устройство вложенности, поэтому любая задача, где что-то открывается и должно закрыться в обратном порядке, решается стеком.

символ     действие                          стек

(          кладём                            (
[          кладём                            ( [
{          кладём                            ( [ {
}          вершина { -- парная, снимаем      ( [
]          вершина [ -- парная, снимаем      (
)          вершина ( -- парная, снимаем      пусто

стек пуст в конце -> последовательность правильная

Проверка скобочной последовательности ( [ { } ] )

Скобки и теги — проверка вложенности в выражениях, JSON, XML, HTML.
Вычисление выражений — обратная польская запись и алгоритм сортировочной станции.
Отмена действий — история правок, где откатывается последнее.
Рекурсия без рекурсии — обход дерева явным стеком, когда глубина грозит переполнить системный.
Упрощение путей — a/b/../c — это каталогов.

На практике

и вызов функции — одно и то же: возврат всегда происходит к последнему вызвавшему. Поэтому любая механически переписывается в цикл со стеком, и в этом смысле рекурсия — просто синтаксис поверх этой структуры.

Два приёма, построенных на стеке и деке, разобраны отдельно: они решают не задачу хранения, а задачу поиска. за один проход находит для каждой позиции ближайший больший элемент, монотонный дек — максимум внутри .

Разбор целиком — в теме монотонный стек и дек: трассировка по шагам, инвариант, четыре комбинации «больший или меньший, слева или справа» и типичные ошибки.

Сигнал в условии	Структура
Вложенность, парность, «последнее открытое»
«Ближайший больший (меньший) справа или слева»
«Сколько ждать до следующего большего»
Максимум или минимум внутри	дек
Обработка в порядке поступления, «по слоям»
Нужен текущий минимум при добавлениях и удалениях
Частые вставки в начало	дек или список, но не массив

Наивное решение звучит как «для каждого элемента ищем ближайший подходящий» — это почти всегда .
Требуется и порядок, и быстрый доступ по значению — одной структуры мало, берут связку словаря и списка (так устроен LRU-кеш).
Нужен k-й по величине, а не крайний — это уже или порядковые статистики, а не .

На практике

Быстрая проверка: если в решении хочется «вернуться назад и посмотреть, что было», спросите, в каком порядке вы будете туда возвращаться. В обратном — , в прямом — очередь, с обеих сторон — дек.

Где применяется

Разбор вложенных структурСкобки, теги, выражения, пути — везде .
Ближайший больший элементТемпературы, биржевые диапазоны, прямоугольник в гистограмме — .
задаёт порядок «сначала ближние, потом дальние».
Потоковая обработкаКольцевой буфер и скользящий максимум по последним k событиям.

Плюсы, минусы и альтернативы

Плюсы

Операции за константу: и , и очередь, и дек не зависят от длины.
снимает целый порядок сложности в задачах «ближайший подходящий».
Реализуются поверх массива, поэтому дружат с кешем и не требуют ссылок на каждый элемент.

Минусы

Ни одна из дисциплин не даёт доступа в середину — за ним идут к другим структурам.
отвечает на один вопрос: ближайший, а не k-й и не любой подходящий.
привлекателен асимптотически и почти всегда проигрывает массиву на практике.

Брать, если

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

Не брать, если

Нужен k-й по величине или текущий минимум при произвольных удалениях — это .
Нужен доступ по значению — это .
Нужен порядок и диапазонные запросы одновременно — это дерево поиска.

Чем заменяют

Trees and HeapsактуальноДеревья и кучи · Алгоритмы и структуры данныхНужен минимум при произвольных вставках и удалениях — это .Hash TablesактуальноХеш-таблицы · Алгоритмы и структуры данныхДоступ нужен по ключу, а не по порядку.Two Pointers and Sliding WindowактуальноДва указателя: семейство приёмов · Алгоритмы и структуры данных само по себе решает задачу и хранить кандидатов не нужно.

Видеолекции

Записи университетских курсов, где эта тема звучит. Где у записи есть тайм-коды, ссылка открывает её с нужной секунды; где их не проставили — с начала.

20:51Очереди задач для вычисленийПрикладной MLOps · Лекция «Вычислительные системы ML» · 3 ч 1 мин с началаСтруктуры данных (словарь, множество, связный список, стек, очередь). Хэш-таблицы, хэш-функцииАлгоритмы и структуры данных · Лекция · 2 ч 39 мин

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

Структуры данных

Проверить себя

Тема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.

Тест: Алгоритмы и структуры данных29

Следующий шагПроверить себя: Алгоритмы и структуры данныхТема встречается в этом тесте 1 раз. Ошибка приведёт обратно на эту страницу — с объяснением, что именно не сошлось.Перейти →

Глава «Алгоритмы и структуры данных» последний раз правилась 17 сентября 2026 г.. Нашли ошибку — напишите.

Ключевые тезисы

Какую задачу решает

Подробный разбор

Где применяется

Плюсы, минусы и альтернативы

Плюсы

Минусы

Брать, если

Не брать, если

Чем заменяют

Видеолекции

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

Hash Tables85%

Trees and Heaps85%

Sorting Algorithms85%

Order Statistics85%

Caching85%

Цена операции

Стек (LIFO)

Очередь (FIFO)

Монотонный стек и дек

Arrays, Lists, Stacks and Queues

Ключевые тезисы

Какую задачу решает

Подробный разбор

1Цена операции, а не набор возможностейМассив и список умеют одно и то же — отличается только счёт.

2Стек: последнее открытое закрывается первымВложенность в условии — почти всегда стек в решении.

3Монотонный стек и декПриём поверх этих структур вынесен в отдельную тему.

4Как распознать паттернСлова условия, за которыми стоит конкретная дисциплина доступа.

Где применяется

Плюсы, минусы и альтернативы

Плюсы

Минусы

Брать, если

Не брать, если

Чем заменяют

Видеолекции

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

Hash Tables85%

Trees and Heaps85%

Sorting Algorithms85%

Order Statistics85%

Caching85%

Ключевые понятия4 определения из текста — каждое со ссылкой на разбор

Цена операции

Стек (LIFO)

Очередь (FIFO)

Монотонный стек и дек