Java ArrayDeque

ArrayDeque<E> — это циклический массив, который растёт по мере необходимости. Он реализует оба интерфейса — Queue<E> и Deque<E>, — поэтому может выступать в роли очереди FIFO, стека LIFO или двусторонней очереди без каких-либо изменений кода. Javadoc класса Stack рекомендует использовать Deque вместо устаревшего класса; Javadoc класса Deque добавляет практическую рекомендацию, что ArrayDeque должен быть вашей реализацией по умолчанию. Он почти всегда быстрее LinkedList, занимает меньше памяти и является предпочтительным выбором стандартной библиотеки, когда интерфейс List не нужен.

Зачем нужен циклический массив

Классическая «очередь из массива» сталкивается с проблемой: после нескольких циклов добавления в хвост и удаления из головы массив заполняется с хвоста, тогда как с головы накапливаются пустые слоты. Наивное решение — сдвигать все элементы влево при каждом извлечении — даёт O(n) на каждое удаление, что катастрофически сказывается на производительности.

Трюк с циклическим массивом решает эту проблему. Класс хранит два индекса — head и tail — и позволяет им «оборачиваться»:

slots:   [ . . . D E F G H A B C ]
                         ^head     ^... wraps to slot 0 ... ^tail

addFirst уменьшает head, addLast увеличивает tail, оба по модулю длины массива. removeFirst и removeLast делают обратное. Каждая операция выполняется за O(1); единственная затрата — удвоение внутреннего массива при столкновении head с tail, которое амортизируется по времени.

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

Краткое напоминание об интерфейсе Deque

У Deque есть два конца. Каждая операция представлена тремя вариантами:

Кроме того, синонимы для Queue и стека отображаются на головной конец:

Таким образом, Deque — это один интерфейс, который одновременно предоставляет очередь и стек, в зависимости от того, как называть головной конец. Мы разбирали эти соответствия в главах про Queue и Stack; Deque — это место, где они встречаются.

Что добавляет ArrayDeque

На практике — совсем немного с точки зрения API, и это суть. Класс честно реализует контракт Deque: два конца, три стиля обработки ошибок на каждую операцию, а также clear(), iterator(), descendingIterator(), contains, size, isEmpty. Итерация со стандартным итератором идёт от головы к хвосту; descendingIterator — это дешёвый способ обойти деку от хвоста к голове без разворота.

Конструкторы повторяют ArrayList:

Deque<String> a = new ArrayDeque<>();          // initial capacity 16
Deque<String> b = new ArrayDeque<>(1_000);     // pre-sized
Deque<String> c = new ArrayDeque<>(other);     // from any Collection (head = first iter element)

Задавайте размер заранее, если знаете объём данных. Значение по умолчанию — 16 — округляется до степени двойки, а при расширении массив удваивается. То есть миллион вызовов offerLast с деком размером по умолчанию вызовет около 16 операций расширения и копирования.

Правила: без null, не потокобезопасен, fail-fast

Три правила, которые нужно запомнить:

1. ArrayDeque не допускает элементы null. Любая вставка выбрасывает NullPointerException. Именно поэтому возврат null из pollFirst() однозначно означает пустую деку.
2. Не потокобезопасен. Два потока, изменяющих один ArrayDeque, повредят его. Для конкурентного использования смотрите на ConcurrentLinkedDeque (неблокирующий, неограниченный) или LinkedBlockingDeque (ограниченный, блокирующий).
3. Итерация fail-fast. Изменение деки за пределами итератора во время обхода приводит к ConcurrentModificationException. Используйте Iterator.remove() или removeIf для безопасного изменения.

Когда выбирать ArrayDeque вместо альтернатив

Дерево решений:

• Нужна Queue? → ArrayDeque. По умолчанию.
• Нужен стек? → ArrayDeque. По умолчанию. Используйте push / pop / peek.
• Нужна Deque? → ArrayDeque. По умолчанию.
• Нужны и семантика Deque, и семантика List на одном объекте? → LinkedList. Редкий случай.
• Нужен порядок по приоритету? → PriorityQueue. Другая абстракция.
• Нужен конкурентный доступ? → ConcurrentLinkedDeque (неограниченный) или LinkedBlockingDeque (ограниченный). Правильный выбор зависит от того, нужно ли вам back-pressure.

Javadoc прямым текстом излагает рекомендацию: «Этот класс, вероятно, быстрее Stack при использовании в качестве стека и быстрее LinkedList при использовании в качестве очереди». Это слова непосредственно авторов JDK; стоит воспринимать их буквально.

Разбор примера: очередь, стек, дека, скользящее окно

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

Что можно вынести из этого примера:

• Секции 1 и 2 — это один и тот же класс, выполняющий две роли за счёт вызова разных методов. Очередь FIFO: offerLast / pollFirst. Стек LIFO: push / pop. Никакого отдельного класса изучать не нужно.
• descendingIterator() — это дешёвый обратный обход, полезный, когда вы построили деку как стек и хотите вывести её снизу вверх.
• Функция скользящего окна использует оба конца в одном цикле — pollFirst для удаления индексов, вышедших за пределы окна, pollLast для поддержания монотонно убывающего стека, peekFirst для считывания текущего максимума. Именно для такого двустороннего доступа существует ArrayDeque; попытка реализовать это через ArrayList давала бы квадратичную сложность.

Что дальше

Вы увидели, как ArrayDeque реализует оба конца истории об очередях и стеках. Интерфейс, который он реализует на протяжении всего этого времени, заслуживает отдельной главы — Deque — это контракт, объединяющий всё, что мы изучили по коллекциям, похожим на очередь. Рассмотрим его на следующем занятии.

Практика