Класс ArrayDeque в Java

Сравните две очереди с одинаковыми элементами: new ArrayDeque<>(List.of(1, 2, 3)).equals(new ArrayDeque<>(List.of(1, 2, 3))) вернёт false. ArrayDeque не переопределяет equals(), поэтому сравнивает ссылки, а не содержимое — на этом падают unit-тесты и поиск деки в HashSet. Это одна из особенностей реализации, о которых ничего не говорит интерфейс Deque.

ArrayDeque (java.util.ArrayDeque, array deque — «двусторонняя очередь на массиве») — класс из Java 6, который реализует интерфейс Deque на кольцевом массиве с автоматическим ростом. Добавление и удаление на обоих концах выполняется за амортизированное O(1), поэтому ArrayDeque — стандартный выбор для стека и очереди FIFO в однопоточном коде. Элементы null запрещены, класс не потокобезопасен.

Методы интерфейсов Queue и Deque — offer(), poll(), peek(), push(), pop() и их варианты с First/Last — разобраны в уроке Интерфейсы Queue и Deque. Здесь речь о том, как они работают именно в ArrayDeque.

Как устроен ArrayDeque: кольцевой массив

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

Так выглядит условный массив из 8 ячеек после вызовов addLast("A"), addLast("B"), addLast("C") и addFirst("Z"):

индекс:   0     1     2     3     4     5     6     7
        [ A ] [ B ] [ C ] [   ] [   ] [   ] [   ] [ Z ]
                          ^ tail                  ^ head

addFirst() сдвинул head с 0 на 7, «обернувшись» через конец массива, а addLast() пишет в ячейку tail и сдвигает его вправо. Логический порядок элементов — от head по кругу до tail:

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

public class RingBufferDemo {
    public static void main(String[] args) {
        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]
        System.out.println(deque.peekFirst() + " " + deque.peekLast()); // Z C
    }
}

Вывод:

[Z, A, B, C]
Z C

Когда массив заполняется, ArrayDeque создаёт новый массив побольше и копирует в него элементы — это O(n), но происходит редко, поэтому в среднем добавление остаётся O(1). Именно этим ArrayDeque отличается от ArrayList: тот всегда начинает данные с индекса 0, и remove(0) сдвигает весь массив.

Конструкторы и ёмкость ArrayDeque

У ArrayDeque три конструктора: пустой с начальной ёмкостью 16 элементов, с заданной начальной ёмкостью и копирующий элементы другой коллекции. Ёмкость — это размер внутреннего массива, а не ограничение: при заполнении дека растёт автоматически.

Как именно растёт массив, зависит от версии JDK. В Java 8 ёмкость всегда округлялась до степени двойки (минимум 8) и при заполнении удваивалась. В JDK 17 и 21 конструктор выделяет место ровно под numElements элементов, а при росте массив удваивается, пока он меньше 64 ячеек, и дальше увеличивается на 50%. В обратную сторону массив не уменьшается: после удаления элементов память под ячейки остаётся занятой.

Пример ArrayDeque: очередь и стек

Один и тот же класс ArrayDeque работает и как стек LIFO, и как очередь FIFO — всё зависит от вызываемых методов: push()/pop() работают с головой, add()/remove() добавляют в хвост и забирают из головы. Переменную объявляют типом интерфейса Deque или Queue.

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        Deque<String> queue = new ArrayDeque<>(2);
        stack.push("A");
        stack.push("B");
        stack.push("C");
        stack.push("D");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();

        queue.add("A");
        queue.add("B");
        queue.add("C");
        queue.add("D");
        while (!queue.isEmpty()) {
            System.out.print(queue.remove() + " ");
        }
    }
}

Вывод:

D C B A
A B C D

Стек вернул элементы в обратном порядке: последний добавленный "D" вышел первым. Очередь сохранила порядок добавления. Обратите внимание: queue создана с начальной ёмкостью 2, но без ошибок приняла четыре элемента — массив вырос сам.

ArrayDeque как стек: проверка парности скобок

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

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

public class BracketChecker {
    static boolean isBalanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;          // закрывающая скобка без пары
                }
                char open = stack.pop();
                if ((c == ')' && open != '(')
                        || (c == ']' && open != '[')
                        || (c == '}' && open != '{')) {
                    return false;          // скобки разных видов
                }
            }
        }
        return stack.isEmpty();            // остались незакрытые скобки?
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("list.get(map[key])"));
        System.out.println(isBalanced("{[}]"));
        System.out.println(isBalanced("(("));
        System.out.println(isBalanced(")("));
    }
}

Вывод:

true
false
false
false

Проверка stack.isEmpty() перед pop() обязательна: для строки ")(" без неё pop() на пустом стеке бросил бы NoSuchElementException. Как очередь ArrayDeque используют, например, в обходе дерева или графа в ширину: offer() в хвост, poll() из головы.

Методы ArrayDeque и их сложность

ArrayDeque реализует все методы Deque, Queue и Collection; собственный публичный метод сверх интерфейсов у него один — clone(). Операции на концах выполняются за O(1), а всё, что требует поиска элемента внутри, — за O(n). Методов с индексом (get(int), set(int, E)) нет.

Что делает каждый метод и чем отличаются пары offer/add и poll/remove, показано в таблицах урока Интерфейс Deque в Java.

null, contains() и equals(): неочевидные моменты

ArrayDeque не хранит null, потому что пустые ячейки кольцевого массива как раз и отмечены значением null, а poll() и peek() возвращают null как сигнал «дека пуста». Кроме того, класс не переопределяет equals() и hashCode(), поэтому сравнивает деки по ссылке.

Запрет действует только на запись: offer(null), push(null) и addLast(null) бросают NullPointerException, а contains(null) и remove(null) спокойно возвращают false. Почему null в очереди опасен и как на нём ломается цикл с poll(), разобрано в разделе Queue и null.

Что выведет этот код?

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class DequeEquals {
    public static void main(String[] args) {
        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));
        System.out.println(List.copyOf(a).equals(List.copyOf(b)));
        System.out.println(Arrays.equals(a.toArray(), b.toArray()));
        System.out.println(new LinkedList<>(a).equals(new LinkedList<>(b)));
    }
}

Вывод:

false
true
true
true

ArrayDeque наследует equals() от Object, поэтому a.equals(b) истинно только для одного и того же объекта. Чтобы сравнить содержимое, деки превращают в списки или массивы — порядок при этом сохраняется от головы к хвосту. По той же причине ArrayDeque нельзя использовать как ключ HashMap или элемент HashSet в расчёте на сравнение по содержимому. У LinkedList такой проблемы нет: он реализует List и сравнивает элементы.

Потокобезопасность и fail-fast итераторы

ArrayDeque не потокобезопасен: если два потока одновременно добавляют или удаляют элементы, индексы head и tail могут разойтись с содержимым массива, и элементы потеряются. Для общей очереди между потоками используют ConcurrentLinkedDeque или блокирующую LinkedBlockingDeque.

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

ArrayDeque vs LinkedList vs Stack

Для стека и очереди в однопоточном коде лучше всего подходит ArrayDeque: документация Java прямо говорит, что он, скорее всего, быстрее Stack в роли стека и быстрее LinkedList в роли очереди. LinkedList выбирают, когда нужны null или интерфейс List, а Stack остался только в старом коде.

Разница в скорости между ArrayDeque и LinkedList при одинаковой оценке O(1) объясняется памятью: элементы массива лежат рядом и хорошо попадают в кэш процессора, а LinkedList выделяет отдельный объект на каждый элемент и нагружает сборщик мусора. Устройство узлов разобрано в уроке LinkedList, история класса Stack — в уроке Legacy Classes.

Когда использовать ArrayDeque

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