Java Deque Interface | W3Docs Learn Java

Deque<E> — произносится «дек», сокращение от double-ended queue (двусторонняя очередь) — это Queue<E> с двумя концами. В отличие от Queue, которая позволяет извлекать элементы только с головы, Deque даёт возможность добавлять, удалять и просматривать элементы с обоих концов — как с головы, так и с хвоста. Этого единственного дополнения достаточно, чтобы Deque стал основой двух совершенно разных абстракций: он одновременно является очередью и стеком, и JDK рекомендует его в качестве реализации по умолчанию для обоих случаев.

Два конца × три операции × два стиля обработки ошибок

Интерфейс поначалу кажется громоздким, потому что каждая операция представлена в двенадцати вариантах — голова или хвост, вставка или удаление или просмотр, генерация исключения или возврат специального значения. Но это просто сетка Queue 3×2, растянутая на два конца:

Операция	Первый (голова) — исключение	Первый (голова) — спец. значение	Последний (хвост) — исключение	Последний (хвост) — спец. значение
Вставка	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Удаление	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Просмотр	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

Колонка «исключение» используется тогда, когда пустой или переполненный дек в данной точке является ошибкой. Колонка «спец. значение» — когда пустота является ожидаемым состоянием и вы хотите проверять её в условии цикла.

Отображение на очередь

Deque расширяет Queue, поэтому Deque является Queue. Унаследованные методы — это псевдонимы для вариантов с явным указанием конца:

Метод `Queue`	Эквивалент `Deque`
`add(e)` / `offer(e)`	`addLast(e)` / `offerLast(e)`
`remove()` / `poll()`	`removeFirst()` / `pollFirst()`
`element()` / `peek()`	`getFirst()` / `peekFirst()`

Вставка с хвоста, удаление с головы — это дисциплина FIFO, которую Queue уже обеспечивает, просто выраженная с именами, явно указывающими конец.

Отображение на стек

Deque также определяет три «стековых» метода, которые все работают с головой:

Метод стека	Эквивалент Deque
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()`
`peek()`	`peekFirst()`

Положить сверху, снять сверху — дисциплина LIFO, тот же конец (голова), но противоположный по отношению к вставке/удалению в отображении очереди. Именно поэтому глава о Stack направила вас сюда: современный способ написать стек в Java — Deque<E> stack = new ArrayDeque<>(); и вызывать push / pop / peek.

Правило: null не допускается

Как и Queue, контракт Deque резервирует null в качестве «пустого» сентинела для pollFirst, pollLast, peekFirst, peekLast. Поэтому каждый универсальный Deque в JDK отвергает элементы null с NullPointerException при вставке. Единственное исключение — LinkedList, который допускает null по историческим причинам — и наследует всю двусмысленность, связанную с этим. Не делайте так.

Прямая и обратная итерация

По соглашению Deque имеет два итератора:

iterator() обходит элементы от головы к хвосту — в порядке, в котором вы бы последовательно вызывали pollFirst.
descendingIterator() обходит элементы от хвоста к голове — в порядке, в котором вы бы последовательно вызывали pollLast.

Оба, как правило, являются fail-fast: изменение дека снаружи итератора во время обхода вызывает ConcurrentModificationException. Используйте Iterator.remove() или removeIf, если нужно изменять дек в ходе обхода.

Выбор реализации

В однопоточном коде есть фактически два варианта:

ArrayDeque — вариант по умолчанию. Кольцевой массив, O(1) на обоих концах, без выделения памяти для отдельных узлов, кеш-дружественный. Отвергает null. Реализует Deque и Queue.
LinkedList — узлы двусвязного списка. Также реализует List, поэтому каждый элемент получает узел с указателями prev/next. Медленнее на обоих концах, чем ArrayDeque, и использует больше памяти. Выбирайте его только если вам действительно нужна семантика и Deque, и List на одном объекте.

Для конкурентного кода (рассматривается позднее в разделе о конкурентности):

ConcurrentLinkedDeque — неблокирующий, неограниченный.
LinkedBlockingDeque — опционально ограниченный, блокирующий — вариант для построения очереди с похищением работ или модели производитель/потребитель с противодавлением на любом из концов.

Практический пример: очередь, стек и проверка палиндрома в одном деке

Программа ниже использует один ArrayDeque как FIFO-очередь, другой — как LIFO-стек, а третий — для проверки, является ли предложение палиндромом, сравнивая элементы с обоих концов. Суть в том, что один и тот же интерфейс, и даже один и тот же класс, выполняет все три роли.

java— editable, runs on the server

import java.util.*;

public class DequeShowcase {
  public static void main(String[] args) {
    // --- FIFO via Deque ---
    Deque<String> queue = new ArrayDeque<>();
    queue.offerLast("task-1");
    queue.offerLast("task-2");
    queue.offerLast("task-3");
    System.out.println("FIFO drain: " + queue.pollFirst() + ", "
        + queue.pollFirst() + ", " + queue.pollFirst());

// --- LIFO via Deque ---
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(1); stack.push(2); stack.push(3);
    System.out.println("LIFO drain: " + stack.pop() + ", "
        + stack.pop() + ", " + stack.pop());

// --- Empty: returns special value vs throws ---
    Deque<String> empty = new ArrayDeque<>();
    System.out.println("pollFirst on empty: " + empty.pollFirst());
    System.out.println("peekLast  on empty: " + empty.peekLast());
    try { empty.removeFirst(); }
    catch (NoSuchElementException e) {
      System.out.println("removeFirst threw " + e.getClass().getSimpleName());
    }

// --- Iteration: forward and reverse ---
    Deque<Integer> d = new ArrayDeque<>(List.of(10, 20, 30, 40));
    System.out.print("forward: ");
    d.iterator().forEachRemaining(x -> System.out.print(x + " "));
    System.out.println();
    System.out.print("reverse: ");
    d.descendingIterator().forEachRemaining(x -> System.out.print(x + " "));
    System.out.println();

// --- Palindrome check: pollFirst vs pollLast until they meet ---
    System.out.println("\npalindrome? 'racecar' -> " + isPalindrome("racecar"));
    System.out.println("palindrome? 'hello'   -> " + isPalindrome("hello"));
  }

static boolean isPalindrome(String s) {
    Deque<Character> dq = new ArrayDeque<>();
    for (char c : s.toCharArray()) dq.offerLast(c);
    while (dq.size() > 1) {
      if (!dq.pollFirst().equals(dq.pollLast())) return false;
    }
    return true;
  }
}

Что показывает этот запуск:

Один и тот же класс выполняет роли как очереди, так и стека, без переименования единственного метода — меняется только то, с какого конца вы обращаетесь.
Методы «возврата специального значения» тихо возвращают null для пустого дека; методы «генерации исключения» вызывают NoSuchElementException. Выбирайте в зависимости от того, является ли пустота ожидаемым состоянием или ошибкой.
Проверка палиндрома использует оба конца в одном цикле — pollFirst и pollLast вместе. Это паттерн доступа, который только Deque предоставляет эффективно.

Что дальше

Глава о Deque завершает рассмотрение очередной части фреймворка. Другая важная абстракция в Collection — та, что отвергает дубликаты: Set — это Collection со встроенным контрактом уникальности. Его мы рассмотрим следующим.

Практика

Вы хотите использовать LIFO-стек в современном Java-коде. Какая строка соответствует рекомендации JDK?

`Deque<String> stack = new ArrayDeque<>();` и затем вызывать `push` / `pop` / `peek``Stack<String> stack = new Stack<>();` — специализированный класс наиболее ясно выражает намерение`Queue<String> stack = new LinkedList<>();` и вызывать `add(0, ...)` для push`List<String> stack = new ArrayList<>();` и использовать `add` / `remove(size()-1)` — O(1) на конце