Стеки и очереди

← назад к разделу

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

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

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

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

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

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

живой пример

class Stack {
    private final 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; }

    public static void main(String[] args) {
        Stack s = new Stack(4);
        s.push(17);
        s.push(42);
        s.push(8);
        System.out.println("на вершине: " + s.peek());
        StringBuilder order = new StringBuilder();
        while (!s.isEmpty()) order.append(s.pop()).append(' ');
        System.out.println("выходят: " + order);
    }
}

Положили 17, 42, 8 — вышли 8, 42, 17. Все операции — O(1): доступ всегда к одной и той же позиции, вершине.

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

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

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

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

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

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

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

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

Дек

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

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

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

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

Как это сделано в Java

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

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

Все операции — O(1) (амортизированно — из-за того самого редкого переезда в больший массив):

• как стек: push кладёт в голову, pop забирает оттуда же, peek смотрит;
• как очередь: offer добавляет в хвост, poll забирает из головы.

Один класс закрывает обе структуры — дек их обобщает. Разница видна на одних и тех же данных:

живой пример

import java.util.ArrayDeque;
import java.util.Deque;

class StackVsQueue {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        Deque<String> queue = new ArrayDeque<>();
        for (String task : new String[]{"первая", "вторая", "третья"}) {
            stack.push(task);
            queue.offer(task);
        }
        System.out.println("стек:    " + stack.pop() + ", " + stack.pop());
        System.out.println("очередь: " + queue.poll() + ", " + queue.poll());
    }
}

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

Класс, который обходят стороной, — Stack. Он появился в самой первой версии Java и унаследован от Vector, а значит, каждый его метод синхронизирован: за блокировки вы платите даже в одном потоке, где они не нужны. Хуже другое: Stack — это ещё и список, и перебирается он снизу вверх, от самого старого элемента к вершине, то есть в порядке, обратном тому, в котором стек отдаёт элементы через pop. Новый код на Stack не пишут — берут ArrayDeque.

Приоритетная очередь живёт отдельно: это PriorityQueue, построенная на куче.

Грабля у ArrayDeque одна, но о неё спотыкаются регулярно: null в него класть нельзя — прилетит NullPointerException. poll и peek возвращают null, когда дек пуст, и разреши мы хранить null внутри — этот ответ стал бы двусмысленным. LinkedList в роли дека null принимает, и там пустой дек и дек с null на конце различить уже нельзя.

Коротко

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

Что почитать дальше

• Связанные списки — ещё одна начинка для стека и очереди: вставка и удаление без сдвига элементов.
• Пирамиды (кучи) — как приоритетная очередь укладывается в O(log N) вместо O(N).
• Монотонный стек — приём, где стек за один проход находит ближайший больший элемент.
• Рекурсия — стек вызовов изнутри: что именно переполняется при глубокой рекурсии.