Что такое 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]]