Java Queue: от основ к мастерству

В этом уроке мы изучим структуру данных Queue, Java Queue Interface, его основные методы и практические примеры. Мы также увидим различные классы реализации для Queue Interface и варианты использования для всего этого. Мы также сосредоточимся на том, как использовать очереди в многопоточной среде, сделав ее потокобезопасной.

1. Что такое очередь?

1.1 Структура данных очереди

Очередь — это линейная структура данных, которая хранит элементы в порядке FIFO(First In, First Out). Элемент, добавленный в очередь первым, будет удален первым.

Очередь имеет два конца, передний и задний. Элементы добавляются сзади и удаляются спереди.

• Front или Head: индекс, из которого элементы удаляются/обрабатываются из очереди.
• Rear или Tail: индекс, с которого в очередь добавляются новые элементы.

1.2. Когда использовать очередь?

Очереди используются в сценариях, где порядок обработки или обращения имеет решающее значение и следует принципу «первым пришел, первым обслужен». Если мы хотим представить группу отдельных объектов, поставленных в очередь на обработку, то Queue — лучший выбор. Давайте рассмотрим пример, чтобы понять это более ясно,

Служба электронной почты должна отправлять электронные письма на настроенные идентификаторы электронной почты кандидатов. Требование заключается в том, чтобы отправлять электронные письма в том порядке, в котором они добавляются в службу. Поэтому для этого требования мы можем использовать структуру данных Queue для сохранения всех идентификаторов электронной почты, что помогает нам добавлять новые электронные письма в конце(задние) и выбирать новые электронные письма с начала(спереди), чтобы отправлять электронные письма в том же порядке, в котором они добавляются в очередь.

Некоторые важные характеристики очереди:

• Мы можем получить доступ к обоим концам очереди, т.е. очередь открыта с обоих концов.
• Очереди быстры и гибки в использовании.
• Операция добавления элемента в конец очереди называется постановкой в очередь.
• Операция удаления элемента из начала очереди называется «Dequeue».
• Мы можем использовать очереди для представления реальных ситуаций, таких как обработка трафика веб-сайтов, маршрутизаторов и коммутаторов в сетях, а также обработка аппаратных процессов или системных прерываний в реальном времени.

2. Интерфейс очереди Java

Интерфейс Queue является частью фреймворка коллекций Java и обеспечивает функциональность структуры данных очереди. Давайте подробно рассмотрим интерфейс Java Queue.

Интерфейс очереди присутствует в пакете java.util и является дочерним интерфейсом интерфейса коллекции, существуя с версии Java 1.5.

public interface Queue<E> extends Collection<E> {//...}

Поскольку Queue — это интерфейс, его нельзя создать, и, следовательно, существует несколько классов реализации, которые реализуют интерфейс Queue, например LinkedList, PriorityQueue, ArrayDeque и т. д.

Существует несколько интерфейсов, которые расширяют интерфейс очереди и предоставляют расширенные функции:

• Дек
• БлокировкаОчереди
• БлокировкаDeque

3. Общие операции с очередями

Наряду с методами интерфейса коллекции, интерфейс очереди определяет еще несколько методов, которые мы можем использовать при работе с очередями в Java. Давайте рассмотрим некоторые важные методы, представленные в интерфейсе очереди.

3.1 Добавить элемент

Когда мы добавляем элемент, он добавляется в конец очереди. Интерфейс очереди предоставляет следующие два метода для добавления новых элементов:

• boolean add(e): вставляет указанный элемент в очередь. Возвращает true, если операция прошла успешно, в противном случае выдает исключение.
• boolean offer(e): вставляет указанный элемент в очередь. Возвращает true, если операция прошла успешно, в противном случае false.

Queue<String> messageQueue = new LinkedList<>();messageQueue.add("message-1");messageQueue.offer("message-2");

3.2. Запрос элемента

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

• E element(): извлекает, но не удаляет заголовок этой очереди или выдает исключение NoSuchElementException, если эта очередь пуста.
• E peek(): извлекает, но не удаляет, заголовок этой очереди или возвращает null, если эта очередь пуста.

System.out.println( messageQueue.element() ); // "message-1"System.out.println( messageQueue.peek() ); // "message-1"

3.3 Удалить элемент

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

• E poll(): Удалить и вернуть головной элемент очереди. Если очередь пуста, то этот метод возвращает null.
• E remove(): Удалить и вернуть головной элемент очереди. Если очередь пуста, то этот метод выдает исключение NoSuchElementException.

System.out.println( messageQueue.poll() ); // "message-1"System.out.println( messageQueue.remove() ); // "message-2"System.out.println( messageQueue.remove() ); // Exception in thread "main" java.util.NoSuchElementException

Различные типы очередей в Java

Давайте теперь подробно рассмотрим некоторые из этих подинтерфейсов и классы реализации интерфейса очереди, а также практические варианты использования и примеры.

4. Блокирующая очередь

BlockingQueue похож на реализацию Queue с дополнительными возможностями. BlockingQueue — это параллельная очередь, которая управляет операциями очереди параллельно. Она была добавлена в Java версии 1.5 и является частью пакета java.util.concurrent.

Некоторые важные особенности BlockingQueue:

• BlockingQueue не принимает нулевые значения. Если мы попытаемся вставить нулевое значение, то он выдаст исключение NullPointerException.
• Все методы BlockingQueue являются атомарными по своей природе и используют внутренние блокировки или другие формы управления параллелизмом.
• ArrayBlockingQueue и LinkedBlockingQueue — это классы реализации интерфейса BlockingQueue.

4.1. Природа блокировки

Обратите внимание, что BlockingQueue вводит блоки операций добавления или удаления в случае, если он полон или пуст. Таким образом, BlockingQueue отлично подходит, когда мы хотим избежать сложности, связанной с операторами wait-notify, и может использоваться для решения популярной проблемы производителя-потребителя.

• Когда поток пытается вставить элементы в уже заполненную очередь, поток блокируется до тех пор, пока какой-либо другой поток не освободит место в очереди, удалив элементы из нее.
• Аналогично, в случае удаления элементов операция блокируется, если очередь пуста, пока другой поток не вставит элемент в очередь.

4.2 Типы очереди блокировки

Как правило, очереди блокировки делятся на две категории:

• Ограниченная очередь: В ограниченной очереди емкость очереди передается конструктору очереди. Реализация BlockingQueue в ArrayBlockingQueue является примером ограниченной очереди.

BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(5);

• Неограниченная очередь: В неограниченной очереди мы не задаем емкость очереди явно, и она может увеличиваться в размере. Емкость устанавливается в Integer.MAX_VALUE. Реализация LinkedBlockingQueue BlockingQueue является примером неограниченной очереди.

BlockingQueue<String> blockingQueue = new LinkedBlockingDeque<>();

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

В следующем примере мы используем ArrayBlockingQueue, представляющую собой ограниченную блокирующую очередь, поддерживаемую массивом.

После создания его емкость не может быть изменена. Попытка поместить элемент в полную очередь приводит к блокировке операции. Аналогично, попытка взять элемент из пустой очереди также приведет к блокировке.

В следующей программе поток-производитель добавляет 5 элементов в очередь, но размер очереди равен 2, поэтому ему нужно дождаться, пока поток-потребитель удалит несколько элементов.

ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<>(2);// Producer Thread adding 5 itemsThread producerThread = new Thread(() -> {for(int i = 1; i <= 5; i++) {try {queue.put(i);System.out.println("Producer added: " + i);} catch(InterruptedException e) {System.out.println("Producer Thread interrupted.");}}});// Consumer ThreadThread consumerThread = new Thread(() -> {for(int i = 1; i <= 5; i++) {try {Thread.sleep(200);int element = queue.take();System.out.println("Consumer removed: " + element);} catch(InterruptedException e) {System.out.println("Consumer Thread interrupted.");}}});producerThread.start();consumerThread.start();

Вывод программы. Обратите внимание, что операторы печати могут появляться в разном порядке для каждого запуска, но концепция остается той же.

Producer added: 1Producer added: 2Producer added: 3Consumer removed: 1Consumer removed: 2Producer added: 4Consumer removed: 3Producer added: 5Consumer removed: 4Consumer removed: 5

5. TransferQueue

TransferQueue — это реализация параллельной блокирующей очереди, в которой производители могут ожидать получения сообщений потребителями. Добавлено в Java версии 1.7 и является частью пакета java.util.concurrent.

public interface TransferQueue<E> extends BlockingQueue<E>

5.1. Особенности TransferQueue

Мы можем использовать TransferQueue в приложениях передачи сообщений, в которых производители иногда(используют метод transfer()) ожидают получения элементов потребителями, вызывающими take или poll, а в других случаях ставят элементы в очередь(с помощью метода put()), не дожидаясь получения.

Некоторые важные функции TransferQueue:

• TransferQueue не допускает нулевых значений. Если мы попытаемся вставить нулевое значение, то он выдаст исключение NullPointerException.
• Все методы TransferQueue являются потокобезопасными.
• LinkedTransferQueue — один из классов реализации интерфейса TransferQueue.

5.2 Пример TransferQueue

Давайте теперь рассмотрим пример TransferQueue с использованием класса LinkedTransferQueue.

Поток производителя использует метод transfer() для добавления элементов в очередь, который выполняет прямую передачу ожидающему потребителю(если таковой имеется). Если ни один потребитель не готов к приему, производитель блокируется до тех пор, пока потребитель не станет доступен для приема элемента.

Потребительский поток использует метод take() для удаления элементов из очереди, который блокируется, если очередь пуста. В этом случае потребитель будет ждать, пока производитель передаст элемент.

Оба потока работают асинхронно: производитель передает элементы, а потребитель получает их в одном и том же порядке.

LinkedTransferQueue<Integer> transferQueue = new LinkedTransferQueue<>();// Producer ThreadThread producerThread1 = new Thread(() -> {for(int i = 1; i <= 5; i++) {try {System.out.println("Producer is transferring: " + i);transferQueue.transfer(i);System.out.println("Producer transferred: " + i);} catch(InterruptedException e) {System.out.println("Producer Thread interrupted.");}}});// Consumer ThreadThread consumerThread1 = new Thread(() -> {for(int i = 1; i <= 5; i++) {try {System.out.println("Consumer is waiting to receive...");int element = transferQueue.take();System.out.println("Consumer received: " + element);} catch(InterruptedException e) {System.out.println("Consumer Thread interrupted.");}}});producerThread1.start();consumerThread1.start();

Вывод программы может выводить операторы в случайном порядке при каждом запуске.

Consumer is waiting to receive...Producer is transferring: 1Producer transferred: 1Consumer received: 1Consumer is waiting to receive...Producer is transferring: 2Producer transferred: 2Producer is transferring: 3Consumer received: 2Consumer is waiting to receive...Consumer received: 3Consumer is waiting to receive...Producer transferred: 3Producer is transferring: 4Producer transferred: 4Consumer received: 4Consumer is waiting to receive...Producer is transferring: 5Producer transferred: 5Consumer received: 5

6. Дек

Deque — это двухсторонняя очередь, в которой мы можем добавлять или удалять элементы из очереди с обоих концов. Она используется как очередь и следует порядку FIFO(First In, First Out) или как стек и следует порядку LIFO(Last In, First Out). Добавлена в Java версии 1.6 и является частью пакета java.util.

public interface Deque<E> extends Queue<E> 

Мы можем использовать Deque и как стек, и как очередь, поэтому это полезно в таких случаях использования, как ведение истории веб-браузера, ведение списка отмененных операций в приложении, алгоритмы планирования заданий и т. д.

6.1 Особенности Deque

Некоторые из важных особенностей Deque:

• Для реализации Deque мы можем использовать дважды связанный список.
• Он не является потокобезопасным и не подходит для использования в многопоточных приложениях.
• Он не допускает нулевых значений и выдает исключение NullPointerException.
• ArrayDeque — один из классов реализации интерфейса Deque.

6.2 Пример дека

Давайте теперь рассмотрим пример использования Deque,

Deque<Integer> deque = new ArrayDeque<>();// Adding elements to the front of the Dequedeque.offerFirst(10);deque.offerFirst(20);deque.offerFirst(30);// Adding elements to the back of the Dequedeque.offerLast(40);deque.offerLast(50);System.out.println("Deque elements: " + deque); // [30, 20, 10, 40, 50]// Peeking elements at both ends of the DequeSystem.out.println("Peek First(Front): " + deque.peekFirst()); // 30System.out.println("Peek Last(Back): " + deque.peekLast()); // 50// Removing elements from both ends of the DequeSystem.out.println("Popped First(Front): " + deque.pollFirst()); // 30System.out.println("Popped Last(Back): " + deque.pollLast()); // 50System.out.println("Deque elements: " + deque); // [20, 10, 40]

7. ПриоритетнаяОчередь

Обычно элементы в очереди следуют порядку FIFO, но иногда нам нужно обработать элементы очереди на основе приоритета, и вот тогда в игру вступает Priority Queue. Добавлено в Java версии 1.5 и является частью пакета java.util.

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

PriorityQueue основан на приоритетной куче. Элементы приоритетной очереди упорядочиваются на основе естественного порядка сортировки по умолчанию или настраиваемого порядка сортировки, определенного Comparator, предоставленным во время создания очереди.

Мы можем использовать PriorityQueue в искусственном интеллекте(алгоритм поиска A*), в сортировке кучи, реализованной с использованием кучи, в алгоритме Прима, а также в методах сжатия данных.

7.1. Функции PriorityQueue

Некоторые важные особенности PriorityQueue:

• Мы не можем вставить нулевое значение в PriorityQueue. Если мы попытаемся вставить нулевое значение, то будет выдано исключение NullPointerException.
• Дублирующиеся элементы в PriorityQueue не допускаются.
• PriorityQueue не является потокобезопасным. Вместо этого мы можем использовать PriorityBlockingQueue для потокобезопасных операций.
• Если мы вставляем элементы на основе естественного порядка сортировки по умолчанию, то мы можем добавлять в PriorityQueue только однородные и сопоставимые элементы, в противном случае будет выдано исключение ClassCastException.
• Если мы вставляем элементы на основе настроенной сортировки Comparator, то элементы не обязательно должны быть однородными или сопоставимыми.

7.2 Пример PriorityQueue

Давайте теперь рассмотрим пример использования PriorityQueue. У нас есть тип записи Task с полем priority. Числовое значение priority представляет приоритет задачи в очереди. Большее число означает больший приоритет.

record Task(long id, String name, int priority) implements Comparable<Task> {@Overridepublic int compareTo(Task other) {return Integer.compare(other.priority, this.priority);}}

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

PriorityQueue<Task> priorityQueue = new PriorityQueue<>();priorityQueue.add(new Task(10001, "Task 1", 5));priorityQueue.add(new Task(10002, "Task 2", 1));priorityQueue.add(new Task(10003, "Task 3", 10));System.out.println(priorityQueue);while(!priorityQueue.isEmpty()) {System.out.println(priorityQueue.poll());}

Вывод программы:

Task[id=10003, name=Task 3, priority=10]Task[id=10001, name=Task 1, priority=5]Task[id=10002, name=Task 2, priority=1]

8. Безопасность потока

Основным недостатком большинства реализаций Queue, таких как PriorityQueue, LinkedList, является то, что они не являются потокобезопасными, что затрудняет работу с очередями в многопоточном приложении. Хотя возможность совместного использования Queues делает их отличными для многопоточных процессов, попытки нескольких потоков выполнить операции чтения в одной очереди могут привести к конкуренции за ресурсы и снижению скорости записи.

Java предлагает такие классы, какConcurrentLinkedQueue, ArrayBlockingQueue иConcurrentLinkedDeque, которые потокобезопасны и идеально подходят для многопоточных программ. Создание одного потока записи с BlockingQueue может облегчить эту проблему и привести к значительному повышению скорости записи.

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

Таким образом, интерфейс Queue поддерживает безопасную многопоточность, обеспечивая при этом эффективность использования памяти, что делает его идеальным для многих бизнес-кейсов, требующих оптимизированных структур данных и связанных с ними процессов.

9. Заключение

Мы узнали о структуре данных Queue вместе с Java Queue Interface, иерархией классов и ее основными методами. Мы также увидели различные классы реализации и подинтерфейсы Queue interface и их практические варианты использования, а также их основные функции и примеры того, как использовать их в нашем коде.