В чем разница между интерфейсами Queue и Deque в Java Collections Framework?

Question

В чем разница между интерфейсами Queue и Deque в Java Collections Framework?

Тип вопроса: Алгоритмы и структуры данных Вероятность: 10% Категория: Java Разработчик

Ответ

Queue — интерфейс, представляющий коллекцию, предназначенную для хранения элементов перед обработкой в порядке FIFO (First-In-First-Out), хотя некоторые реализации (например, PriorityQueue) используют другой порядок. Основные операции работают с началом (head) и концом (tail) очереди.

Deque (Double Ended Queue) — интерфейс, который расширяет Queue. Он представляет двустороннюю очередь, позволяющую добавлять, удалять и просматривать элементы с обоих концов. Таким образом, Deque может работать как очередь (FIFO), стек (LIFO) или гибридная структура.

Ключевые отличия:

Гибкость: Deque является надмножеством Queue и предоставляет более широкий набор операций.
Стек: Deque полностью заменяет устаревший класс Stack, так как его методы push(e), pop(), peek() эффективнее.

Основные методы:

Операция	`Queue` (FIFO)	`Deque` (Двусторонняя)
Добавить	`add(e)` / `offer(e)` (в конец)	`addFirst(e)` / `offerFirst(e)` (в начало) `addLast(e)` / `offerLast(e)` (в конец, как у Queue)
Удалить	`remove()` / `poll()` (с начала)	`removeFirst()` / `pollFirst()` (с начала, как у Queue) `removeLast()` / `pollLast()` (с конца)
Просмотреть	`element()` / `peek()` (начало)	`peekFirst()` (начало, как у Queue) `peekLast()` (конец)

Пример использования Deque как стека (LIFO):

Deque<String> stack = new ArrayDeque<>();
stack.push("A"); // Добавить в начало [A]
stack.push("B"); // [B, A]
String top = stack.peek(); // "B" (посмотреть)
String popped = stack.pop(); // "B" (удалить с начала), осталось [A]

Пример использования Deque как очереди (FIFO):

Deque<String> queue = new ArrayDeque<>();
queue.offerLast("A"); // Добавить в конец [A]
queue.offerLast("B"); // [A, B]
String first = queue.pollFirst(); // Удалить с начала -> "A", осталось [B]

Распространенные реализации: LinkedList, ArrayDeque (рекомендуется для стека/очереди из-за лучшей производительности).

Ответ 18+ 🔞

Давай разберем эту всю хуйню про очереди, чтобы у тебя в голове всё встало на свои места, а не болталось как манда с ушами.

Представь себе обычную очередь в столовой, блядь. Первый пришёл — первый получил свою пюрешку с котлетой. Это и есть Queue, ёпта. Интерфейс, который говорит: "Эй, дружок, клади элементы с одного конца, а забирай с другого, по-честному, FIFO". Ну, типа add(e) — встал в хвост, remove() — вышел из головы. Всё просто, как три копейки.

Queue<String> очередьВСтоловую = new LinkedList<>();
очередьВСтоловую.offer("Вася"); // Вася пришёл
очередьВСтоловую.offer("Петя"); // Петя встал за Васей
String ктоПервый = очередьВСтоловую.poll(); // Вася получил еду и ушёл. Теперь первый — Петя.

А теперь, внимание, хуй с горы! Появляется его ушастый родственник — Deque (Double Ended Queue). Это не просто очередь, это, блядь, универсальный солдат. Его главный козырь — он расширяет Queue. То есть всё, что умеет обычная очередь, умеет и эта, плюс ещё овердохуища всего.

Чем он так охуенен? А тем, что к нему можно подходить с двух сторон! Хочешь — работай как с обычной очередью (FIFO). Захотелось — открой в себе внутреннего мазохиста и используй его как стек (LIFO), "последний пришёл — первый ушёл". А можешь вообще хуярить элементы и в начало, и в конец, как тебе вздумается. Он — полная замена тому старому, кривому Stack, который все уже заебали не рекомендовать.

Вот тебе наглядная разница, чтобы не путаться:

Что делаем	В обычной `Queue` (односторонняя)	В хитрожопом `Deque` (двусторонняя)
Запихнуть элемент	`add(e)` / `offer(e)` (в хвост)	`addFirst(e)` / `offerFirst(e)` (в ГОЛОВУ) `addLast(e)` / `offerLast(e)` (в ХВОСТ, как у Queue)
Выдернуть элемент	`remove()` / `poll()` (с головы)	`removeFirst()` / `pollFirst()` (с ГОЛОВЫ, как у Queue) `removeLast()` / `pollLast()` (с ХВОСТА)
Подсмотреть элемент	`element()` / `peek()` (на голову)	`peekFirst()` (на ГОЛОВУ, как у Queue) `peekLast()` (на ХВОСТ)

Пример: делаем из Deque стек (LIFO). Вспоминаем, как книги на стопку кладёшь.

Deque<String> стопкаКниг = new ArrayDeque<>();
стопкаКниг.push("Война и мир"); // Кладём снизу, блядь [Война и мир]
стопкаКниг.push("Муму"); // Кладём сверху [Муму, Война и мир]
String верхняяКнига = стопкаКниг.peek(); // Смотрим на верхнюю -> "Муму"
String взялиКнигу = стопкаКниг.pop(); // Забираем верхнюю -> "Муму". Осталась [Война и мир]

Пример: используем Deque как нормальную очередь (FIFO). Та же столовая, но через крутые методы.

Deque<String> очередьЧерезDeque = new ArrayDeque<>();
очередьЧерезDeque.offerLast("Маша"); // Встала в конец [Маша]
очередьЧерезDeque.offerLast("Глаша"); // Встала за Машей [Маша, Глаша]
String первыйВОчереди = очередьЧерезDeque.pollFirst(); // Забрали первого -> "Маша". Осталась [Глаша]

Что использовать? LinkedList — он везде пролезет, и как Queue, и как Deque. Но если тебе нужна скорость, а не эта вся хуйня со ссылками, бери ArrayDeque. Для стека и очереди он, в большинстве случаев, быстрее. Stack — забудь как страшный сон, он старый и медленный, в рот его чих-пых.

Короче, Deque — это как Queue, но на стероидах. Можешь делать всё то же самое, плюс ебнуть элемент в начало или выдернуть с конца. Удобно, гибко, охуенно.