Стеки и очереди
Когда важен порядок обработки
Массивы и хеш-таблицы помогают быстро обращаться к данным по индексу или ключу, но иногда задача устроена иначе: важно не столько что хранится, сколько в каком порядке элементы должны извлекаться. Стек отдаёт последний добавленный элемент, очередь — первый, а deque позволяет работать сразу с обоими концами.
Эти структуры особенно полезны, когда алгоритму нужно помнить незавершённые действия, обрабатывать события в порядке поступления или поддерживать небольшой набор «кандидатов», из которого элементы уходят по строгому правилу. На этой базе строятся и более сильные приёмы — монотонные структуры и проверки вложенности.
Что входит в раздел
- Стек. Разберём принцип LIFO и операции добавления, просмотра и удаления вершины.
- Очередь. Перейдём к принципу FIFO и обработке элементов в порядке их поступления.
- Deque. Научимся добавлять и удалять элементы с обоих концов одной структуры.
- Монотонный стек. Увидим, как поддерживать стек в упорядоченном состоянии и быстро находить ближайшие подходящие элементы.
- Монотонная очередь. Применим похожую идею к окну данных и научимся сохранять только полезных кандидатов.
- Задачи со скобками. Используем стек для проверки правильной вложенности и сопоставления открывающих и закрывающих символов.
- Очередь на стеках. Соберём одну абстракцию поверх другой и разберём, как перенос элементов меняет порядок извлечения.
Один интерфейс — разные правила
Deque<Integer> values = new ArrayDeque<>();
values.push(10);
values.push(20);
int last = values.pop(); // 20В следующих темах важно будет не запоминать набор методов, а видеть правило, по которому структура отдаёт элементы. Именно это правило обычно подсказывает, нужен ли задаче стек, очередь или deque.