Интерфейсы Queue и Deque в Java - Java программирование Вопросы - 6 вопросов

1.

Чем интерфейс Queue отличается от Deque в Java?

Queue (Java 5, расширяет Collection) — очередь с одним входом и одним выходом: элементы добавляются в хвост (tail) и извлекаются из головы (head), обычно по принципу FIFO «первым пришёл — первым ушёл». Интерфейс FIFO не требует: PriorityQueue отдаёт первым наименьший элемент.

Deque (double-ended queue, «дек», Java 6) расширяет Queue: добавлять, извлекать и просматривать элементы можно с обоих концов (методы offerFirst/Last(), pollFirst/Last(), peekFirst/Last(), descendingIterator()), поэтому один объект работает и как очередь FIFO, и как стек LIFO (push(), pop(), peek()).

Любой Deque является Queue, но не наоборот: PriorityQueue реализует только Queue. Практическое правило: объявляйте переменную типом Queue, если нужна только очередь, и Deque, если нужен стек или доступ к обоим концам.

2.

Какие методы есть у Queue и чем add/offer, remove/poll, element/peek отличаются друг от друга?

Queue задаёт три операции, и каждая есть в двух вариантах: один бросает исключение, другой возвращает специальное значение.

Добавить в хвост: add(e) — IllegalStateException, если в очереди ограниченной ёмкости нет места; offer(e) — возвращает false.
Извлечь голову с удалением: remove() — NoSuchElementException на пустой очереди; poll() — возвращает null.
Посмотреть голову без удаления: element() — NoSuchElementException; peek() — возвращает null.

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

3.

Можно ли хранить null в Queue и почему poll() тогда вводит в заблуждение?

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

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

Если null возможен, проверяйте пустоту явно:

while (!queue.isEmpty()) {
    System.out.println(queue.poll()); // A, null, B
}

Надёжнее вовсе не класть null в очереди.

4.

Как использовать Deque как стек и как очередь? Есть ли метод pop() у Queue?

Стек (LIFO) работает только с головой: push(e) = addFirst(e), pop() = removeFirst(), peek() = peekFirst(). Очередь (FIFO) добавляет в хвост и забирает из головы: offer(e) = offerLast(e), poll() = pollFirst(), peek() = peekFirst().

Вершина стека и голова очереди — один и тот же конец, поэтому операции можно смешивать:

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

На пустом деке peek() возвращает null, а pop() бросает NoSuchElementException, как removeFirst().

У Queue метода pop() нет: push() и pop() объявлены в Deque. Код Queue<String> q = new ArrayDeque<>(); q.pop(); не скомпилируется (cannot find symbol), хотя объект ArrayDeque этот метод имеет. Для очереди используйте poll() или remove(), для стека объявляйте переменную как Deque.

5.

Какую реализацию Queue или Deque выбрать и когда add() и offer() ведут себя по-разному?

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

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

Queue<String> queue = new ArrayBlockingQueue<>(2);
queue.offer("A");                     // true
queue.offer("B");                     // true
System.out.println(queue.offer("C")); // false - места нет
queue.add("C");                       // IllegalStateException: Queue full

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

6.

Как перебрать очередь, не удаляя элементы, и можно ли получить элемент очереди по индексу?

Перебрать без удаления можно циклом for-each или через iterator(): элементы остаются в очереди. У ArrayDeque и LinkedList обход идёт от головы к хвосту, а descendingIterator() обходит Deque в обратную сторону (с Java 21 есть ещё reversed() — представление в обратном порядке). Исключение — PriorityQueue: её итератор не гарантирует порядок по приоритету, отсортированно элементы выходят только через poll().

По индексу — нет: в Queue и Deque нет методов get(int) и add(int, E), доступны только концы. Проверить наличие элемента можно через contains(), удалить из середины — через remove(Object) или removeFirstOccurrence(). Если индексы нужны, берут LinkedList через интерфейс List или ArrayList.

Интерфейсы Queue и Deque в Java - Вопросы