PriorityQueue

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

В приоритетной очереди следующим элементом считается элемент, обладающий наивысшим приоритетом. Например, в аэропорту пассажира, самолет которого скоро улетит, могут пропустить без очереди. В системах обработки сообще­ний некоторые сообщения могут быть важнее других и должны обрабатываться как можно скорее, независимо от момента их поступления. Параметризованный класс PriorityQueue был добавлен в Java SE5 как механизм автоматической реали­зации этого поведения.

При помещении объекта в PriorityQueue вызовом offer() объект сортируется в очереди. По умолчанию используется естественный порядок помещения объектов в очередь, однако вы можете изменить его, предоставив собственную реа­лизацию Comparator. PriorityQueueгарантирует, что при вызове peek(), poll() или remove() вы получите элемент с наивысшим приоритетом.

Создание приоритетной очереди для встроенных типов — Integer, String, Character и т. д. — является делом тривиальным. В следующем примере используются те же значения, что и в предыдущем, но PriorityQueue выдает их в другом порядке:

//: holding/PriorityQueueDemo.java

import java.util.*;

public class PriorityQueueDemo {

public static void main(String[] args) {

PriorityQueue<Integer> priorityQueue =

new PriorityQueue<Integer>();

Random rand = new Random(47);

for(int i = 0; i < 10; i++)

priorityQueue.offer(rand.nextInt(i + 10));

QueueDemo.printQ(priorityQueue);

List<Integer> ints = Arrays.asList(25, 22, 20,

18, 14, 9, 3, 1, 1, 2, 3, 9, 14, 18, 21, 23, 25);

priorityQueue = new PriorityQueue<Integer>(ints);

QueueDemo.printQ(priorityQueue);

priorityQueue = new PriorityQueue<Integer>(

ints.size(), Collections.reverseOrder());

priorityQueue.addAll(ints);

QueueDemo.printQ(priorityQueue);

String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";

List<String> strings = Arrays.asList(fact.split(""));

PriorityQueue<String> stringPQ =

new PriorityQueue<String>(strings);

QueueDemo.printQ(stringPQ);

stringPQ = new PriorityQueue<String>(

strings.size(), Collections.reverseOrder());

stringPQ.addAll(strings);

QueueDemo.printQ(stringPQ);

Set<Character> charSet = new HashSet<Character>();

for(char c : fact.toCharArray())

charSet.add(c); // Autoboxing

PriorityQueue<Character> characterPQ =

new PriorityQueue<Character>(charSet);

QueueDemo.printQ(characterPQ);

}

}

<spoiler text="Output:">

0 1 1 1 1 1 3 5 8 14

1 1 2 3 3 9 9 14 14 18 18 20 21 22 23 25 25

25 25 23 22 21 20 18 18 14 14 9 9 3 3 2 1 1

A A B C C C D D E E E F H H I I L N N O O O O S S S T T U U U W

W U U U T T S S S O O O O N N L I I H H F E E E D D C C C B A A

A B C D E F H I L N O S T U W

</spoiler> Мы видим, что дубликаты разрешены, а меньшие значения обладают более высокими приоритетами. Чтобы показать, как изменить порядок элементов посредством передачи собственного объекта Comparator, при третьем вызове кон­структораPriorityQueue<Integer> и втором — PriorityQueue<String> используется Comparator с обратной сортировкой, полученный вызовом Collections.reverseOrder() (одно из новшеств Java SE5). В последней части добавляется HashSet для уничтожения дубликатов Character — просто для того, чтобы пример был чуть более интересным. Integer, String и Character изначально работают с PriorityQueue, потому что они обладают «встроенным» естественным упорядочением. Если вы хотите использовать собственный класс с PriorityQueue, включите дополнительную реализацию естественного упорядочения или предоставьте собственный объект Comparator.