Интерфейсы Queue и Deque в Java

Положите в очередь LinkedList строки "A", null, "B" и обработайте её привычным циклом while ((s = queue.poll()) != null) — программа выведет только A и молча оставит "B" в очереди. poll() возвращает null и для пустой очереди, и для элемента null, поэтому разница между методами очереди — не формальность.

Queue (в переводе с английского «очередь») — интерфейс java.util.Queue, который описывает очередь: элементы добавляются в хвост (tail) и извлекаются из головы (head), обычно по принципу «первым пришёл — первым ушёл» (FIFO). Deque (double-ended queue, произносится «дек») — интерфейс java.util.Deque, двусторонняя очередь: она расширяет Queue и позволяет добавлять и удалять элементы с обоих концов, поэтому работает и как очередь FIFO, и как стек LIFO.

Интерфейс Queue в Java

Интерфейс Queue<E> появился в Java 5, расширяет Collection и задаёт три операции очереди: добавить в хвост, извлечь из головы и посмотреть голову без удаления. Каждая операция есть в двух вариантах: один бросает исключение, если операция невозможна, другой возвращает специальное значение — false или null.

Большинство очередей работают по FIFO, но интерфейс этого не требует: например, PriorityQueue отдаёт первым не самый ранний, а наименьший элемент. Сама структура данных «очередь» без привязки к Java описана в уроке Структуры данных.

Подробно по каждому методу:

Не путайте remove() без параметров с унаследованным от Collection методом remove(Object o): первый извлекает голову очереди, второй ищет и удаляет конкретный элемент в любом месте. Количество элементов возвращает size(), проверку на пустоту делает isEmpty().

Пример: методы offer(), peek(), poll() и remove()

import java.util.ArrayDeque;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayDeque<>();
        queue.offer("Харьков");
        queue.offer("Киев");
        queue.offer("Кременчуг");
        queue.offer("Львов");

        System.out.println("Голова: " + queue.peek());
        System.out.println("Размер: " + queue.size());

        String town;
        while ((town = queue.poll()) != null) {
            System.out.println(town);
        }

        System.out.println("poll() пустой очереди: " + queue.poll());
        queue.remove();
    }
}

Вывод:

Голова: Харьков
Размер: 4
Харьков
Киев
Кременчуг
Львов
poll() пустой очереди: null
Exception in thread "main" java.util.NoSuchElementException

Элементы выходят в том же порядке, в каком были добавлены. peek() голову не удаляет, поэтому size() после него по-прежнему 4. На пустой очереди poll() спокойно возвращает null, а remove() завершает программу исключением. Цикл с poll() != null здесь безопасен: ArrayDeque не хранит null, так что null означает только одно — очередь пуста.

Queue и null: когда poll() вводит в заблуждение

Большинство реализаций Queue не допускают null: ArrayDeque, PriorityQueue и очереди из java.util.concurrent бросают NullPointerException при offer(null). Причина в том, что poll() и peek() используют null как сигнал «очередь пуста». Исключение — LinkedList: он принимает null, и тогда этот сигнал становится двусмысленным.

Что выведет этот код?

import java.util.LinkedList;
import java.util.Queue;

public class QueueNullExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("A");
        queue.offer(null);
        queue.offer("B");

        String s;
        while ((s = queue.poll()) != null) {
            System.out.println(s);
        }
        System.out.println("Осталось в очереди: " + queue.size());
    }
}

Вывод:

A
Осталось в очереди: 1

Второй вызов poll() удалил элемент null и вернул его — цикл решил, что очередь закончилась, и "B" остался необработанным. Если в очереди могут быть null, проверяйте пустоту явно:

while (!queue.isEmpty()) {
    System.out.println(queue.poll()); // Вывод: A, null, B — каждый с новой строки
}

Надёжнее вовсе не класть null в очереди. Если заменить LinkedList на ArrayDeque, ошибка проявится сразу: строка queue.offer(null) бросит NullPointerException.

Интерфейс Deque в Java

Интерфейс Deque<E> появился в Java 6 и расширяет Queue: у двусторонней очереди есть голова (first) и хвост (last), и каждую операцию можно выполнить с любого конца. Методы называются по схеме «операция + First/Last» и, как в Queue, существуют в двух вариантах — с исключением и со специальным значением.

Кроме того, Deque умеет обходить элементы с хвоста: descendingIterator(). С Java 21 Deque расширяет SequencedCollection и получил метод reversed() — представление очереди в обратном порядке (подробнее об этих интерфейсах — в уроке Коллекции в Java). Методы getFirst(), removeFirst() и их пары у Deque были и раньше, начиная с Java 6.

Deque как стек: push, pop, peek

Чтобы использовать Deque как стек, работают только с головой: push() кладёт элемент на вершину, pop() снимает его, peek() показывает вершину без удаления. Чтобы использовать Deque как очередь FIFO, добавляют в хвост (offer()) и забирают из головы (poll()). Все эти методы — синонимы методов с First/Last.

Поскольку и очередь, и стек забирают элементы из головы, их можно смешивать в одном объекте. Что выведет этот код?

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(1);   // в хвост
        deque.offer(2);   // в хвост
        deque.push(0);    // в голову

        System.out.println(deque);            // [0, 1, 2]
        System.out.println(deque.pop());      // 0 — из головы
        System.out.println(deque.pollLast()); // 2 — из хвоста
        System.out.println(deque.peek());     // 1 — голова, без удаления

        deque.clear();
        System.out.println(deque.peek());     // null
        deque.pop();                          // NoSuchElementException
    }
}

Вывод:

[0, 1, 2]
0
2
1
null
Exception in thread "main" java.util.NoSuchElementException

push(0) поставил ноль перед уже добавленными через offer() элементами, потому что вершина стека и голова очереди — один и тот же конец. На пустом деке peek() возвращает null, а pop() бросает исключение, как removeFirst(). Готовые классы для стека, конструкторы и устройство кольцевого массива разобраны в уроке ArrayDeque, а почему вместо старого класса Stack берут Deque — в уроке Legacy Classes.

Queue vs Deque: в чём разница

Queue — очередь с одним входом и одним выходом: добавление в хвост, извлечение из головы. Deque — её расширение, двусторонняя очередь, в которой добавлять, извлекать и просматривать элементы можно с обоих концов. Любой Deque является Queue, но не наоборот: PriorityQueue реализует только Queue.

Практическое правило: объявляйте переменную типом Queue, если коду нужна только очередь, и Deque, если нужен стек или доступ к обоим концам. Узкий тип не даст случайно вызвать pollLast() там, где по смыслу допустим только FIFO.

Реализации Queue и Deque

Для обычной очереди или стека в однопоточном коде выбирают ArrayDeque; LinkedList нужен, когда та же коллекция должна быть и списком; PriorityQueue — когда элементы извлекаются по приоритету. Очереди фиксированного размера и потокобезопасные очереди находятся в пакете java.util.concurrent.

Именно в очередях ограниченной ёмкости проявляется разница между add() и offer() (и между addFirst() и offerFirst() у Deque). Пример очереди фиксированного размера:

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class FixedSizeQueue {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayBlockingQueue<>(2);
        System.out.println(queue.offer("A")); // true
        System.out.println(queue.offer("B")); // true
        System.out.println(queue.offer("C")); // false — места нет
        queue.add("C");                       // IllegalStateException
    }
}

Вывод:

true
true
false
Exception in thread "main" java.lang.IllegalStateException: Queue full

У ArrayDeque, LinkedList и PriorityQueue ёмкость не ограничена, поэтому offer() у них всегда возвращает true, а add() никогда не бросает IllegalStateException.