Коллекции (Collections) в Java. Queue

В этой статье речь пойдет об очередях, а именно: об интерфейсе Queue и о классе PriorityQueue.

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

Очереди обычно, но не обязательно, упорядочивают элементы в FIFO (first-in-first-out, "первым вошел - первым вышел") порядке.

Метод offer() вставляет элемент в очередь, если это не удалось - возвращает false. Этот метод отличается от метода add() интерфейса Collection тем, что метод add() может неудачно добавить элемент только с использованием unchecked исключения.

Методы remove() и poll() удаляют верхушку очереди и возвращают ее. Какой элемент будет удален (первый или последний) зависит от реализации очереди. Методы remove() и poll() отличаются лишь поведением, когда очередь пустая: метод remove() генерирует исключение, а метод poll() возвращает null.

Методы 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.