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 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() i 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 first element is: " + friends.peekLast());

System.out.println(friends);
    

Обидва методи повертають перший/останній елемент із черги і не видаляють їх. Якщо черга порожня, буде повернено null.

Загалом якось так, сьогодні ми навчилися працювати з чергами в Java. Тепер ти знатимеш, як їх використовувати на практиці.