Опашка

За повечето хора думата "опашка" предизвиква много малко приятни асоциации. Но днес говорим за различни опашки — Java опашки. В Java опашката е всичко, което наследява интерфейса Queue , който от своя страна разширява интерфейса Collection . Това означава, че опашките могат да се третират като колекции.

Опашките в Java поддържат два принципа на работа: FIFO и LIFO .

Принципът FIFO (First In, First Out) управлява обикновена опашка — първият елемент, добавен към опашката, е първият, който я напуска.

Принципът LIFO (Last In, First Out) описва поведението на стека — последният елемент, добавен към опашката, е първият, който я напуска. Например, ето How работите с тесте карти: взимате карти една по една от горната, докато стигнете до дъното на тестето.

Йерархията на опашката в Java изглежда така:

Тук можете да видите, че Queue има 3 класа за изпълнение: LinkedList , ArrayDeque и PriorityQueue . LinkedList и ArrayDeque директно наследяват не Queue , а Deque .

Deque е интерфейс, добавен в Java 6. Той включва няколко метода, които са полезни за опашки и позволява на опашката да функционира като двустранна (or двупосочна) опашка. Това означава, че може да бъдеFIFOиLIFO.

Един от двата наследника на интерфейса Deque е ArrayDeque . Той поддържа опашка с двоен край, която ви позволява да вмъквате и премахвате елементи от двата края. Освен това е динамичен масив, който автоматично нараства по размер.

Има и клас PriorityQueue , който е пряк наследник на Queue : той се държи различно от класовете, които имплементират Deque .

PriorityQueue е опашка с приоритет, която организира елементи според естествения им ред по подразбиране. Тук сортирането използва интерфейсите Comparable и Comparator . Принципът е същият като при TreeSet or 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());
}

Ако изпълните този пример, ето Howво ще видите в конзолата:

Тъй като работим с опашки, а не с обикновени колекции, трябва да премахнем елементите от списъка. За да направим това, използваме тази конструкция:

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

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

Нека сега разгледаме някои от тези методи на практика.

Първо, нека добавим елемент към опашка:

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

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue
  
        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());
                          
    }
    

Този code показва първия и последния елемент от опашката.

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

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

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);
    

Изпълнявайки този code, получаваме:

Разликата между 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()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
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 .

Много добре! Днес научихме How да работим с опашки в Java. Сега знаете How да ги използвате на практика.