Java Queue Interface und seine Implementierungen

Hier werden wir die Java Queue-Schnittstelle besprechen. Sie erfahren, was die Datenstruktur einer Warteschlange ist, wie sie in Java dargestellt wird und welche Methoden für alle Warteschlangen am wichtigsten sind. Außerdem erfahren Sie, welche Implementierungen von Queue in der Java-Sprache vorhanden sind. Anschließend schauen wir uns die wichtigsten Umsetzungen genauer an und lernen sie anhand von Beispielen kennen.

Warteschlangendatenstruktur

Eine Warteschlange ist eine lineare abstrakte Datenstruktur mit der bestimmten Reihenfolge der ausgeführten Operationen – First In First Out (FIFO). Das bedeutet, dass Sie ein Element nur am Ende der Struktur hinzufügen (oder in die Warteschlange einreihen) können und ein Element nur am Anfang übernehmen (aus der Warteschlange entfernen oder aus der Warteschlange entfernen) können. Sie können sich die Datenstruktur der Warteschlange sehr leicht vorstellen. Im wirklichen Leben sieht es aus wie eine Warteschlange oder eine Schlange von Kunden. Der Kunde, der zuerst da war, wird auch zuerst bedient. Wenn bei McDonalds oder anderswo vier Personen in der Schlange stehen, ist derjenige, der als Erster ansteht, auch der Erste, der den Laden betritt. Wenn der neue Kunde kommt, ist er/sie der 5. in der Schlange, um Hamburger zu bekommen. Wenn Sie also mit einer Warteschlange arbeiten, werden neue Elemente am Ende hinzugefügt. Wenn Sie ein Element erhalten möchten, wird es vom Anfang an übernommen. Dies ist das Hauptprinzip der klassischen Warteschlangendatenstrukturarbeit.

Warteschlange in Java

Die Warteschlange in Java ist eine Schnittstelle. Laut Oracle-Dokumentation verfügt die Queue-Schnittstelle über zwei Superschnittstellen, vier verschiedene Schnittstellen, die von der Warteschlange erben, und eine äußerst beeindruckende Liste von Klassen.Was bedeutet das? Erstens ist Java Queue Teil des Collection Framework und implementiert die Collection-Schnittstelle. Daher unterstützt es alle Methoden der Collection-Schnittstelle wie Einfügen, Löschen usw. Queue implementiert eine iterierbare Schnittstelle, die es einem Objekt ermöglicht, das Ziel der „for-each-loop“-Anweisung zu sein.

Warteschlangenmethoden Java

Die Queue deklariert eine Reihe von Methoden. Als Schnittstellenmethoden sollten sie in allen Klassen vertreten sein, die Queue implementieren. Die wichtigsten Queue-Methoden, Java:

• Boolean offer() – fügt ein neues Element in die Warteschlange ein, wenn es möglich ist
• Boolean add(E e) – fügt ein neues Element in die Warteschlange ein, wenn es möglich ist. Gibt im Erfolgsfall „true“ zurück und löst eine IllegalStateException aus, wenn kein Leerzeichen vorhanden ist.
• Objekt poll() – ruft ein Element aus dem Kopf ab und entfernt es. Gibt null zurück, wenn die Warteschlange leer ist.
• Object remove() – ruft ein Element ab und entfernt es aus dem Kopf der Warteschlange.
• Object peek() – ruft ein Element vom Kopf der Warteschlange ab, entfernt es jedoch nicht. Gibt null zurück, wenn die Warteschlange leer ist.
• Objekt element() – ruft ein Element vom Kopf der Warteschlange ab, entfernt es jedoch nicht.

Unterschnittstellen der Java Queue

Die Warteschlangenschnittstelle wird von 4 Unterschnittstellen geerbt – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Sie können sie in drei Gruppen einteilen: Deques, Blocking Queues und Transfer Queues, wobei BlockingDeque zu den beiden ersten gehört. Werfen wir einen Blick auf diese Gruppen.

Deques

Deque bedeutet „Double - Ended Queue “ und unterstützt das Hinzufügen oder Entfernen von einem der Enden der Daten als Warteschlange (First-In-First-Out/FIFO) oder vom Kopf als eine andere beliebte Datenstruktur namens Stack (Last-In-First-Out ) . First-out/LIFO). Klassen, die die Deque-Schnittstelle implementieren: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Blockierende Warteschlangen

Eine blockierende Warteschlange ist eine Warteschlange, die einen Thread in zwei Fällen blockiert:

• Thread versucht, Elemente aus einer leeren Warteschlange abzurufen
• Der Thread versucht, Elemente in die vollständige Warteschlange zu stellen

Wenn ein Thread versucht, Elemente aus einer leeren Warteschlange abzurufen, wartet er, bis ein anderer Thread die Elemente in die Warteschlange stellt. Wenn ein Thread versucht, Elemente in eine volle Warteschlange zu stellen, wartet er entsprechend, bis ein anderer Thread die Elemente aus der Warteschlange nimmt, um freien Speicherplatz für die Elemente zu erhalten. Sicherlich impliziert das Konzept der „vollständigen Warteschlange“, dass die Warteschlange eine begrenzte Größe hat, die normalerweise im Konstruktor angegeben wird. Zu den Standard-Blockierungswarteschlangen gehören LinkedBlockingQueue, SynchronousQueue und ArrayBlockingQueue. Implementierende Klassen der BlockingQueue- Schnittstelle: ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeist eine Unterschnittstelle für BlockingQueue. BlockingDeque wie BlockingQueue ist eine blockierende Warteschlange, jedoch bidirektional. Es erbt also die Eigenschaften der Deque-Schnittstelle. Es ist auf die Multithread-Ausführung ausgerichtet, lässt keine Nullelemente zu und die Kapazität könnte begrenzt sein. Implementierungen der BlockingDeque-Schnittstelle blockieren den Vorgang des Abrufens von Elementen, wenn die Warteschlange leer ist, und des Hinzufügens eines Elements zur Warteschlange, wenn diese voll ist.

Übertragungswarteschlangen

Die TransferQueue-Schnittstelle erweitert die BlockingQueue-Schnittstelle. Im Gegensatz zur Implementierung von BlockingQueue-Schnittstellenwarteschlangen, bei denen Threads blockiert werden können, wenn die Warteschlange leer ist (Lesen) oder wenn die Warteschlange voll ist (Schreiben), blockieren TransferQueue-Schnittstellenwarteschlangen den Schreibstream, bis ein anderer Stream das Element abruft. Nutzen Sie hierfür eine Übertragungsmethode. Mit anderen Worten: Die Implementierung von BlockingQueue garantiert, dass das vom Produzenten erstellte Element in der Warteschlange sein muss, während die Implementierung von TransferQueue garantiert, dass das Producer-Element vom Verbraucher „empfangen“ wird. Es gibt nur eine offizielle Java-Implementierung der TransferQueue-Schnittstelle – LinkedTransferQueue.

Implementierungen von Java-Warteschlangen

Es gibt viele Klassen, die die Queue-Schnittstelle implementieren:

• AbstractQueue Laut Queue Java 8-Dokumenten stellt diese abstrakte Klasse grundlegende Implementierungen einiger Queue-Operationen bereit. Es sind keine Nullelemente zulässig. Es gibt drei weitere Methoden zum Hinzufügen, Entfernen und Element basierend auf dem klassischen Angebot , der Umfrage und dem Peek der Warteschlange. Allerdings lösen sie Ausnahmen aus, anstatt einen Fehler über die Rückgabe „false“ oder „null“ anzuzeigen.
• ArrayBlockingQueue – eine FIFO-Blockierungswarteschlange mit fester Größe, die von einem Array unterstützt wird
• ArrayDeque – anpassbare Array-Implementierung der Deque-Schnittstelle
• ConcurrentLinkedDeque – eine unbegrenzte gleichzeitige Deque basierend auf verknüpften Knoten.
• ConcurrentLinkedQueue – eine unbegrenzte threadsichere Warteschlange basierend auf verknüpften Knoten.
• DelayQueue – eine zeitbasierte Planungswarteschlange, die von einem Heap unterstützt wird
• LinkedBlockingDeque – die gleichzeitige Implementierung der Deque-Schnittstelle.
• LinkedBlockingQueue – eine optional begrenzte FIFO-Blockierungswarteschlange, die von verknüpften Knoten unterstützt wird
• LinkedList – doppelt verknüpfte Listenimplementierung der List- und Deque-Schnittstellen. Implementiert alle optionalen Listenoperationen und lässt alle Elemente zu (einschließlich Null).
• LinkedTransferQueue – eine unbegrenzte TransferQueue basierend auf verknüpften Knoten
• PriorityBlockingQueue – eine unbegrenzte Blockierungsprioritätswarteschlange, die durch einen Heap unterstützt wird
• PriorityQueue – eine Prioritätswarteschlange basierend auf der Heap-Datenstruktur
• SynchronousQueue – eine blockierende Warteschlange, in der jeder Einfügungsvorgang auf einen entsprechenden Entfernungsvorgang durch einen anderen Thread warten muss und umgekehrt.

Die beliebtesten Implementierungen sind LinkedList, ArrayBlockingQueue und PriorityQueue. Schauen wir sie uns an und machen wir zum besseren Verständnis einige Beispiele.

LinkedList

Die Klasse LinkedList in Java implementiert List- und Deque-Schnittstellen. Es handelt sich also um eine Kombination aus List und Deque, einer bidirektionalen Warteschlange, die das Hinzufügen und Entfernen von Elementen auf beiden Seiten unterstützt. In Java ist LinkedList eine doppelt verknüpfte Liste: Jedes Element der Liste ruft Node auf und enthält ein Objekt und Verweise auf zwei benachbarte Objekte – das vorherige und das nächste. Man könnte sagen, dass LinkedList im Hinblick auf die Speichernutzung nicht sehr effektiv ist. Das stimmt, aber diese Datenstruktur kann im Falle der Leistung von Einfüge- und Löschvorgängen nützlich sein. Dies geschieht jedoch nur, wenn Sie dafür Iteratoren verwenden (in diesem Fall erfolgt es in konstanter Zeit). Zugriffsoperationen nach Index werden durchgeführt, indem vom Anfang bis zum Ende (je nachdem, was näher liegt) bis zum gewünschten Element gesucht wird. Vergessen Sie jedoch nicht die zusätzlichen Kosten für die Speicherung von Referenzen zwischen Elementen. Daher ist LinkedList die beliebteste Warteschlangenimplementierung in Java. Es ist ebenfalls eine Implementierung von List und Deque und ermöglicht es uns, eine bidirektionale Warteschlange zu erstellen, die aus beliebigen Objekten einschließlich Null besteht. LinkedList ist eine Sammlung von Elementen.

LinkedList-Konstruktoren

LinkedList() ohne Parameter wird verwendet, um eine leere Liste zu erstellen. LinkedList(Collection<? erweitert E> c) dient zum Erstellen einer Liste, die die Elemente der angegebenen Sammlung enthält, in der Reihenfolge, in der sie vom Iterator der Sammlung zurückgegeben werden.

Wichtigste LinkedList-Methoden:

• add(E-Element) Hängt das angegebene Element an das Ende dieser Liste an;
• add(int index, E element) Fügt das Element am angegebenen Positionsindex ein;
• get(int index) Gibt das Element an der angegebenen Position in dieser Liste zurück;
• remove(int index) Entfernt das Element, das sich an der Position index befindet;
• remove(Object o) Entfernt das erste Vorkommen des ?o-Elements aus dieser Liste, falls es vorhanden ist.
• remove() Ruft das erste Element der Liste ab und entfernt es.
• addFirst(), addLast() fügen ein Element am Anfang/Ende einer Liste hinzu
• clear() entfernt alle Elemente aus der Liste
• enthält(Objekt o) gibt true zurück, wenn die Liste das o-Element enthält.
• indexOf(Object o) gibt den Index des ersten Vorkommens des o-Elements zurück oder -1, wenn es nicht in der Liste enthalten ist.
• set(int index, E element) ersetzt das Element an der Indexposition durch das Element
• size()Gibt die Anzahl der Elemente in der Liste zurück.
• toArray() gibt ein Array zurück, das alle Elemente der Liste vom ersten bis zum letzten Element enthält.
• pop(), das ein Element vom Stapel entfernt (dargestellt durch die Liste)
• push(E e), das ein Element auf den Stapel schiebt (dargestellt durch diese Liste)

Beispiel für eine Java-Warteschlange – LinkedList (Elemente auf unterschiedliche Weise einfügen und entfernen)

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

Prioritätswarteschlange

PriorityQueue ist nicht genau die Warteschlange im allgemeinen Sinne von FIFO. Die Elemente der Prioritätswarteschlange werden entsprechend ihrer natürlichen Reihenfolge oder durch einen Komparator geordnet, der zum Zeitpunkt der Warteschlangenerstellung bereitgestellt wird, je nachdem, welcher Konstruktor verwendet wird. Es handelt sich jedoch nicht um eine Reihenfolge, wie sie in einer linearen Struktur wie einer Liste vorliegen könnte (vom Größten zum Kleinsten oder umgekehrt). Eine Prioritätswarteschlange basierend auf einem Prioritäts-Mindestheap. Heap ist eine Datenstruktur, die auf einem Binärbaum basiert. Die Priorität jedes Elternteils ist höher als die Prioritäten seiner Kinder. Ein Baum heißt vollständiger Binärbaum, wenn jeder Elternteil nicht mehr als zwei Kinder hat und die Füllung der Ebenen von oben nach unten erfolgt (von derselben Ebene aus von links nach rechts). Der binäre Heap organisiert sich jedes Mal neu, wenn ein neues Element hinzugefügt oder daraus entfernt wird. Im Falle eines Min-Heaps wird das kleinste Element unabhängig von der Reihenfolge seiner Einfügung in die Wurzel verschoben. Die Prioritätswarteschlange basiert auf diesem Min-Heap. Wenn wir also eine PriorityQueue mit ganzen Zahlen haben, ist ihr erstes Element die kleinste dieser Zahlen. Wenn Sie die Wurzel löschen, wird die nächstkleinere zur Wurzel.

Wichtigste PriorityQueue-Methoden:

• boolean add(object) fügt das angegebene Element in die Prioritätswarteschlange ein. Gibt im Erfolgsfall true zurück. Wenn die Warteschlange voll ist, löst die Methode eine Ausnahme aus.
• boolean offer(object) fügt das angegebene Element in diese Prioritätswarteschlange ein. Wenn die Warteschlange voll ist, gibt die Methode false zurück.
• boolean „remove(object)“ entfernt eine einzelne Instanz des angegebenen Elements aus dieser Warteschlange, sofern es vorhanden ist.
• Das Objekt poll() ruft den Kopf dieser Warteschlange ab und entfernt ihn. Gibt null zurück, wenn die Warteschlange leer ist.
• void clear() entfernt alle Elemente aus der Prioritätswarteschlange.
• Das Objekt element() ruft den Kopf dieser Warteschlange ab, ohne ihn zu entfernen. Löst eine NoSuchElementException aus, wenn die Warteschlange leer ist.
• Das Objekt peek() ruft den Kopf der Warteschlange ab, ohne ihn zu entfernen. Gibt null zurück, wenn die Warteschlange leer ist.
• boolean contains(Object o) gibt true zurück, wenn die Warteschlange das o-Element enthält.
• int size() gibt die Anzahl der Elemente in dieser Warteschlange zurück.

Beispiel für 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

Es ist wichtig zu verstehen, dass Prioritätswarteschlangen auf binären Heaps basieren, sodass sie Elemente nicht in linearer Sortierreihenfolge halten. Jeder Weg von der Wurzel bis zum Blatt ist geordnet, die verschiedenen Wege von der Wurzel jedoch nicht. Das bedeutet, dass Sie sehr schnell das minimale Element der Warteschlange erhalten können. Wenn Sie den Kopf jedes Mal löschen, wird eine sortierte Struktur gedruckt.

ArrayBlockingQueue

Interne Datenstruktur von ArrayBlockingQueuebasiert auf einem kreisförmigen Array zum Speichern von Elementen. Es handelt sich um eine typische Warteschlange (FIFO) für den Fall, dass neue Elemente am Ende der Warteschlange eingefügt werden und Extraktionsvorgänge ein Element vom Kopf der Warteschlange zurückgeben. Die einmal erstellte Warteschlangenkapazität kann nicht mehr geändert werden. Versuche, ein Element in eine volle Warteschlange einzufügen (zu platzieren), führen zur Blockierung des Flusses; Der Versuch, ein Element aus einer leeren Warteschlange zu übernehmen, blockiert ebenfalls den Thread. Wie bereits erwähnt, ist dieses Array kreisförmig. Das bedeutet, dass das erste und das letzte Element des Arrays logisch benachbart behandelt werden. Die Warteschlange erhöht die Indizes der Kopf- und Schwanzelemente jedes Mal, wenn Sie das Elemento in die Warteschlange stellen oder aus der Warteschlange entfernen. Wenn ein Index das letzte Element des Arrays vorrückt, beginnt es bei 0 neu. Daher gilt: Die Warteschlange muss nicht alle Elemente verschieben, wenn der Kopf entfernt wird (wie im üblichen Array). Wenn jedoch ein Element aus der Mitte entfernt wird (mit Iterator.remove), werden die Elemente verschoben. ArrayBlockingQueue unterstützt eine zusätzliche Fairness-Richtlinie mit Fair- Parametern im Konstruktor, um die Arbeit der wartenden Abläufe von Produzenten (Elemente einfügen) und Konsumenten (Elemente extrahieren) zu ordnen. Standardmäßig ist die Bestellung nicht garantiert. Wenn die Warteschlange jedoch mit „fair == true“ erstellt wird, stellt die Implementierung der ArrayBlockingQueue-Klasse Thread-Zugriff in FIFO-Reihenfolge bereit. Eigenkapital reduziert in der Regel die Bandbreite, reduziert aber auch die Volatilität und verhindert, dass Ressourcen knapp werden.

Konstruktoren der ArrayBlockingQueue-Klasse

• ArrayBlockingQueue (int Capacity) erstellt eine Warteschlange mit fester Kapazität und einer Standardzugriffsrichtlinie.
• ArrayBlockingQueue (int Capacity, boolean fair) erstellt eine Warteschlange mit einer festen Kapazität und einer angegebenen Zugriffsrichtlinie.
• ArrayBlockingQueue (int Capacity, boolean fair, Collection <? erweitert E> c) erstellt eine Warteschlange mit einer durch die Zugriffsrichtlinie angegebenen festen Kapazität und schließt Elemente in die Warteschlange ein.

Hier haben wir das BlockingQueueExample-Beispiel. Wir erstellen eine Warteschlange der ArrayBlockingQueue mit einer Kapazität von einem Element und einem Fair-Flag. Zwei Threads werden gestartet. Der erste von ihnen, der Producer-Thread, stellt Nachrichten aus dem Nachrichten-Array mithilfe der Put-Methode in die Warteschlange. Der zweite Thread, Consumer, liest mithilfe der Take -Methode Elemente aus der Warteschlange und zeigt sie in der Konsole an. Die Reihenfolge der Elemente ist die natürliche für die Warteschlange.

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

Die Ausgabe ist die Warteschlange in natürlicher Reihenfolge; Die ersten beiden Elemente erscheinen mit Verzögerung. Um das Gelernte zu vertiefen, empfehlen wir Ihnen, sich eine Videolektion aus unserem Java-Kurs anzusehen

Schlussfolgerungen

• Die Warteschlange wird verwendet, um Elemente am Ende der Warteschlange einzufügen und am Anfang der Warteschlange zu entfernen. Es folgt dem FIFO-Konzept.
• Java Queue ist Teil des Collection Framework und implementiert die Collection-Schnittstelle. Daher unterstützt es alle Methoden der Collection-Schnittstelle wie Einfügen, Löschen usw.
• Die am häufigsten verwendeten Implementierungen von Queue sind LinkedList, ArrayBlockingQueue und PriorityQueue.
• Die Elemente der Prioritätswarteschlange werden entsprechend ihrer natürlichen Reihenfolge oder durch einen Komparator geordnet, der zum Zeitpunkt der Warteschlangenerstellung bereitgestellt wird, je nachdem, welcher Konstruktor verwendet wird.
• Wenn eine Nulloperation für BlockingQueues ausgeführt wird, wird eine NullPointerException ausgelöst.