📦 Раздел 4 · Вопрос #10

Что такое Deque

Колода игральных карт в руках фокусника: карту можно снять как сверху колоды, так и вытащить снизу; положить карту можно как наверх, так и под низ.

📦 Коллекции 📄 Исходный Markdown

🟢 Junior Level

Deque (Double-Ended Queue — двусторонняя очередь, произносится как «дек») — это интерфейс Java Collections Framework, позволяющий добавлять, просматривать и извлекать элементы с обоих концов структуры: как из начала (головы), так и из конца (хвоста).

Аналогия из реального мира

Колода игральных карт в руках фокусника: карту можно снять как сверху колоды, так и вытащить снизу; положить карту можно как наверх, так и под низ.

Deque объединяет в себе Стек и Очередь

Интерфейс Deque является универсальной структурой данных:

  • Как очередь (FIFO): элементы добавляются в конец (offerLast), а извлекаются из начала (pollFirst).
  • Как стек (LIFO): элементы кладутся наверх (push / addFirst) и снимаются сверху (pop / removeFirst).
Deque<String> deque = new ArrayDeque<>();

// 1. Использование как очереди FIFO:
deque.offer("Первый");
deque.offer("Второй");
System.out.println(deque.poll()); // "Первый"

// 2. Использование как стека LIFO:
deque.push("Нижний");
deque.push("Верхний");
System.out.println(deque.pop());  // "Верхний"

🟡 Middle Level

1. Таблица методов Deque: Голова против Хвоста

Каждая операция с обоими концами очереди представлена в двух вариантах: выбрасывающем исключение и возвращающем специальное значение (false или null):

Операция В начале (Голова) — Exception В начале (Голова) — Special Value В конце (Хвост) — Exception В конце (Хвост) — Special Value
Вставка addFirst(e) offerFirst(e) addLast(e) offerLast(e)
Удаление removeFirst() pollFirst() removeLast() pollLast()
Просмотр getFirst() peekFirst() getLast() peekLast()

2. Почему ArrayDeque — лучшая реализация Deque?

В стандартной библиотеке Java интерфейс Deque реализуют два основных класса: ArrayDeque и LinkedList.

Критерий ArrayDeque LinkedList
Базовая структура данных Кольцевой циклический массив (Object[]) Двусвязный список узлов (Node)
Сложность операций с концами $O(1)$ амортизированное $O(1)$
Локализация в кэше CPU Превосходная (данные лежат в непрерывном блоке) Ужасная (постоянные кэш-промахи)
Расход памяти Минимальный (~4–8 байт на элемент) Высокий (~24–32 байта на элемент)
Нагрузка на Garbage Collector Нулевая при работе (только при редком ресайзе) Создание и удаление Node на каждый элемент
Поддержка null ❌ Запрещен (NullPointerException) ✅ Разрешен

[!TIP] Согласно бенчмаркам JMH, ArrayDeque превосходит LinkedList при итерации в 3–10 раз и при операциях вставки/удаления в 2–5 раз. В современном коде для реализации очередей и стеков всегда выбирайте ArrayDeque.

🔴 Senior Level

1. Архитектура кольцевого буфера на битовых масках

В классе ArrayDeque размер внутреннего массива elements всегда строго равен степени двойки ($2^k$: 16, 32, 64, 128…).

Это позволяет исключить дорогую операцию целочисленного деления по модулю (% elements.length), заменив её поразрядным логическим И (&):

// Исходный код java.util.ArrayDeque:
public void addFirst(E e) {
    if (e == null) throw new NullPointerException();
    // Движение головы против часовой стрелки (влево):
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity(); // Массив полон -> ресайз в 2 раза
}

public void addLast(E e) {
    if (e == null) throw new NullPointerException();
    elements[tail] = e;
    // Движение хвоста по часовой стрелке (вправо):
    if ((tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

Пример для длины массива 8 (в двоичном виде: length = 1000₂, mask = 0111₂):
- Пусть head = 0. Выполняем (0 - 1) & 7:
  -1 в дополнительном коде = ...11111111₂
  ...11111111₂ & 00000111₂ = 00000111₂ = 7!
  Указатель мгновенно закольцевался на последний индекс массива за 1 такт CPU!

2. Алгоритм кражи работы (Work Stealing) и BlockingDeque

В многопоточных высокопроизводительных фреймворках (включая ForkJoinPool из java.util.concurrent) двусторонние очереди являются базой для алгоритма Work Stealing:

Поток Worker 1: [Локальный Deque]
  ├── Владелец работает с головой (LIFO): push() / pop() (кэш горячий)
  │
Поток Worker 2 (простаивающий «вор»):
  └── Крадет задачу с противоположного конца (хвоста FIFO): pollLast()!
  • Владелец очереди кладет и забирает подзадачи с головы стека (push / pop), обеспечивая максимальную локализацию данных в процессорном кэше.
  • Если у другого потока закончились задачи, он не простаивает, а «крадет» задачу из хвоста чужой очереди (pollLast).
  • Поскольку владелец и «вор» работают с противоположными концами очереди, состязание за блокировки (Lock Contention) сведено к абсолютному минимуму.

3. Интеграция с Java 21 SequencedCollection (JEP 431)

Начиная с Java 21, интерфейс Deque стал прямым наследником SequencedCollection:

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A");
deque.addLast("Z");

// Новые стандартизированные методы:
String first = deque.getFirst(); // "A"
String last = deque.getLast();   // "Z"

// Получение реверсивного представления за O(1) без копирования массива:
SequencedCollection<String> reversedView = deque.reversed();

🎯 Шпаргалка для интервью

30-секундный ответ для собеседования

«Deque (Double-Ended Queue) — это двусторонняя очередь, позволяющая вставлять и удалять элементы с обоих концов за константное время $O(1)$. Она объединяет функциональность стека (LIFO) и очереди (FIFO). Лучшей реализацией является ArrayDeque, работающий на непрерывном кольцевом массиве с емкостью степени двойки, где перемещение указателей рассчитывается быстрой битовой маской (i + 1) & (length - 1). ArrayDeque превосходит LinkedList по скорости и памяти в разы, а также полностью вытеснил устаревший класс Stack. В многопоточности двусторонние очереди (BlockingDeque) лежат в основе алгоритма Work Stealing в ForkJoinPool».

Вопросы повышенной сложности с ответами

  1. Почему ArrayDeque строго запрещает сохранение элементов null, тогда как LinkedList их разрешает? Ответ: Это осознанное архитектурное решение. Методы pollFirst(), pollLast(), peekFirst() и peekLast() возвращают null в качестве служебного сигнала о том, что очередь пуста. Если бы null был разрешенным элементом, невозможно было бы однозначно отличить ситуацию, когда очередь пуста, от ситуации, когда из нее был успешно извлечен элемент со значением null.

  2. Как в ArrayDeque реализовано циклическое зацикливание указателей без операции деления по модулю? Ответ: Размер внутреннего массива elements принудительно поддерживается равным степени двойки ($2^k$). В математике операция взятия остатка от деления $X \pmod{2^k}$ эквивалентна побитовой операции X & (2^k - 1). Вместо тяжелой машинной инструкции деления idiv (занимающей 10–20 тактов CPU) ArrayDeque выполняет инструкцию and, которая выполняется за 1 такт процессора.

  3. Что такое Work Stealing в ForkJoinPool и почему для него необходим интерфейс Deque? Ответ: Work Stealing — это алгоритм балансировки многопоточной нагрузки. У каждого рабочего потока есть собственный двусторонний дек задач. Сам поток-владелец помещает и забирает задачи с одного конца (головы) по принципу стека LIFO, что дает отличную кэш-локальность. Если другой поток освободился, он пытается украсть задачу у перегруженного соседа с противоположного конца (хвоста) по принципу FIFO. Разнесение операций владельца и вора по разным концам Deque минимизирует конкуренцию за замки.

  4. Чем deque.pop() отличается от deque.poll()? Ответ: Оба метода извлекают и удаляют элемент с головы очереди (вершины стека). Различие заключается в реакции на пустую коллекцию: если Deque пуст, pop() выбрасывает NoSuchElementException, тогда как poll() безопасно возвращает null.

Типичные ошибки и Red Flags

  • ❌ Использовать LinkedList для реализации двусторонней очереди или стека. (Red Flag: непонимание избыточных накладных расходов памяти и кэш-промахов связных узлов).
  • ❌ Пытаться положить null в ArrayDeque. (Приводит к немедленному NullPointerException).
  • ❌ Считать ArrayDeque потокобезопасным классом. (Для многопоточности нужен ConcurrentLinkedDeque или LinkedBlockingDeque).

Связанные темы