Колекції (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.