Класс ArrayDeque в Java - Вопросы

ArrayDeque (java.util, с Java 6) — реализация интерфейса Deque на кольцевом массиве с автоматическим ростом. Внутри лежат массив Object[] и два индекса: head (голова) и tail (хвост). Массив замкнут в кольцо: если addFirst() уводит индекс левее нуля, элемент записывается в последнюю ячейку. Поэтому добавление и удаление на обоих концах не сдвигает остальные элементы и выполняется за амортизированное O(1).

Deque<String> deque = new ArrayDeque<>();
deque.addLast("A");
deque.addLast("B");
deque.addLast("C");
deque.addFirst("Z");
System.out.println(deque); // [Z, A, B, C]

В этом отличие от ArrayList: список всегда начинает данные с индекса 0, поэтому add(0, e) и remove(0) сдвигают весь массив — O(n). Взамен у ArrayDeque нет доступа по индексу.

Конструкторов три:

• ArrayDeque() — пустая дека, в которую без расширения помещается 16 элементов;
• ArrayDeque(int numElements) — пустая дека с массивом под numElements элементов; отрицательное или нулевое значение исключения не вызывает: new ArrayDeque<>(-5) создаёт деку минимальной ёмкости (а new ArrayList<>(-5) бросит IllegalArgumentException);
• ArrayDeque(Collection<? extends E> c) — копия элементов c в порядке её итератора; null в c даёт NullPointerException.

Ёмкость — это размер внутреннего массива, а не ограничение: new ArrayDeque<>(100) спокойно примет 101-й элемент, массив будет пересоздан. Начальную ёмкость имеет смысл передавать, когда размер известен заранее, — это избавляет от лишних копирований. В Java 8 ёмкость округлялась до степени двойки и удваивалась; в современных JDK массив, пока он меньше 64 ячеек, растёт примерно вдвое, а дальше на 50%. В обратную сторону массив не уменьшается, trimToSize() нет; чтобы вернуть память после пика, создают копию: deque = new ArrayDeque<>(deque);. Жёсткий предел размера дают очереди из java.util.concurrent, например ArrayBlockingQueue.

Операции на концах — addFirst()/addLast(), offer*(), push(), poll*(), remove*(), pop(), peek*(), get*(), а также size() и isEmpty() — выполняются за O(1); добавление — амортизированное O(1), в момент роста массива O(n). Всё, что ищет элемент внутри, — contains(o), remove(o), removeFirstOccurrence(o), removeLastOccurrence(o), removeIf(), iterator().remove() — работает за O(n). clone() и toArray() копируют массив за O(n), но не сами элементы (поверхностная копия).

На пустой деке poll*() и peek*() возвращают null, а remove*(), pop(), get*() и element() бросают NoSuchElementException. offer*() всегда возвращают true: ограничения ёмкости нет. Методов с индексом (get(int), set(int, E)) у ArrayDeque нет; собственный публичный метод сверх интерфейсов только один — clone().

Пустые ячейки кольцевого массива отмечены значением null, а poll() и peek() возвращают null как сигнал «дека пуста», поэтому хранить null нельзя. Запрет действует только на запись: offer(null), push(null), addLast(null) и конструктор из коллекции с null бросают NullPointerException, а contains(null) и remove(null) просто возвращают false. Если null нужен — берут LinkedList.

ArrayDeque не переопределяет equals() и hashCode(), поэтому две деки с одинаковыми элементами не равны: сравниваются ссылки. По той же причине деку нельзя использовать как ключ HashMap или элемент HashSet в расчёте на сравнение по содержимому. Содержимое сравнивают через копии, порядок сохраняется от головы к хвосту:

Deque<Integer> a = new ArrayDeque<>(List.of(1, 2, 3));
Deque<Integer> b = new ArrayDeque<>(List.of(1, 2, 3));
System.out.println(a.equals(b));                                // false
System.out.println(List.copyOf(a).equals(List.copyOf(b)));      // true
System.out.println(Arrays.equals(a.toArray(), b.toArray()));    // true

Нет. Если два потока одновременно добавляют или удаляют элементы, индексы head и tail могут разойтись с содержимым массива, и элементы потеряются. Для очереди, общей между потоками, используют ConcurrentLinkedDeque или блокирующую LinkedBlockingDeque. Обёртки Collections.synchronizedDeque() не существует, а Collections.synchronizedCollection(deque) вернёт Collection без push() и pollFirst().

Итераторы ArrayDeque — fail-fast: если изменить деку во время обхода не через iterator.remove(), итератор, как правило, бросит ConcurrentModificationException. Это проверка «по возможности» (best-effort): исключение не гарантировано, строить на нём логику нельзя. Удалять элементы при обходе нужно через итератор или removeIf():

Deque<Integer> deque = new ArrayDeque<>(List.of(1, 2, 3, 4));
deque.removeIf(x -> x % 2 == 0);
System.out.println(deque); // [1, 3]

Документация Java говорит, что ArrayDeque, скорее всего, быстрее Stack в роли стека и быстрее LinkedList в роли очереди. У LinkedList операции на концах тоже O(1), но на каждое добавление создаётся объект-узел, узлы разбросаны по памяти и нагружают сборщик мусора; ArrayDeque пишет ссылку в готовую ячейку массива, соседние элементы лежат рядом и хорошо попадают в кэш процессора. Stack — наследник Vector: каждый метод synchronized, а get(i) нарушает принцип стека; он остался только в старом коде.

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

• нужно хранить null или нужен интерфейс List — LinkedList;
• нужен доступ по индексу — ArrayList;
• элементы извлекаются по приоритету — PriorityQueue;
• очередь общая для нескольких потоков — ConcurrentLinkedDeque, LinkedBlockingDeque;
• нужен жёсткий предел размера — ArrayBlockingQueue, LinkedBlockingDeque(capacity).