Що таке Deque?

🟢 Junior Level

Deque (Double-Ended Queue) — черга, де можна додавати та видаляти елементи з обох кінців.

Аналогія: Колода карт — можна брати карту зверху або знизу, можна класти зверху або знизу.

Проста аналогія: Двостороння черга у парку розваг — можна заходити та виходити з обох кінців.

Deque = Stack + Queue:

Deque<String> deque = new ArrayDeque<>();

// Як стек (LIFO):
deque.push("A");     // Зверху
deque.pop();         // Зняти зверху

// Як черга (FIFO):
deque.offer("A");    // В кінець
deque.poll();        // З початку

// З обох кінців:
deque.addFirst("A"); // На початок
deque.addLast("B");  // В кінець
deque.removeFirst(); // Видалити початок
deque.removeLast();  // Видалити кінець

🟡 Middle Level

ArrayDeque: найкраща реалізація

// Кільцевий масив (Circular Buffer)
Deque<String> deque = new ArrayDeque<>();

// Операції: O(1) amortized
deque.addFirst("A");   // O(1)
deque.addLast("B");    // O(1)
deque.removeFirst();   // O(1)
deque.removeLast();    // O(1)
deque.peekFirst();     // O(1)
deque.peekLast();      // O(1)

Чому ArrayDeque кращий за LinkedList

	ArrayDeque	LinkedList
Пам’ять	Масив (мало)	Node об’єкти (багато)
Кеш-локальність	Відмінна	Жахлива
Алокації	При ресайзі	На кожну вставку
GC pressure	Низький	Високий
Швидкість	За даними JMH-бенчмарків: ArrayDeque у 3-10 разів швидший за LinkedList при ітерації та у 2-5 разів швидший при вставці/видаленні.

Deque як Stack

// ❌ Не використовуйте Stack
Stack<String> stack = new Stack<>();

// ✅ Використовуйте Deque
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.pop();
stack.peek();

Java 21: SequencedCollection

// Java 21 доступна не скрізь. Для Java 11/17 використовуйте deque.peekFirst() замість getFirst() та deque.peekLast() замість getLast().

// Deque тепер SequencedCollection
deque.getFirst();    // Новий метод!
deque.getLast();     // Новий метод!
deque.reversed();    // Зворотний порядок (view)

// Гарантований порядок обходу
for (String s : deque) { ... }  // Від першого до останнього
for (String s : deque.reversed()) { ... }  // Навпаки

🔴 Senior Level

Кільцевий буфер (Circular Array)

Масив: [A][B][C][ ][ ][ ][ ][ ]
         ↑head        ↑tail

addLast(D):
[A][B][C][D][ ][ ][ ][ ]
         ↑head     ↑tail

removeFirst():
[ ][B][C][D][ ][ ][ ][ ]
    ↑head     ↑tail

tail дійшов до кінця → загортає:
[ ][B][C][D][E][F][ ][ ]
    ↑head              ↑tail

Індекс: (tail + 1) & (length - 1)  // Бітове І!

Бітові маски замість ділення

// Звичайний cyclic index:
index = (index + 1) % capacity;  // Ділення — повільно!

// ArrayDeque (capacity = степінь 2):
index = (index + 1) & (elements.length - 1);  // AND — швидко!

// Приклад: capacity = 8 (1000 у бінарному)
// (7 + 1) & 7 = 8 & 7 = 0  ← Загорнули!

// Чому степінь 2?
// 8 = 1000, 7 = 0111
// x & 7 = x % 8  (для x < 16)
// → Одна CPU інструкція замість ділення!

Trade-off: степінь 2 означає що масив може бути заповнений лише на 50-75% перед ресайзом (щоб відрізнити «повен» від «порожній»). Це трохи більше wasted memory, але економія на діленні того варта.

Чому ArrayDeque забороняє null?

deque.offer(null);  // → NullPointerException!

// Чому?
// poll() та peek() повертають null для порожньої deque
// Якщо null валідний елемент → не можна відрізнити!

// Це architectural decision, не баг!

Concurrency

// ArrayDeque НЕ thread-safe!

// Lock-free Deque:
Deque<String> deque = new ConcurrentLinkedDeque<>();

// Blocking Deque (Work Stealing):
BlockingDeque<String> deque = new LinkedBlockingDeque<>();
// → Потоки можуть "красти" задачі з хвоста
// → ForkJoinPool використовує це!

// **Work Stealing** — алгоритм балансування навантаження: коли потік завершив свою чергу задач, він «краде» задачі з хвоста черги іншого потоку. Це запобігає ситуації, коли один потік перевантажений, а інший простоює. Використовується у ForkJoinPool.

Production Experience

Реальний сценарій: LinkedList → ArrayDeque

Message queue: LinkedList
GC кожні 2 секунди (Node алокації)
Рішення: ArrayDeque
Результат: GC раз на хвилину, +50% throughput

Best Practices

ArrayDeque — для стеків та черг
Забороняє null — архітектурне обмеження
Степінь 2 → бітові маски замість ділення
Java 21 → getFirst(), getLast(), reversed()
ConcurrentLinkedDeque — lock-free
LinkedBlockingDeque — Work Stealing
НЕ використовуйте Stack або LinkedList

Резюме для Senior

Deque = двостороння черга (LIFO + FIFO)
ArrayDeque = кільцевий масив, capacity = 2^n
Бітові маски → (index + 1) & (length - 1)
null заборонений → poll/peek однозначні
Кеш-локальність » LinkedList
SequencedCollection (Java 21) → getFirst/reversed
Work Stealing → LinkedBlockingDeque
Ніколи не використовуйте Stack

🎯 Шпаргалка для інтерв’ю

Обов’язково знати:

Deque (Double-Ended Queue) = двостороння черга, підтримка LIFO + FIFO
ArrayDeque — найкраща реалізація: кільцевий масив, O(1) amortized для всіх операцій з обох кінців
ArrayDeque кращий за LinkedList: у 3-10 разів швидший при ітерації, у 2-5 разів при вставці/видаленні, менше GC pressure
Кільцевий буфер: capacity = степінь 2 → бітові маски замість ділення ((index + 1) & (length - 1))
ArrayDeque забороняє null — архітектурне рішення (poll/peek повертають null для порожньої deque)
Java 21: SequencedCollection → getFirst(), getLast(), reversed() для Deque
Concurrency: ConcurrentLinkedDeque (lock-free), LinkedBlockingDeque (Work Stealing, ForkJoinPool)
ArrayDeque замінює Stack: push/pop/peek — ті ж методи, без synchronized та LSP violation

Часті уточнюючі запитання:

Чому ArrayDeque використовує capacity = степінь 2? — Для бітових масок: (index + 1) & (length - 1) замість повільного ділення %
Чому ArrayDeque забороняє null? — poll()/peek() повертають null для порожньої deque, null елемент створив би двозначність
Що таке Work Stealing? — Потоки «крадуть» задачі з хвоста чужої черги, балансування навантаження у ForkJoinPool
Чим Deque відрізняється від Queue? — Deque підтримує операції з обох кінців, Queue — тільки з одного (FIFO)

Червоні прапорці (НЕ говорити):

❌ “LinkedList — гарна реалізація Deque” — ArrayDeque завжди кращий (кеш-локальність, менше пам’яті)
❌ “ArrayDeque можна використовувати як Map ключ” — Deque не має hashCode/equals контракту для ключів
❌ “Deque може містити null” — ArrayDeque забороняє null, це architectural decision
❌ “Використовуйте Stack як стек” — ArrayDeque замінює Stack без synchronized оверхеду та LSP violation

Пов’язані теми:

[[Що таке Queue і які реалізації існують]]
[[Що таке Stack]]
[[В чому різниця між ArrayList та LinkedList]]
[[Які основні інтерфейси Collection Framework]]
[[Що таке Vector і чим він відрізняється від ArrayList]]