Очередь обычно представляет собой контейнер, работающий по принципу «первым вошел, первым вышел»(FIFO). Иначе говоря, элементы заносятся в очередь с одного «конца» и извлекаются с другого в порядке их поступления. Очереди часто применяются для реализации надежной передачи объектов между разными областями программы.
Класс LinkedList содержит методы, поддерживающие поведение очереди, и реализует интерфейс Queue, поэтому LinkedList может использоваться в качестве реализации Queue. В следующем примере LinkedList повышается восходящим преобразованием до Queue:
//: hoiding/QueueDemo.java
// Восходящее преобразование LinkedList в Queue
import java.util.*;
public class QueueDemo {
public static void printQCQueue queue) { while(queue.peek() != null)
System out print(queue.remove() + " "), System out printin(),
}
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<Integer>();
Random rand = new Random(47); for(int i = 0; i < 10; i++)
queue.offer(rand.nextlnt(i + 10)); printQ(queue);
Queue<Character> qc = new LinkedList<Character>(); for(char с ; "Brontosaurus".toCharArrayO)
qc.offer(c); printQ(qc);
}
} /* Output;
8 1 1 1 5 14 3 1 0 1
Brontosaurus
*///;-
Метод offer(), один из методов Queue, вставляет элемент в конец очереди, а если вставка невозможна — возвращает false. Методы реек() и element() возвращают начальный элемент без его удаления из очереди, но реек() для пустой очереди возвращает null, a element() выдает исключение NoSuchElementException. Методы poll() и remove() удаляют и возвращают начальный элемент очереди, но poll() для пустой очереди возвращает null, a remove() выдает NoSuchElementException.
Автоматическая упаковка преобразует результат int вызова nextlnt() в объект Integer, необходимый для queue, a char с — в объект Character, необходимый для qc. Интерфейс Queue сужает доступ к методам LinkedList так, что доступными остаются только соответствующие методы и у пользователя остается меньше возможностей для вызова методов LinkedList (конечно, queue можно преобразовать обратно в LinkedList, но это создает дополнительные затруднения).
Принцип FIFO описывает наиболее типичную организацию очереди. Именно организация очереди определяет, какой элемент будет следующим для заданного состояния очереди. Правило FIFO означает, что следующим элементом будет тот, который дольше всего находится в очереди.
В приоритетной очереди следующим элементом считается элемент, обладающий наивысшим приоритетом. Например, в аэропорту пассажира, самолет которого скоро улетит, могут пропустить без очереди. В системах обработки сообщений некоторые сообщения могут быть важнее других и должны обрабатываться как можно скорее, независимо от момента их поступления. Параметризованный класс PriorityQueue был добавлен в Java SE5 как механизм автоматической реализации этого поведения.
При помещении объекта в PriorityQueue вызовом offer() объект сортируется в очереди. По умолчанию используется естественный порядок помещения объектов в очередь, однако вы можете изменить его, предоставив собственную реализацию Comparator. PriorityQueue гарантирует, что при вызове peek(), poll() или removeQ вы получите элемент с наивысшим приоритетом.
Создание приоритетной очереди для встроенных типов — Integer, String, Character и т. д. — является делом тривиальным. В следующем примере используются те же значения, что и в предыдущем, но PriorityQueue выдает их в другом порядке:
//. hoiding/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.pri ntQCpriori tyQueue);
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.pri ntQ(pri ori tyQueue); priorityQueue = new PriorityQueue<Integer>(
ints.sizeO. Collections reverseOrderO); pri ori tyQueue.addAl1(i nts). QueueDemo.pri ntQCpriori tyQueue);
String fact = "EDUCATION SHOULD ESCHEW 0BFUSCATI0N"; List<String> strings = Arrays.asList(fact.split("")); PriorityQueue<String> stringPQ =
new Pri ori tyQueue<Stri ng>(stri ngs); QueueDemo.printQ(stringPQ); stringPQ = new PriorityQueue<String>(
strings.sizeO. Col lections. reverseOrderO); stringPQ.addAl1(strings); QueueDemo.printQ(stringPQ);
Set<Character> charSet = new HashSet<Character>(); for(char с • fact toCharArray())
charSet.add(c); // Автоматическая упаковка PriorityQueue<Character> characterPQ =
new PriorityQueue<Character>(charSet); QueueDemo printQ(characterPQ).
}
} /* 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
AABCCCDDEEEFHHIILNN0000SSSTTUUUW WUUUTTSSS0000NNLIIHHFEEEDDCCCBAA
ABCDEFH I LN0STUW *///:-
Мы видим, что дубликаты разрешены, а меньшие значения обладают более высокими приоритетами. Чтобы показать, как изменить порядок элементов посредством передачи собственного объекта Comparator, при третьем вызове конструктора PriorityQueue<Integer> и втором — PriorityQueue<String> используется
Comparator с обратной сортировкой, полученный вызовом Collections.reverse- Order() (одно из новшеств Java SE5).
В последней части добавляется HashSet для уничтожения дубликатов Character — просто для того, чтобы пример был чуть более интересным.
Integer, String и Character изначально работают с PriorityQueue, потому что они обладают «встроенным» естественным упорядочением. Если вы хотите использовать собственный класс с PriorityQueue, включите дополнительную реализацию естественного упорядочения или предоставьте собственный объект Comparator.
Collection и Iterator
Collection — корневой интерфейс, описывающий общую функциональность всех последовательных контейнеров. Его можно рассматривать как «вторичный интерфейс», появившийся вследствие сходства между другими интерфейсами. Кроме того, класс java.util. AbstractCollection предоставляет реализацию Collection по умолчанию, поэтому вы можете создать новый подтип AbstractCollection без избыточного дублирования кода.
Один из доводов в пользу интерфейсов заключается в том, что они позволяют создавать более универсальный код. Код, написанный для интерфейса, а не для его реализации, может быть применен к более широкому кругу объектов. Таким образом, если я пишу метод, которому при вызове передается Collection, этот метод будет работать с любым типом, реализующим Collection, — следовательно, если новый класс реализует Collection, он будет совместим с моим методом. Однако интересно заметить, что стандартная библиотека С++ не имеет общего базового класса для своих контейнеров — вся общность контейнеров обеспечивается итераторами. Казалось бы, в Java будет логично последовать примеру С++ и выражать сходство между контейнерами при помощи итераторов, а не Collection. Тем не менее эти два подхода взаимосвязаны, потому что реализация Collection также означает поддержку метода iterator():
//: hoiding/InterfaceVsIterator.java import typeinfo pets *, import java.util.*,
public class InterfaceVsIterator {
public static void display(Iterator<Pet> it) {. whileCit hasNextO) {
Pet p = it.nextO.
System out pri nt(p id() + " " + p + " ").