Содержание
В этой статье речь пойдет об очередях, а именно: об интерфейсе Queue и о классе PriorityQueue.
Queue - коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.
Очереди обычно, но не обязательно, упорядочивают элементы в FIFO (first-in-first-out, "первым вошел - первым вышел") порядке.
Метод offer() вставляет элемент в очередь, если это не удалось - возвращает false. Этот метод отличается от метода add() интерфейса Collection тем, что метод add() может неудачно добавить элемент только с использованием unchecked исключения.
Методы remove() и poll() удаляют верхушку очереди и возвращают ее. Какой элемент будет удален (первый или последний) зависит от реализации очереди. Методы remove() и poll() отличаются лишь поведением, когда очередь пустая: метод remove() генерирует исключение, а метод poll() возвращает null.
Методы element() и peek() возвращают (но не удаляют) верхушку очереди.
То есть, вышеприведенные методы существуют в двух формах: одни генерируют исключение если операция не удалась, другие - возвращают специальное значение. Это можно продемонстрировать следующей таблицей:
Тип операции | Генерирует исключение | Возвращает специальное значение |
---|---|---|
Добавление | add(e) | offer(e) |
Удаление | remove() | poll() |
Получение верхушки | element() | peek() |
На Рис.1 приведена иерархия классов Queue.
Рис 1. Иерархия Queue во фреймворке Collections
Обычно, очередь не позволяет добавлять null элементы из-за того, что null используется как служебный объект метода poll() и peek(). Однако в некоторых реализация интерфейса Queue есть возможность добавление null элементов (например, LinkedList). Также не разрешается добавлять элементы, которые не можно сравнить с помощью класса Comparator.
PriorityQueue - единственная прямая реализация интерфейса Queue (не считая LinkedList, который больше является списком, чем очередью).
Эта очередь упорядочивает элементы либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе. Например, следующим кодом упорядочиваются целочисленные элементы в обратном порядке:
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if( o1 > o2 ){
return -1;
}
if( o1 < o2 ){
return 1;
}
return 0;
}
};
Queue<Integer> intQueue = new PriorityQueue<>(10, comparator);
intQueue.add(4);
intQueue.add(3);
intQueue.add(1);
while( !intQueue.isEmpty() ){
System.out.println( intQueue.remove() );
}
Обратите внимание, что при использовании цикла foreach или итератора для перебора элементов очереди, они (элементы) будут идти в неправильном порядке. Чтобы решить эту проблему, необходимо использовать метод sort() класса Arrays. Например, так:
...
Queue<Integer> intQueue = new PriorityQueue<>(10, comparator);
intQueue.add(4);
intQueue.add(3);
intQueue.add(1);
Integer[] intArray = new Integer[intQueue.size()];
intQueue.toArray( intArray );
Arrays.sort(intArray, comparator);
for( int entry : intArray ){
System.out.println( entry );
}
Размер PriorityQueue ничем не ограничен, однако в этой очереди есть внутреннее значение capacity, которое регулирует размер очереди. Это значение должно быть как минимум больше, чем размер очереди. При добавлении элементов в PriorityQueue мощность (capacity) растет автоматически.
Также стоит отметить, что PriorityQueue является не синхронизированной очередью. Разные потоки не должны одновременно модифицировать экземпляр PriorityQueue. Для этого используйте потоко-безопасный класс PriorityBlockingQueue.
< | Коллекции (Collections) в Java. Set | Коллекции (Collections) в Java. Map | > |
24 ноября 2014 г. 17:32
|
хороший сайт
почти ничего не понял, но инфа полезная:) |