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

Стек: последним пришёл — первым вышел

Стек устроен как стопка бумаг на столе: новый лист кладут наверх, и берут тоже сверху. Доступен только верхний элемент — тот, что положили последним. Это и есть принцип LIFO (Last In, First Out — «последним пришёл, первым вышел»).

Операций всего три:

  • push — положить элемент на вершину;
  • pop — снять элемент с вершины (и получить его);
  • peek — посмотреть верхний элемент, не снимая.

Реализовать стек проще всего на массиве: храним индекс вершины top, при push увеличиваем его и пишем в ячейку, при pop читаем и уменьшаем.

class Stack {
    private long[] a;
    private int top = -1;
    Stack(int size) { a = new long[size]; }
    void push(long v) { a[++top] = v; }
    long pop()        { return a[top--]; }
    long peek()       { return a[top]; }
    boolean isEmpty() { return top == -1; }
}

Все операции — O(1): доступ всегда к одной и той же позиции, вершине. Размер стеку обычно нужен небольшой — это временная рабочая структура.

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

  • обратный порядок. Сложили элементы в стек и достали — получили их задом наперёд (например, перевернуть строку).
  • проверка парных скобок. Открывающую скобку кладём в стек, на закрывающую снимаем и проверяем, что она парная. Так компиляторы ловят несбалансированные (, {, [.
  • отмена действий (undo). Каждое действие — в стек; отмена снимает последнее.
  • стек вызовов. Сам язык использует стек: при вызове метода в него кладётся адрес возврата и аргументы, при выходе — снимаются. Поэтому рекурсия и работает.

Очередь: первым пришёл — первым вышел

Очередь — как очередь в магазине: встают в хвост, обслуживают с головы. Первым выйдет тот, кто первым пришёл, — принцип FIFO (First In, First Out). Операции:

  • enqueue — добавить элемент в хвост;
  • dequeue — забрать элемент из головы.

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

Циклическая очередь

Наивная реализация очереди на массиве быстро упирается в проблему: голова и хвост «уползают» вправо, и левая часть массива пустует зря. Решение — циклическая очередь (кольцевой буфер): когда хвост доходит до конца массива, он перескакивает в начало, если там уже освободилось место. Индексы считают по модулю длины массива, и массив используется по кругу. Так enqueue и dequeue остаются O(1) без сдвигов.

Дек

Дек (deque, double-ended queue) — «двусторонняя очередь»: добавлять и забирать можно с обоих концов. Это обобщение: если разрешить операции только с одного конца, дек превращается в стек; если добавлять с одного, а забирать с другого — в очередь. Удобен, когда нужна гибкость обоих подходов сразу.

Приоритетная очередь

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

Простую приоритетную очередь можно сделать на упорядоченном массиве (вставляем с сохранением порядка — тогда выемка максимума мгновенна, но вставка O(N)). Когда нужна эффективность, её строят на особой структуре — куче (пирамиде), где и вставка, и выемка приоритетного элемента стоят O(log N). Приоритетные очереди — сердце многих алгоритмов, например поиска кратчайшего пути Дейкстры.

Стек в деле: арифметические выражения

Классическое применение стека — разбор арифметических выражений. Человеку привычна инфиксная запись 3 × (4 + 5), но программе удобнее постфиксная (обратная польская) 3 4 5 + ×, где не нужны скобки. Оба шага — и перевод инфиксной записи в постфиксную, и вычисление постфиксной — делаются с помощью стека: операнды и операторы временно складываются в стек и снимаются в нужный момент. На этом принципе работали старые калькуляторы и работают многие интерпретаторы.

Коротко

  • Стек — LIFO, доступен только верхний элемент; операции push/pop/peek, все O(1). Применяют для обращения порядка, проверки скобок, отмены действий, стека вызовов.
  • Очередь — FIFO, добавляют в хвост, забирают с головы; для обработки задач в порядке поступления. Циклическая очередь использует массив по кругу, чтобы не терять место.
  • Дек — очередь с доступом с обоих концов; обобщает стек и очередь.
  • Приоритетная очередь отдаёт первым элемент с наибольшим приоритетом; эффективно реализуется на куче.
  • Ограничение доступа — не недостаток, а то, что делает эти структуры простыми, быстрыми и точно подходящими под свои задачи.

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