Що таке Deque

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

🟢 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(); // Масив переповнений -> ресайз удвічі
}

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».

Питання підвищеної складності з відповідями

Чому ArrayDeque суворо забороняє збереження елементів null, тоді як LinkedList їх дозволяє? Відповідь: Це усвідомлене архітектурне рішення. Методи pollFirst(), pollLast(), peekFirst() та peekLast() повертають null як службовий сигнал про те, що черга наразі порожня. Якби null був дозволеним елементом, було б неможливо однозначно розрізнити ситуацію, коли черга порожня, від ситуації, коли з неї було успішно вилучено елемент зі значенням null.
Як в ArrayDeque реалізовано зациклення покажчиків без операції ділення за модулем? Відповідь: Розмір внутрішнього масиву elements примусово підтримується рівним степеню двійки ($2^k$). У двійковій арифметиці операція взяття остачі від ділення $X \pmod{2^k}$ еквівалентна побітовій операції X & (2^k - 1). Замість важкої машинної інструкції ділення idiv (яка займає 10–20 тактів CPU) ArrayDeque виконує інструкцію and, яка відпрацьовує за 1 машинний такт процесора.
Що таке Work Stealing у ForkJoinPool і чому для нього необхідний інтерфейс Deque? Відповідь: Work Stealing — це алгоритм балансування багатопотокового навантаження. Кожен робочий потік володіє власним двостороннім деком завдань. Сам потік-власник додає та вилучає завдання з одного кінця (голови) за принципом стека LIFO, що забезпечує відмінну кеш-локальність. Якщо інший потік звільнився, він намагається вкрасти завдання в перевантаженого сусіда з протилежного кінця (хвоста) за принципом FIFO. Рознесення дій власника та злодія за різними кінцями Deque зводить конкуренцію за блокування до мінімуму.
Чим deque.pop() відрізняється від deque.poll()? Відповідь: Обидва методи вилучають і видаляють елемент із голови черги (вершини стека). Різниця полягає в реакції на порожню колекцію: якщо Deque порожній, pop() викидає виняток NoSuchElementException, тоді як poll() безпечно повертає null.

Типові помилки та Red Flags

❌ Використовувати LinkedList для реалізації двосторонньої черги або стека. (Red Flag: нерозуміння надлишкових витрат пам’яті та промахів кешу зв’язних вузлів).
❌ Намагатися покласти null в ArrayDeque. (Призводить до негайного викидання NullPointerException).
❌ Вважати ArrayDeque потокобезпечним класом. (Для багатопотоковості потрібен ConcurrentLinkedDeque або LinkedBlockingDeque).