PriorityBlockingQueue

PriorityBlockingQueue — это класс из стандартной библиотеки языка Java (пакет java.util.concurrent), реализующий потокобезопасную неограниченную очередь с приоритетом. Он объединяет функциональность неблокирующей очереди с приоритетом (PriorityQueue) и блокирующей очереди (BlockingQueue), обеспечивая безопасный доступ к элементам из нескольких потоков.

Основные характеристики

PriorityBlockingQueue основана на структуре данных «бинарная куча» (binary heap). Элементы в очереди упорядочиваются либо в соответствии с их естественным порядком (если они реализуют интерфейс Comparable), либо с помощью компаратора, переданного при создании очереди. Голова очереди всегда содержит наименьший элемент согласно заданному порядку.

Очередь является неограниченной: её ёмкость не фиксируется, и она автоматически расширяется по мере добавления элементов. Однако, как и все блокирующие очереди, она поддерживает операции с тайм-аутами для ожидания при извлечении элементов.

Ключевые особенности

Потокобезопасность

PriorityBlockingQueue использует внутренние блокировки (ReentrantLock) для синхронизации доступа. Это позволяет безопасно добавлять и извлекать элементы из нескольких потоков одновременно. В отличие от PriorityQueue, которая не является потокобезопасной, PriorityBlockingQueue гарантирует корректное поведение в многопоточной среде.

Блокирующие операции

Как и другие реализации BlockingQueue, PriorityBlockingQueue поддерживает блокирующие методы:

• take() — извлекает и удаляет голову очереди, блокируя поток, если очередь пуста, до появления нового элемента.
• poll(long timeout, TimeUnit unit) — извлекает и удаляет голову очереди, ожидая в течение заданного времени, если очередь пуста.

Неблокирующие операции

• offer(E e) — добавляет элемент в очередь, возвращая true (всегда, так как очередь неограниченная).
• poll() — извлекает и удаляет голову очереди, возвращая null, если очередь пуста.
• peek() — возвращает голову очереди без удаления, или null, если очередь пуста.

Итераторы

Итератор, возвращаемый методом iterator(), не гарантирует обход элементов в порядке приоритета. Он обходит элементы в произвольном порядке, соответствующем внутренней структуре кучи. Для получения элементов в порядке приоритета следует использовать методы poll() или take().

Пример использования

```java import java.util.concurrent.PriorityBlockingQueue;

public class PriorityBlockingQueueExample { public static void main(String[] args) throws InterruptedException { // Создаем очередь с приоритетом по умолчанию (естественный порядок) PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();

// Добавляем элементы queue.offer(5); queue.offer(1); queue.offer(3); queue.offer(7);

// Извлекаем элементы в порядке приоритета System.out.println("Извлечение в порядке приоритета:"); while (!queue.isEmpty()) { System.out.println(queue.poll()); // Выведет: 1, 3, 5, 7 } } } ```

Применение

PriorityBlockingQueue используется в сценариях, где требуется обработка задач с приоритетом в многопоточной среде. Типичные примеры включают:

• Планировщики задач: где задачи с более высоким приоритетом должны выполняться раньше.
• Системы обработки событий: где события с разными приоритетами обрабатываются в порядке важности.
• Потоковые пулы: где задачи могут иметь разный приоритет, и пул потоков должен обрабатывать их в соответствии с этим приоритетом.

Отличия от других реализаций BlockingQueue

Ограничения и особенности

• PriorityBlockingQueue не поддерживает нулевые элементы (null). Попытка добавить null вызовет NullPointerException.
• Порядок элементов с одинаковым приоритетом не гарантируется. Если несколько элементов имеют одинаковый приоритет, порядок их извлечения может быть произвольным.
• В отличие от PriorityQueue, PriorityBlockingQueue не предоставляет методов для изменения приоритета уже добавленного элемента. Для изменения приоритета необходимо удалить элемент и добавить его снова.
• Итератор не является потокобезопасным. Если очередь изменяется во время итерации, итератор может выбросить ConcurrentModificationException.

Источники

• Java Documentation: java.util.concurrent.PriorityBlockingQueue
• «Java Concurrency in Practice» by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, Doug Lea
• «Effective Java» by Joshua Bloch