Java Queue Interface i jego implementacje

Tutaj omówimy interfejs Java Queue. Dowiesz się czym jest struktura danych Queue , jak jest reprezentowana w Javie, jakie metody są najważniejsze dla wszystkich kolejek. Ponadto, jakie implementacje Queue są w języku Java. Następnie przyjrzymy się bliżej najważniejszym wdrożeniom i poznamy je na przykładach.

Struktura danych kolejki

Kolejka to liniowa abstrakcyjna struktura danych z określoną kolejnością wykonywania operacji — FIFO (First In First Out). Oznacza to, że możesz dodać element (lub wstawić do kolejki, umieścić w kolejce) tylko na końcu struktury, a wziąć element (usunąć z kolejki lub usunąć z kolejki) dopiero od jej początku. Możesz bardzo łatwo wyobrazić sobie strukturę danych Queue. Wygląda jak kolejka lub kolejka klientów w prawdziwym życiu. Klient, który przyszedł pierwszy, również zostanie obsłużony jako pierwszy. Jeśli masz cztery osoby w kolejce w McDonalds lub gdzie indziej, pierwsza, która ustawi się w kolejce, jako pierwsza wejdzie do sklepu. Jeśli pojawi się nowy klient, będzie piąty w kolejce po hamburgery. Tak więc podczas pracy z kolejką nowe elementy są dodawane na koniec, a jeśli chcesz uzyskać element, zostanie on pobrany od początku. Jest to główna zasada działania struktury danych klasycznej kolejki.

Kolejka w Javie

Kolejka w Javie to interfejs. Zgodnie z dokumentacją Oracle, interfejs Queue ma 2 superinterfejsy, 4 różne interfejsy dziedziczące po kolejce oraz niezwykle imponującą listę klas. Co to znaczy? Przede wszystkim Java Queue jest częścią Collection Framework i implementuje interfejs Collection. Obsługuje więc wszystkie metody interfejsu Collection, takie jak wstawianie, usuwanie i tak dalej. Queue implementuje interfejs Iterable, który pozwala obiektowi być celem instrukcji „for-each loop”.

Metody kolejkowania Java

Kolejka deklaruje szereg metod. Jako metody interfejsu powinny być reprezentowane we wszystkich klasach implementujących Queue. Najważniejsze metody kolejkowania, Java:

• Boolean Offer() – wstawia nowy element do kolejki, jeśli jest taka możliwość
• Boolean add(E e) – wstawia nowy element do kolejki jeśli jest taka możliwość. Zwraca true w przypadku powodzenia i zgłasza wyjątek IllegalStateException, jeśli nie ma spacji.
• Object poll() – pobiera i usuwa element z nagłówka. Zwraca wartość null, jeśli kolejka jest pusta.
• Object remove() – pobiera i usuwa element z nagłówka kolejki.
• Object peek() – pobiera, ale nie usuwa elementu z początku kolejki. Zwraca wartość null, jeśli kolejka jest pusta.
• Element obiektu() – pobiera, ale nie usuwa elementu z nagłówka kolejki.

Podinterfejsy Java Queue

Interfejs kolejki jest dziedziczony przez 4 podinterfejsy – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Możesz podzielić je na 3 grupy: Deques, Blocking Queues i Transfer Queues z BlockingDeque należącymi do dwóch pierwszych. Rzućmy okiem na te grupy.

Deques

Deque oznacza podwójnie zakończoną kolejkę i obsługuje dodawanie lub usuwanie z końca danych jako kolejki (first-in-first-out/FIFO) lub z nagłówka jako inna popularna struktura danych zwana stosem ( last - in- pierwsze wyjście/LIFO). Klasy implementujące interfejs Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Blokowanie kolejek

Kolejka blokująca to kolejka, która blokuje wątek w dwóch przypadkach:

• wątek próbuje pobrać elementy z pustej kolejki
• wątek próbuje umieścić elementy w pełnej kolejce

Gdy wątek próbuje pobrać elementy z pustej kolejki, czeka, aż jakiś inny wątek umieści elementy w kolejce. Podobnie, gdy wątek próbuje umieścić elementy w pełnej kolejce, czeka, aż jakiś inny wątek usunie elementy z kolejki, aby zwolnić miejsce dla tych elementów. Jasne, koncepcja „pełnej kolejki” implikuje, że kolejka ma ograniczony rozmiar, który jest zwykle określony w konstruktorze. Standardowe kolejki blokowania obejmują LinkedBlockingQueue, SynchronousQueue i ArrayBlockingQueue. Implementacja klas interfejsu BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlokowanieDequejest podinterfejsem dla BlockingQueue. BlockingDeque, takie jak BlockingQueue, jest kolejką blokującą, ale dwukierunkową. Dziedziczy więc właściwości interfejsu Deque. Jest zorientowany na wykonywanie wielowątkowe, nie dopuszcza zerowych elementów, a pojemność może być ograniczona. Implementacje interfejsu BlockingDeque blokują operację pobierania elementów, jeśli kolejka jest pusta i dodawania elementu do kolejki, jeśli jest pełna.

Kolejki transferowe

Interfejs TransferQueue rozszerza interfejs BlockingQueue. Jednak w przeciwieństwie do implementacji kolejek interfejsu BlockingQueue, gdzie wątki mogą być blokowane, jeśli kolejka jest pusta (odczyt) lub jeśli kolejka jest pełna (zapis), kolejki interfejsu TransferQueue blokują strumień zapisu, dopóki inny strumień nie pobierze elementu. Użyj do tego metody transferu. Innymi słowy, implementacja BlockingQueue gwarantuje, że element stworzony przez Producenta musi znaleźć się w kolejce, natomiast implementacja TransferQueue gwarantuje, że element Producer zostanie „odebrany” przez Konsumenta. Istnieje tylko jedna oficjalna implementacja Java interfejsu TransferQueue — LinkedTransferQueue.

Implementacje kolejek w Javie

Istnieje wiele klas, które implementują interfejs Queue:

• AbstractQueue zgodnie z dokumentacją Queue Java 8, ta klasa abstrakcyjna zapewnia podstawowe implementacje niektórych operacji Queue. Nie dopuszcza elementów zerowych. Istnieją jeszcze 3 metody dodawania, usuwania i elementu oparte odpowiednio na klasycznej ofercie Queue , poll i peek . Jednak zgłaszają wyjątki zamiast wskazywać niepowodzenie poprzez fałszywe lub zerowe zwroty.
• ArrayBlockingQueue — kolejka blokowania FIFO o stałym rozmiarze wspierana przez tablicę
• ArrayDeque — implementacja tablicy o zmiennym rozmiarze interfejsu Deque
• ConcurrentLinkedDeque — nieograniczona współbieżna deque oparta na połączonych węzłach.
• ConcurrentLinkedQueue — nieograniczona, bezpieczna dla wątków kolejka oparta na połączonych węzłach.
• DelayQueue — oparta na czasie kolejka planowania wspierana przez stertę
• LinkedBlockingDeque — współbieżna implementacja interfejsu Deque.
• LinkedBlockingQueue — opcjonalnie ograniczona kolejka blokowania FIFO wspierana przez połączone węzły
• LinkedList — podwójnie połączona implementacja list interfejsów List i Deque. Implementuje wszystkie opcjonalne operacje na listach i zezwala na wszystkie elementy (w tym null)
• LinkedTransferQueue — nieograniczona kolejka TransferQueue oparta na połączonych węzłach
• PriorityBlockingQueue — nieograniczona kolejka priorytetów blokowania wspierana przez stertę
• PriorityQueue — kolejka priorytetowa oparta na strukturze danych sterty
• SynchronousQueue — kolejka blokująca, w której każda operacja wstawiania musi czekać na odpowiadającą jej operację usuwania przez inny wątek i odwrotnie.

Najpopularniejsze implementacje to LinkedList, ArrayBlockingQueue i PriorityQueue. Przyjrzyjmy się im i zróbmy kilka przykładów dla lepszego zrozumienia.

Połączona lista

Klasa LinkedList w Javie implementuje interfejsy List i Deque. Jest to więc połączenie List i Deque, dwukierunkowej kolejki, która obsługuje dodawanie i usuwanie elementów z obu stron. W Javie LinkedList jest podwójnie połączoną Listą: każdy element Listy wywołuje Node i zawiera obiekt oraz odniesienia do dwóch sąsiednich obiektów — poprzedniego i następnego. Można powiedzieć, że LinkedList jest mało efektywny pod względem wykorzystania pamięci. To prawda, ale ta struktura danych może być przydatna w przypadku wykonywania operacji wstawiania i usuwania. Dzieje się tak jednak tylko wtedy, gdy używasz dla nich iteratorów (w tym przypadku dzieje się to w stałym czasie). Operacje dostępu według indeksu są wykonywane przez wyszukiwanie od początku końca (w zależności od tego, co jest bliższe) do żądanego elementu. Nie zapomnij jednak o dodatkowych kosztach przechowywania referencji między elementami. Tak więc LinkedList jest najpopularniejszą implementacją kolejek w Javie. Jest to również implementacja List i Deque i pozwala nam stworzyć dwukierunkową kolejkę składającą się z dowolnych obiektów, w tym null. LinkedList to zbiór elementów.

Konstruktory LinkedList

LinkedList() bez parametrów służy do konstruowania pustej listy. LinkedList(Collection<? extends E> c) służy do tworzenia listy zawierającej elementy określonej kolekcji, w kolejności, w jakiej są zwracane przez iterator kolekcji.

Główne metody LinkedList:

• add(E element) Dołącza określony element na końcu tej listy;
• add(int index, E element) Wstawia element w określonym indeksie pozycji;
• get(int index) Zwraca element na podanej pozycji na tej liście;
• remove(int index) Usuwa element znajdujący się na pozycji index;
• remove(Object o) Usuwa pierwsze wystąpienie elementu ?o z tej listy, jeśli się tam znajduje.
• remove() Pobiera i usuwa pierwszy element listy.
• addFirst(), addLast() dodają element na początek/koniec listy
• clear() usuwa wszystkie elementy z listy
• zawiera(Obiekt o) zwraca wartość true, jeśli lista zawiera element o.
• indexOf(Object o) zwraca indeks pierwszego wystąpienia elementu o lub -1, jeśli nie ma go na liście.
• set(int index, element E) zastępuje element na pozycji indeksu elementem
• size()Zwraca liczbę elementów na liście.
• toArray() zwraca tablicę zawierającą wszystkie elementy listy od pierwszego do ostatniego elementu.
• pop(), która zdejmuje element ze stosu (reprezentowany przez listę)
• push(E e), która wypycha element na stos (reprezentowany przez tę listę)

Przykład Java Queue — LinkedList (wstawianie i usuwanie elementów na różne sposoby)

import java.util.*;

public class LinkedListTest {

       public static void main(String args[]){

           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

Kolejka priorytetowa

PriorityQueue nie jest dokładnie kolejką w ogólnym znaczeniu FIFO. Elementy kolejki priorytetowej są uporządkowane zgodnie z ich naturalną kolejnością lub przez Komparator dostarczony podczas budowy kolejki, w zależności od użytego konstruktora. Nie jest to jednak kolejność, jak w przypadku struktury liniowej, takiej jak lista (od największego do najmniejszego lub odwrotnie). Kolejka priorytetowa oparta na stercie minimalnym priorytetu. Sterta to struktura danych oparta na drzewie binarnym. Priorytety każdego rodzica są ważniejsze niż priorytety jego dzieci. Drzewo nazywamy kompletnym binarnym, jeśli każdy rodzic ma nie więcej niż dwoje dzieci, a wypełnienie poziomów przebiega od góry do dołu (z tego samego poziomu — od lewej do prawej). Sterta binarna reorganizuje się za każdym razem, gdy nowy element jest dodawany lub usuwany z niej. W przypadku min-heap najmniejszy element trafia do korzenia niezależnie od kolejności jego wstawiania. Kolejka priorytetowa oparta na tym min-heap, więc jeśli mamy kolejkę PriorityQueue złożoną z liczb całkowitych, jej pierwszym elementem będzie najmniejsza z tych liczb. Jeśli usuniesz pierwiastek, następny najmniejszy stanie się pierwiastkiem.

Główne metody kolejki priorytetowej:

• boolean add(object) wstawia określony element do kolejki priorytetowej. Zwraca true w przypadku sukcesu. Jeśli kolejka jest pełna, metoda zgłasza wyjątek.
• boolean Offer(object) wstawia określony element do tej kolejki priorytetów. Jeśli kolejka jest pełna, metoda zwraca wartość false.
• boolean remove(object) usuwa pojedynczą instancję określonego elementu z tej kolejki, jeśli jest obecna.
• Obiekt poll() pobiera i usuwa nagłówek tej kolejki. Zwraca wartość null, jeśli kolejka jest pusta.
• void clear() usuwa wszystkie elementy z kolejki priorytetów.
• Element obiektu() pobiera nagłówek tej kolejki bez jej usuwania. Zgłasza wyjątek NoSuchElementException, jeśli kolejka jest pusta.
• Object peek() pobiera nagłówek kolejki bez usuwania go. Zwraca wartość null, jeśli kolejka jest pusta.
• logiczna zawiera(Obiekt o) zwraca wartość true, jeśli kolejka zawiera element o.
• int size() zwraca liczbę elementów w tej kolejce.

Przykład kolejki priorytetowej

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

Ważne jest, aby zrozumieć, że kolejki priorytetowe są oparte na stosach binarnych, więc nie przechowują elementów w porządku liniowym. Każda droga od korzenia do liścia jest uporządkowana, ale różne drogi od korzenia nie. Oznacza to, że możesz bardzo szybko uzyskać minimalny element kolejki. Jeśli usuniesz głowę za każdym razem, wydrukujesz posortowaną strukturę.

Kolejka blokująca tablicę

Wewnętrzna struktura danych ArrayBlockingQueuejest oparty na okrągłej tablicy do przechowywania elementów. Jest to typowa kolejka (FIFO) w przypadku, gdy nowe elementy są wstawiane na końcu kolejki, a operacje ekstrakcji zwracają element z początku kolejki. Raz utworzonej pojemności kolejki nie można zmienić. Próby wstawienia (umieszczenia) elementu w pełnej kolejce prowadzą do zablokowania przepływu; próba pobrania elementu z pustej kolejki również blokuje wątek. Jak powiedzieliśmy wcześniej, ta tablica jest okrągła. Oznacza to, że pierwszy i ostatni element tablicy są traktowane jako logicznie przylegające. Kolejka zwiększa indeksy elementów head i tail za każdym razem, gdy umieszczasz elemento w kolejce lub usuwasz go z kolejki. Jeśli jakiś indeks przesuwa ostatni element tablicy, rozpoczyna się od 0. Stąd kolejka nie musi przesuwać wszystkich elementów w przypadku usunięcia głowy (jak w zwykłej tablicy). Natomiast w przypadku usunięcia elementu ze środka (za pomocą Iterator.remove) następuje przesunięcie elementów. ArrayBlockingQueue obsługuje dodatkową politykę fairness z parametrem fair w konstruktorze, aby uporządkować pracę oczekujących przepływów producentów (wstawianie elementów) i konsumentów (wyodrębnianie elementów). Domyślnie zamówienie nie jest gwarantowane. Jeśli jednak kolejka jest tworzona z wartością „fair == true”, implementacja klasy ArrayBlockingQueue zapewnia dostęp do wątków w kolejności FIFO. Kapitał zazwyczaj zmniejsza przepustowość, ale także zmniejsza zmienność i zapobiega wyczerpaniu zasobów.

Konstruktory klasy ArrayBlockingQueue

• ArrayBlockingQueue (int Capacity) tworzy kolejkę o stałej pojemności i z domyślną polityką dostępu.
• ArrayBlockingQueue (int capacity, boolean fair) tworzy kolejkę o stałej pojemności i określonej polityce dostępu.
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) tworzy kolejkę o stałej pojemności określonej przez politykę dostępu i zawiera elementy w kolejce.

Oto przykład BlockingQueueExample. Tworzymy kolejkę typu ArrayBlockingQueue o pojemności jednego elementu i flagi fair. Uruchamiane są dwa wątki. Pierwszy z nich, wątek Producer, kolejkuje komunikaty z tablicy komunikatów za pomocą metody put. Drugi wątek, Konsument, odczytuje elementy z kolejki metodą take i wyświetla je w konsoli. Kolejność elementów jest naturalna dla kolejki.

import java.util.concurrent.*;

public class ArrayBlockingQueueExample {

   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};

       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }

       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

Dane wyjściowe to kolejka w naturalnym porządku; pierwsze dwa elementy pojawiają się z opóźnieniem. Aby utrwalić to, czego się nauczyłeś, zalecamy obejrzenie lekcji wideo z naszego kursu języka Java

Wnioski

• Kolejka służy do wstawiania elementów na końcu kolejki i usuwania z początku kolejki. Jest zgodny z koncepcją FIFO.
• Java Queue jest częścią Collection Framework i implementuje interfejs Collection. Obsługuje więc wszystkie metody interfejsu Collection, takie jak wstawianie, usuwanie i tak dalej.
• Najczęściej używanymi implementacjami Queue są LinkedList, ArrayBlockingQueue i PriorityQueue.
• Elementy kolejki priorytetowej są uporządkowane zgodnie z ich naturalną kolejnością lub przez Komparator dostarczony podczas budowy kolejki, w zależności od użytego konstruktora.
• Jeśli na BlockingQueues zostanie wykonana jakakolwiek operacja o wartości null, zostanie zgłoszony wyjątek NullPointerException.