Queue and Deque

Queue и Deque

Queue

Queue<E> описывает коллекцию, из которой элементы извлекаются по некоторой политике. Обычная очередь следует FIFO, но интерфейс этого не гарантирует: PriorityQueue, например, выдаёт элемент с наивысшим приоритетом.

У операций есть две формы:

Действие	Исключение при неуспехе	Специальное значение
вставить	add(e)	offer(e) → false
посмотреть голову	element()	peek() → null
извлечь голову	remove()	poll() → null

Формы offer/poll особенно полезны для очередей с ограниченной ёмкостью и для пустой очереди.

Queue<String> tasks = new ArrayDeque<>();
tasks.offer("index");
tasks.offer("notify");
 
while (!tasks.isEmpty()) {
    process(tasks.poll());
}

Deque

Deque<E> — двусторонняя очередь. Она поддерживает вставку, чтение и удаление с обоих концов.

Начало	Конец
addFirst, offerFirst	addLast, offerLast
getFirst, peekFirst	getLast, peekLast
removeFirst, pollFirst	removeLast, pollLast

ArrayDeque обычно подходит и для очереди, и для стека:

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
 
String value = stack.pop(); // second

Для нового кода Deque предпочтительнее устаревшего Stack: у него яснее контракт и нет наследия синхронизированного Vector.

ArrayDeque, LinkedList и PriorityQueue

• ArrayDeque — кольцевой расширяемый массив, быстрые операции с концов, не допускает null.
• LinkedList тоже реализует Deque, допускает null, но хранит отдельный узел для каждого элемента и обычно хуже использует память и кэш.
• PriorityQueue — двоичная куча. peek возвращает минимальный элемент по естественному порядку или заданному Comparator; полный обход не обязан быть отсортирован.

Queue<Job> byPriority = new PriorityQueue<>(
        Comparator.comparingInt(Job::priority)
);
byPriority.offer(new Job("report", 20));
byPriority.offer(new Job("alert", 1));
 
Job next = byPriority.poll(); // alert

Инварианты и ловушки

• Не храните null в очереди, если poll/peek используют null как сигнал отсутствия.
• Не ожидайте FIFO от PriorityQueue.
• Не используйте remove(0) у ArrayList как очередь: каждый раз сдвигается весь хвост.
• Итерация по PriorityQueue не выдаёт элементы в приоритетном порядке; для этого нужно последовательно вызывать poll.
• Для обмена между потоками нужны BlockingQueue или concurrent-деки, а не обычный ArrayDeque.

Вопросы на собеседовании

1. Чем пары add/offer, remove/poll и element/peek отличаются друг от друга?
2. Почему ArrayDeque обычно лучше Stack?
3. Гарантирует ли Queue порядок FIFO?
4. Как устроена PriorityQueue и какова стоимость вставки и извлечения?
5. Почему обход PriorityQueue не равен извлечению по приоритету?

Связанные заметки

Collection · Иерархия коллекций · List · Big O оценка сложности операций с коллекциями · Comparator Java