Warteschlange

Bei den meisten Menschen weckt das Wort „Warteschlange“ kaum angenehme Assoziationen. Aber heute sprechen wir über andere Warteschlangen – Java-Warteschlangen. In Java ist eine Warteschlange alles, was die Queue- Schnittstelle erbt, was wiederum die Collection- Schnittstelle erweitert. Das bedeutet, dass Warteschlangen wie Sammlungen behandelt werden können.

Warteschlangen in Java unterstützen zwei Funktionsprinzipien: FIFO und LIFO .

Das FIFO- Prinzip (First In, First Out) regelt eine reguläre Warteschlange – das erste Element, das der Warteschlange hinzugefügt wird, ist das erste, das sie verlässt.

Das LIFO- Prinzip (Last In, First Out) beschreibt das Verhalten eines Stapels – das letzte Element, das der Warteschlange hinzugefügt wird, verlässt sie als erstes. So arbeiten Sie beispielsweise mit einem Kartenspiel: Sie nehmen eine Karte nach der anderen von der Oberseite, bis Sie das untere Ende des Kartenspiels erreichen.

Die Warteschlangenhierarchie in Java sieht folgendermaßen aus:

Hier sehen Sie, dass Queue drei Implementierungsklassen hat: LinkedList , ArrayDeque und PriorityQueue . LinkedList und ArrayDeque erben direkt nicht Queue , sondern Deque .

Deque ist eine Schnittstelle, die in Java 6 hinzugefügt wurde. Sie enthält mehrere Methoden, die für Warteschlangen nützlich sind, und ermöglicht es einer Warteschlange, als doppelendige (oder bidirektionale) Warteschlange zu fungieren. Das heißt, es kannFIFOundLIFO.

Einer der beiden Nachkommen der Deque- Schnittstelle ist ArrayDeque . Es unterstützt eine doppelendige Warteschlange, mit der Sie Elemente an beiden Enden einfügen und entfernen können. Es handelt sich außerdem um ein dynamisches Array, dessen Größe automatisch zunimmt.

Es gibt auch eine PriorityQueue- Klasse, die ein direkter Nachkomme von Queue ist : Sie verhält sich anders als die Klassen, die Deque implementieren .

PriorityQueue ist eine Prioritätswarteschlange, die Elemente standardmäßig gemäß ihrer natürlichen Reihenfolge organisiert. Hier verwendet die Sortierung die Schnittstellen Comparable und Comparator . Das Prinzip ist dasselbe wie bei TreeSet oder TreeMap – Klassen, die die Comparable- Schnittstelle verwenden und über eine eigene Sortierreihenfolge verfügen.

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

Wenn Sie dieses Beispiel ausführen, sehen Sie Folgendes in der Konsole:

Da wir mit Warteschlangen und nicht mit regulären Sammlungen arbeiten, müssen wir die Elemente aus der Liste entfernen. Dazu verwenden wir dieses Konstrukt:

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

Die Deque- Schnittstelle erbt die Queue- Methoden und fügt mehrere eigene interessante Methoden hinzu:

Schauen wir uns nun einige dieser Methoden in der Praxis an.

Fügen wir zunächst ein Element zu einer Warteschlange hinzu:

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

Lassen Sie uns nun Werte aus einer Warteschlange abrufen:

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

    }

Dieser Code zeigt das erste und letzte Element der Warteschlange an.

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

Wenn wir diesen Code ausführen, erhalten wir:

Der Unterschied zwischen pop() und poll() besteht darin, dass pop() eine NoSuchElementException auslöst, wenn die Liste leer ist, poll() jedoch null zurückgibt .

Nun betrachten wir die Methoden pollFirst() und 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);

Beide Methoden geben einen Wert zurück und entfernen ihn aus der Warteschlange.

Hier ist ein Beispiel für die Verwendung der Methoden peekFirst() und 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);

Beide Methoden geben das erste/letzte Element aus der Warteschlange zurück und entfernen es nicht. Wenn die Warteschlange leer ist, wird null zurückgegeben.

Gut gemacht! Heute haben wir gelernt, wie man in Java mit Warteschlangen arbeitet. Jetzt wissen Sie, wie Sie sie in der Praxis anwenden können.