Java Queue Interface en zijn implementaties

Hier gaan we de Java Queue-interface bespreken. U zult ontdekken wat de datastructuur van Queue is, hoe deze wordt weergegeven in Java, welke methoden het belangrijkst zijn voor alle wachtrijen. Ook welke implementaties van Queue in de Java-taal zijn. Daarna nemen we de belangrijkste implementaties onder de loep en leren ze aan de hand van voorbeelden.

Wachtrij gegevensstructuur

Een wachtrij is een lineaire abstracte gegevensstructuur met de specifieke volgorde van uitvoeren van bewerkingen: First In First Out (FIFO). Dat betekent dat u een element alleen aan het einde van de structuur kunt toevoegen (of in de wachtrij plaatsen, in de wachtrij plaatsen), en een element alleen vanaf het begin kunt nemen (uit de wachtrij verwijderen of uit de wachtrij kunt verwijderen). U kunt zich de wachtrijgegevensstructuur heel gemakkelijk voorstellen. Het lijkt in het echte leven op een rij of een rij klanten. De klant die het eerst kwam, wordt ook het eerst bediend. Als je vier mensen in de rij hebt staan ​​bij McDonalds of ergens anders, is de eerste die in de rij staat de eerste die de winkel binnengaat. Als de nieuwe klant komt, is hij/zij de 5e in de rij om hamburgers te halen. Dus terwijl u met een wachtrij werkt, worden nieuwe elementen aan het einde toegevoegd en als u een element wilt krijgen, wordt het vanaf het begin genomen. Dit is het belangrijkste principe van het klassieke werken met wachtrijgegevensstructuren.

Wachtrij in Java

Wachtrij in Java is een interface. Volgens de Oracle-documentatie heeft de Queue-interface 2 superinterfaces, 4 verschillende interfaces die erven van de wachtrij en een buitengewoon indrukwekkende lijst met klassen. Wat betekent het? Allereerst maakt Java Queue deel uit van het Collection Framework en implementeert het de Collection-interface. Het ondersteunt dus alle methoden van de verzamelingsinterface, zoals invoegen, verwijderen enzovoort. Wachtrij implementeert Iterable-interface, waarmee een object het doel kan zijn van de "for-each loop"-instructie.

Wachtrijmethoden Java

De wachtrij declareert een aantal methoden. Als methoden van de interface zouden ze vertegenwoordigd moeten zijn in alle klassen die Queue implementeren. De belangrijkste wachtrijmethoden, Java:

• Boolean offer() – voegt een nieuw element in de wachtrij in als dit mogelijk is
• Boolean add(E e) – voegt een nieuw element toe aan de wachtrij indien mogelijk. Retourneert true in geval van succes en genereert een IllegalStateException als er geen spatie is.
• Object poll() – haalt een element op en verwijdert het uit de kop van het. Retourneert null als de wachtrij leeg is.
• Object remove() – haalt een element op en verwijdert het uit de kop van de wachtrij.
• Object peek() – haalt een element op, maar verwijdert het niet uit de kop van de wachtrij. Retourneert null als de wachtrij leeg is.
• Object element() – haalt een element op, maar verwijdert het niet uit de kop van de wachtrij.

Subinterfaces van Java Queue

De wachtrij- interface wordt overgenomen door 4 subinterfaces: BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . U kunt ze onderverdelen in 3 groepen: Deques, Blocking Queues en Transfer Queues waarbij BlockingDeque tot de eerste twee behoort. Laten we een kijkje nemen in deze groepen.

Deques

Deque betekent D ouble- E nded Queue en ondersteunt toevoeging of verwijdering van beide staarten van de data als een wachtrij (first-in-first-out/FIFO) of van de kop als een andere populaire datastructuur genaamd stack (last - in- eerste uit/LIFO). Klassen die Deque Interface implementeren: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Wachtrijen blokkeren

Een blokkeerwachtrij is een wachtrij die een thread in twee gevallen blokkeert:

• thread probeert elementen uit een lege wachtrij te halen
• thread probeert elementen in de volledige wachtrij te plaatsen

Wanneer een thread items uit een lege wachtrij probeert te halen, wacht deze tot een andere thread de items in de wachtrij plaatst. Evenzo, wanneer een thread elementen in een volledige wachtrij probeert te plaatsen, wacht het totdat een andere thread de elementen uit de wachtrij haalt om vrije ruimte voor de elementen te krijgen. Zeker, het concept van "volledige wachtrij" houdt in dat de wachtrij een beperkte grootte heeft, die meestal wordt gespecificeerd in de constructor. Standaard blokkeerwachtrijen omvatten LinkedBlockingQueue, SynchronousQueue en ArrayBlockingQueue. Implementatieklassen van de BlockingQueue- interface: ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeis een subinterface voor BlockingQueue. BlockingDeque zoals BlockingQueue is een blokkerende wachtrij, maar dan in twee richtingen. Het erft dus de eigenschappen van de Deque-interface. Het is gericht op uitvoering met meerdere threads, staat geen nul-elementen toe en de capaciteit kan beperkt zijn. Implementaties van de BlockingDeque-interface blokkeren de werking van het ophalen van elementen als de wachtrij leeg is en het toevoegen van een element aan de wachtrij als deze vol is.

Wachtrijen overdragen

TransferQueue-interface breidt BlockingQueue-interface uit. In tegenstelling tot de implementatie van BlockingQueue-interfacewachtrijen, waarbij threads kunnen worden geblokkeerd als de wachtrij leeg is (lezen) of als de wachtrij vol is (schrijven), blokkeren TransferQueue-interfacewachtrijen de schrijfstroom totdat een andere stroom het element ophaalt. Gebruik hiervoor een overboekingsmethode. Met andere woorden, de implementatie van BlockingQueue garandeert dat het door de Producer aangemaakte element in de wachtrij moet staan, terwijl de implementatie van TransferQueue garandeert dat het Producer-element wordt "ontvangen" door de Consument. Er is slechts één officiële Java-implementatie van de TransferQueue-interface: LinkedTransferQueue.

Java Queue-implementaties

Er zijn veel klassen die de Queue-interface implementeren:

• AbstractQueue volgens Queue Java 8-docs, deze abstracte klasse biedt basisimplementaties van sommige Queue-bewerkingen. Het staat geen null-elementen toe. Er zijn nog 3 methoden voor toevoegen, verwijderen en element op basis van respectievelijk Queue classic offer , poll en peek . Ze genereren echter uitzonderingen in plaats van een fout aan te geven via valse of null-retouren.
• ArrayBlockingQueue — een FIFO-blokkeerwachtrij van vaste grootte ondersteund door een array
• ArrayDeque - aanpasbare array-implementatie van de Deque-interface
• ConcurrentLinkedDeque — een onbeperkte gelijktijdige deque op basis van gekoppelde knooppunten.
• ConcurrentLinkedQueue - een onbeperkte thread-safe wachtrij op basis van gekoppelde knooppunten.
• DelayQueue - een op tijd gebaseerde planningswachtrij ondersteund door een hoop
• LinkedBlockingDeque - de gelijktijdige implementatie van de Deque-interface.
• LinkedBlockingQueue — een optioneel begrensde FIFO-blokkeerwachtrij ondersteund door gekoppelde knooppunten
• LinkedList - dubbel gekoppelde lijstimplementatie van de List- en Deque-interfaces. Implementeert alle optionele lijstbewerkingen en staat alle elementen toe (inclusief null)
• LinkedTransferQueue — een onbegrensde TransferQueue op basis van gekoppelde knooppunten
• PriorityBlockingQueue — een onbeperkte blokkeerprioriteitswachtrij ondersteund door een heap
• PriorityQueue — een prioriteitswachtrij op basis van de heap-gegevensstructuur
• SynchronousQueue - een blokkeerwachtrij waarbij elke invoegbewerking moet wachten op een overeenkomstige verwijderbewerking door een andere thread, en vice versa.

De meest populaire implementaties zijn LinkedList, ArrayBlockingQueue en PriorityQueue. Laten we ze eens bekijken en enkele voorbeelden geven voor een beter begrip.

Gelinkte lijst

Class LinkedList in Java implementeert List- en Deque-interfaces. Het is dus een combinatie van List en Deque, een tweerichtingswachtrij, die het toevoegen en verwijderen van elementen van beide kanten ondersteunt. In Java is LinkedList een dubbel gekoppelde lijst: elk element van List roept Node aan en bevat een object en verwijzingen naar twee naburige objecten - het vorige en het volgende. Je zou kunnen zeggen dat LinkedList niet erg effectief is in termen van geheugengebruik. Dat klopt, maar deze gegevensstructuur kan handig zijn in het geval van de prestaties van invoeg- en verwijderbewerkingen. Het gebeurt echter alleen als u er iterators voor gebruikt (in dit geval gebeurt het in een constante tijd). Toegangsbewerkingen per index worden uitgevoerd door te zoeken vanaf het begin van het einde (wat het dichtst bij is) naar het gewenste element. Vergeet echter niet de extra kosten voor het opslaan van referenties tussen elementen. LinkedList is dus de meest populaire wachtrij-implementatie in Java. Het is ook een implementatie van List en Deque en stelt ons in staat om een ​​bidirectionele wachtrij te creëren die bestaat uit alle objecten, inclusief null. LinkedList is een verzameling elementen.

LinkedList-constructeurs

LinkedList() zonder parameters wordt gebruikt om een ​​lege lijst samen te stellen. LinkedList(Collection<? extends E> c) is voor het maken van een lijst met de elementen van de gespecificeerde collectie, in volgorde waarin ze worden geretourneerd door de iterator van de collectie.

Belangrijkste LinkedList-methoden:

• add(E element) Voegt het gespecificeerde element toe aan het einde van deze lijst;
• add(int index, E element) Voegt het element in op de gespecificeerde positie-index;
• get(int index) Geeft het element terug op de gespecificeerde positie in deze lijst;
• remove(int index) Verwijdert het element dat op positie index staat;
• remove(Object o) Verwijdert het eerste voorkomen van het ?o element uit deze lijst als het er is.
• remove() Haalt het eerste element van de lijst op en verwijdert het.
• addFirst(), addLast() voeg een element toe aan het begin/einde van een lijst
• clear() verwijdert alle elementen uit de lijst
• bevat(Object o) retourneert true als de lijst het o-element bevat.
• indexOf(Object o) geeft de index terug van het eerste voorkomen van het element o, of -1 als het niet in de lijst staat.
• set(int index, E element) vervangt het element op de indexpositie door het element
• size()Retourneert het aantal elementen in de lijst.
• toArray() retourneert een array die alle elementen van de lijst bevat, van het eerste tot het laatste element.
• pop() die een element uit de stapel haalt (weergegeven door de lijst)
• push(E e) dat een element op de stapel duwt (weergegeven door deze lijst)

Voorbeeld van Java Queue — LinkedList (elementen op verschillende manieren plaatsen en verwijderen)

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);
       }
       }

Prioriteits-rij

PriorityQueue is niet precies de wachtrij in algemene FIFO-betekenis. De elementen van de prioriteitswachtrij worden geordend volgens hun natuurlijke ordening, of door een comparator die wordt geleverd tijdens de opbouw van de wachtrij, afhankelijk van welke constructor wordt gebruikt. Het is echter geen volgorde zoals het zou kunnen zijn in een lineaire structuur zoals een lijst (van de grootste naar de kleinste of vice versa). Een prioriteitswachtrij op basis van een minimale prioriteitsheap. Heap is een gegevensstructuur op basis van een binaire boom. De prioriteit van elke ouder is groter dan de prioriteiten van zijn kinderen. Een boom wordt volledig binair genoemd als elke ouder niet meer dan twee kinderen heeft en de niveaus van boven naar beneden worden gevuld (van hetzelfde niveau - van links naar rechts). Binaire heap reorganiseert zichzelf elke keer dat er een nieuw element wordt toegevoegd of verwijderd. In het geval van min-heap gaat het kleinste element naar de root, ongeacht de volgorde van invoeging. Prioriteitswachtrij op basis van deze min-heap, dus als we een PriorityQueue van gehele getallen hebben, is het eerste element het kleinste van deze getallen. Als u de wortel verwijdert, wordt de volgende kleinste een wortel.

Belangrijkste PriorityQueue-methoden:

• boolean add(object) voegt het opgegeven element in de prioriteitswachtrij in. Retourneert true in geval van succes. Als de wachtrij vol is, genereert de methode een uitzondering.
• boolean offer(object) voegt het gespecificeerde element in deze prioriteitswachtrij in. Als de wachtrij vol is, retourneert de methode false.
• boolean remove(object) verwijdert een enkel exemplaar van het gespecificeerde element uit deze wachtrij, indien aanwezig.
• Object poll() haalt de kop van deze wachtrij op en verwijdert deze. Retourneert null als de wachtrij leeg is.
• void clear() verwijdert alle elementen uit de prioriteitswachtrij.
• Object element() haalt de kop van deze wachtrij op zonder deze te verwijderen. Gooit NoSuchElementException als de wachtrij leeg is.
• Object peek() haalt de kop van de wachtrij op zonder deze te verwijderen. Retourneert null als de wachtrij leeg is.
• boolean bevat(Object o) retourneert true als de wachtrij het o-element bevat.
• int size() geeft het aantal elementen in deze wachtrij terug.

Voorbeeld van PriorityQueue

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

Het is belangrijk om te begrijpen dat prioriteitswachtrijen gebaseerd zijn op binaire heaps, zodat ze de elementen niet in lineaire gesorteerde volgorde houden. Elke weg van de wortel naar het blad is geordend, maar de verschillende wegen van de wortel niet. Dat betekent dat je heel snel het minimale deel van de wachtrij kunt krijgen. Als je elke keer de kop verwijdert, print je een gesorteerde structuur.

ArrayBlockingQueue

Interne gegevensstructuur van ArrayBlockingQueueis gebaseerd op een circulaire array om elementen op te slaan. Het is een typische wachtrij (FIFO) in het geval dat nieuwe elementen aan het einde van de wachtrij worden ingevoegd en extractiebewerkingen een element uit het begin van de wachtrij retourneren. Eenmaal aangemaakte capaciteit van de wachtrij kan niet meer worden gewijzigd. Pogingen om een ​​element in een volledige wachtrij in te voegen (plaatsen) leiden tot het blokkeren van de stroom; proberen een element uit een lege wachtrij te halen, blokkeert ook de thread. Zoals we al eerder zeiden, is deze array cirkelvormig. Dat betekent dat de eerste en de laatste elementen van de array logisch naast elkaar worden behandeld. De wachtrij verhoogt de indices van de kop- en staartelementen elke keer dat u de elemento in de wachtrij plaatst of uit de wachtrij verwijdert. Als een index het laatste element van de array vooruitschuift, begint deze opnieuw vanaf 0. Vandaar dat de wachtrij hoeft niet alle elementen te verschuiven in het geval dat de kop wordt verwijderd (zoals bij de gebruikelijke array). Als een element echter uit het midden wordt verwijderd (met Iterator.remove), worden de elementen verschoven. ArrayBlockingQueue ondersteunt een aanvullend eerlijkheidsbeleid met eerlijke parameter in de constructor om het werk van wachtende stromen van producenten (elementen invoegen) en consumenten (elementen extraheren) te ordenen. Standaard is de bestelling niet gegarandeerd. Als de wachtrij echter wordt gemaakt met "fair == true", biedt de implementatie van de klasse ArrayBlockingQueue threadtoegang in FIFO-volgorde. Eigen vermogen vermindert doorgaans de bandbreedte, maar vermindert ook de volatiliteit en voorkomt dat de middelen opraken.

ArrayBlockingQueue Class сonstructors

• ArrayBlockingQueue (int capacity) creëert een wachtrij met vaste capaciteit en met een standaard toegangsbeleid.
• ArrayBlockingQueue (int capacity, boolean fair) creëert een wachtrij met een vaste capaciteit en een gespecificeerd toegangsbeleid.
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) creëert een wachtrij met een vaste capaciteit gespecificeerd door het toegangsbeleid en neemt elementen in de wachtrij op.

Hier hebben we het BlockingQueueExample-voorbeeld. We maken een wachtrij van de ArrayBlockingQueue met een capaciteit van één element en een eerlijke vlag. Er worden twee threads gestart. De eerste daarvan, Producer-thread, plaatst berichten uit de berichtenarray in de wachtrij met behulp van de put-methode. De tweede, Consumer, thread leest elementen uit de wachtrij met behulp van de take- methode en geeft deze weer in de console. De volgorde van elementen is de natuurlijke voor de wachtrij.

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();
       }
   }

De uitvoer is de wachtrij in natuurlijke volgorde; de eerste twee elementen verschijnen met een vertraging. Om te versterken wat je hebt geleerd, raden we je aan een videoles van onze Java-cursus te bekijken

Conclusies

• De wachtrij wordt gebruikt om elementen aan het einde van de wachtrij in te voegen en te verwijderen vanaf het begin van de wachtrij. Het volgt het FIFO-concept.
• Java Queue is een onderdeel van het Collection Framework en implementeert de Collection-interface. Het ondersteunt dus alle methoden van de verzamelingsinterface, zoals invoegen, verwijderen enzovoort.
• De meest gebruikte implementaties van Queue zijn LinkedList, ArrayBlockingQueue en PriorityQueue.
• De elementen van de prioriteitswachtrij worden geordend volgens hun natuurlijke ordening, of door een comparator die wordt geleverd tijdens de opbouw van de wachtrij, afhankelijk van welke constructor wordt gebruikt.
• Als een null-bewerking wordt uitgevoerd op BlockingQueues, wordt NullPointerException gegenereerd.