Queue

У многих людей слово “очередь” вызывает очень мало приятных ассоциаций. Но сегодня мы говорим о других очередях — в Java. Очередью в Java считается все, что наследует интерфейс Queue, который в свою очередь расширяет Collection. Это значит, что с очередями можно работать, как с коллекциями.

Очереди в Java работают по двум принципам: FIFO и LIFO.

FIFO — First In First Out, принцип обычной очереди (конечно, если нет тех кому нужно “только спросить”), в котором первый элемент попадает в очередь и первым выходит из нее.

LIFO — Last In First Out, принцип стека, в котором последний элемент, добавленный в очередь, первым выйдет из нее. Например, как с колодой карт: ты будешь брать все карты с верха по одной, чтобы дойти до конца.

Иерархия Queue в Java выглядит следующим образом:

Здесь видно, что у Queue есть 3 класса реализации: LinkedList, ArrayDeque и PriorityQueue. LinkedList и ArrayDeque наследует напрямую не от Queue, а от Deque.

Deque — это интерфейс, который добавили в 6 версии Java. Он включает в себя ряд полезных для очередей методов и дает возможность очереди функционировать как двунаправленная очередь. То есть работать по принципу FIFO или LIFO.

Одним из двух наследников Deque является ArrayDeque. Он поддерживает двустороннюю структуру данных очереди, что дает возможность вставлять и удалять элементы с обеих сторон. Также он — динамический массив, который может автоматически увеличивать свой размер.

Есть еще класс PriorityQueue, прямой наследник Queue: принцип его работы отличается от наследников Dequeue.

PriorityQueue — это очередь с приоритетом, которая по умолчанию размещает элементы согласно естественному порядку сортировки. Для сортировки здесь используется Comparable и Comparator. Принцип здесь такой же, как и с TreeSet или TreeMap — классов, которые следуют интерфейсу Comparable и имеют свой порядок сортировки.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Запустив этот пример в консоли, ты получишь:

Так как мы работаем с очередями, а не обычными коллекциями, мы должны удалить элемент из списка. Используем эту конструкцию:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

Интерфейс Deque наследует методы Queue и добавляет ряд своих интересных методов:

Давай теперь рассмотрим несколько из них на практике.

Добавим сначала элемент в очередь:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Добавляет элемент Apple в конец очереди
        deque.addFirst("Orange"); // Добавляет элемент Orange в начало очереди
        deque.addLast("Pineapple"); // Добавляет элемент Pineapple в конец очереди
  
        System.out.println(deque);
    

Теперь получим значения с очереди:

	Deque<String> deque = new ArrayDeque<>();

	deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 

         
        System.out.println("The First element is: "+ deque.getFirst());
                          
        System.out.println("The Last element is: " + deque.getLast());
                          
    }
    

Этот код выведет в консоли первый и последний элемент очереди.

         Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pop()); // вытащит и удалит верхний элемент очереди
System.out.println(deque.poll()); // вытащит и удалит верхний элемент очереди

System.out.println(deque);
    

Запустив этот код, получим:

Разница между методами pop() и poll() в том, что pop() вызовет исключение NoSuchElementException при пустом списке, а poll() вернет null.

Теперь рассмотрим методы pollFirst() и pollLast().

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // вытащит и удалит первый элемент очереди
System.out.println(deque.pollLast()); // вытащит и удалит последний элемент очереди.
System.out.println(deque);
    

Оба метода возвращают и удаляют значение из очереди.

Пример использования методов peekFirst() и peekLast():

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);
    

Оба метода возвращают первый/последний элемент из очереди и не удаляют их. В случае, если очередь пуста, будет возвращено null.

В общем, как-то так, сегодня мы научились работать с очередями в Java. Теперь ты будешь знать, как их использовать на практике.