Все мы знаем, что очереди работают по следующей модели: FIFO (First In First Out — «первым пришёл — первым ушёл»), но иногда появляется необходимость обрабатывать объекты в очереди, основанной на приоритете. Например, у нас есть приложение, которое генерирует отчеты и обрабатывает большое количество данных, которые требуют много время на обработку. Когда клиенты посылают запросы к нашему приложению, то образуется очередь, но мы хотим обработать премиум клиентов первыми, а обычных клиентов уже после них. Именно в этом случае нам будет лучше всего использовать PriorityQueue.
Кратко о PriorityQueue
- Класс
PriorityQueue
был введен в Java 1.5 и является частью Java Collections Framework. PriorityQueue является неограниченной очередью. Элементы упорядочены по умолчанию в естественном порядке или же отсортированы с помощью компаратора. - PriorityQueue не позволяет добавлять
null
-значения иnon-comparable
объекты. Размер приоритетной очереди (PriorityQueue) неограничен, но мы можем указать начальный размер в момент его создания. Когда мы добавляем элементы в приоритетную очередь, её размер увеличивается автоматически. - PriorityQueue не является потобезопасной! Для этих целей в Java реализован класс
PriorityBlockingQueue,
реализующий интерфейс BlockingQueue. Именно он используется в многопоточной среде. - В
PriorityQueue
добавление/удаление элементов происходит за времяO(log(n))
.
Пример использования PriorityQueue на Java
Давайте посмотрим реализацию PriorityQueue
для естественного порядка добавления элементов, а также пример PriorityQueue
с компаратором:
Первым делом создадим класс Customer.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
package ua.com.prologistic; public class Customer { private int id; private String name; public Customer(int i, String n){ this.id=i; this.name=n; } public int getId() { return id; } public String getName() { return name; } } |
Мы будем использовать генерацию случайных чисел для генерации случайных объектов клиентов. Для естественного порядка добавления элементов будем использовать Integer, который в Java является классом-оболочкой.
Вот окончательный код, который показывает, как использовать PriorityQueue
.
PriorityQueueExample.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
package ua.com.prologistic; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Random; public class PriorityQueueExample { public static void main(String[] args) { //пример естественного добавления элементов в приоритетную очередь Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7); Random rand = new Random(); for(int i=0; i<7; i++){ integerPriorityQueue.add(new Integer(rand.nextInt(100))); } for(int i=0;i<7;i++){ Integer in = integerPriorityQueue.poll(); System.out.println("Обрабатываем Integer:"+in); } //Пример PriorityQueue с компаратором Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator); addDataToQueue(customerPriorityQueue); pollDataFromQueue(customerPriorityQueue); } //Анонимный класс компаратора public static Comparator<Customer> idComparator = new Comparator<Customer>(){ @Override public int compare(Customer c1, Customer c2) { return (int) (c1.getId() - c2.getId()); } }; // служебный метод добавления элементов в очередь private static void addDataToQueue(Queue<Customer> customerPriorityQueue) { Random rand = new Random(); for(int i=0; i<7; i++){ int id = rand.nextInt(100); customerPriorityQueue.add(new Customer(id, "Pankaj "+id)); } } //служебный метод для обработки данных очереди private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) { while(true){ Customer cust = customerPriorityQueue.poll(); if(cust == null) break; System.out.println("Обработка клиента с id=" + cust.getId()); } } } |
Обратите внимание, что мы используем анонимный класс для реализации интерфейса компаратора и создания компаратора на основе идентификаторов id.
Результат выполнения программы будет следующий:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Обрабатываем Integer:9 Обрабатываем Integer:16 Обрабатываем Integer:18 Обрабатываем Integer:25 Обрабатываем Integer:33 Обрабатываем Integer:75 Обрабатываем Integer:77 Обработка клиента с id=6 Обработка клиента с id=20 Обработка клиента с id=24 Обработка клиента с id=28 Обработка клиента с id=29 Обработка клиента с id=82 Обработка клиента с id=96 |
Вот и все, что нужно знать о PriorityQueue.
Если вам понравилась эта статья, пожалуйста, поделитесь с друзьями или оставьте комментарий.
Хотите узнать больше о памяти в Java? Тогда вот интересный материал о том, что такое Heap и Stack память в Java.
Спасибо. Очень интересно. Понятным «человеческим» языком написано )))