4.4Queues (Schlangen) und Deques 
In der Klassenbibliothek von Java gibt es die Schnittstelle java.util.Queue für Datenstrukturen, die nach dem FIFO-Prinzip (für engl. first in, first out) arbeiten. Die verwandte Datenstruktur ist der Stack, der nach dem Prinzip LIFO (für engl. last in, first out) arbeitet. Eine Deque bietet Methoden für die FIFO-Verarbeitung an beiden Enden über eine Schnittstelle java.util.Deque, die direkt java.util.Queue erweitert.
Abbildung 4.3Queue- und Deque-Schnittstellen
4.4.1Queue-Klassen
Die Schnittstelle Queue erweitert Collection und ist somit auch vom Typ Iterable. Zu den Klassen, die Queue implementieren, gehört unter anderem LinkedList:
Listing 4.11com/tutego/insel/util/queue/QueueDemo.java, main()
queue.offer( "Fischers" );
queue.offer( "Fritze" );
queue.offer( "fischt" );
queue.offer( "frische" );
queue.offer( "Fische" );
queue.poll();
queue.offer( "Nein, es war Paul!" );
while ( ! queue.isEmpty() )
System.out.println( queue.poll() );
Die Operationen sind:
extends Collection<E>
boolean empty()
E element()
boolean offer(E o)
E peek()
E poll()
E remove()
Auf den ersten Blick sieht es so aus, als ob es für das Erfragen zwei Methoden gibt: element() und peek(). Doch der Unterschied besteht darin, dass element() eine NoSuchElementException auslöst, wenn die Queue kein Element mehr liefern kann, peek() jedoch null bei leerer Queue liefert. Da null als Element erlaubt ist, kann peek() das nicht detektieren; die Rückgabe könnte für das null-Element oder als Anzeige für eine leere Queue stehen. Daher ist peek() nur sinnvoll, wenn keine null-Elemente vorkommen, was aber in der Regel erfüllt ist.
Gefüllt werden kann die Queue mit der von Collection geerbten Methode add(…) oder durch die neue Methode offer(…). Der Unterschied: Im Fehlerfall löst add(…) eine Exception aus, während offer(…) durch die Rückgabe false anzeigt, dass das Element nicht hinzugefügt wurde. Tabelle 4.2 macht den Zusammenhang deutlich:
Mit Ausnahme | Ohne Ausnahme | |
|---|---|---|
Einfügen | add(…) | offer(…) |
Erfragen | element() | peek() |
Löschen | remove() | poll() |
Tabelle 4.2Operationen von Queue mit Ausnahmen und ohne
4.4.2Deque-Klassen
Eine Deque (gesprochen »Deck«) bietet Queue-Operationen an beiden Enden an. Die Operationen schreibt eine Schnittstelle Deque vor.
Deque-API
Da es jeweils die Queue-Operationen an beiden Enden gibt, erscheint die Schnittstelle erst einmal groß, was sie aber im Prinzip nicht ist.
Erstes Element (Kopf) | Letztes Element (Schwanz) | |||
|---|---|---|---|---|
Ausnahme im Fehlerfall | Besondere Rückgabe | Ausnahme im Fehlerfall | Besondere Rückgabe | |
Einfügen | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
Löschen | removeFirst() | pollFirst() | removeLast() | pollLast() |
Entnehmen | getFirst() | peekFirst() | getLast() | peekLast() |
Tabelle 4.3Operationen der Datenstruktur Deque
»Besondere Rückgabe« in der Tabelle bedeutet, dass etwa getFirst()/getLast() eine Ausnahme auslösen, wenn die Deque leer ist, aber peekFirst()/peekLast() die Rückgabe null liefern.
[zB]Beispiel
Die Methode removeLast() eignet sich gut dafür, die Datenstruktur auf eine gewisse Anzahl an Elementen zu beschränken. Nehmen wir an, eine Liste soll maximal zehn Elemente aufnehmen, dann können wir beim Einfügen eines neuen Elements schreiben:
searches.removeLast();
Deque-Implementierungen
Von der Schnittstelle gibt es drei Implementierungen:
ArrayDeque: Wie der Namensbestandteil »Array« schon andeutet, sitzt hinter dieser Realisierung ein Feld, das die Deque beschränken kann.
LinkedList: Einer LinkedList ist diese Beschränkung fremd; sie kann beliebig wachsen.
LinkedBlockingDeque: Realisiert BlockingDeque als blockierende Deque, was weder ArrayDeque noch LinkedList machen.
4.4.3Blockierende Queues und Prioritätswarteschlangen
Die Schnittstelle java.util.concurrent.BlockingQueue erweitert die Schnittstelle java.util. Queue. Implementierende Klassen blockieren, falls eine Operation wie take() aufgrund fehlender Daten nicht durchgeführt werden konnte. Die Konsumenten/Produzenten sind mit diesen Klassen ausgesprochen einfach zu implementieren.
Spannende Queue-Klassen (und speziellere BlockingQueue-Klassen) sind:
ConcurrentLinkedQueue: threadsichere Queue, durch verkettete Listen implementiert
DelayQueue: Queue, der die Elemente erst nach einer gewissen Zeit entnommen werden können
ArrayBlockingQueue: Queue mit einer maximalen Kapazität, abgebildet auf ein Feld
LinkedBlockingQueue: unbeschränkte oder beschränkte Queue (also mit maximaler Kapazität), abgebildet durch eine verkettete Liste
PriorityQueue: Hält in einem Heap-Speicher Elemente sortiert und liefert bei Anfragen das jeweils größte Element. Wie beim TreeSet müssen die Elemente entweder Comparable implementieren, oder es muss ein Comparator angegeben werden. Unbeschränkt.
PriorityBlockingQueue: wie PriorityQueue, nur blockierend
SynchronousQueue: Eine blockierende Queue zum Austausch von genau einem Element. Wenn ein Thread ein Element in die Queue setzt, muss ein anderer Thread auf dieses Element warten, andernfalls blockiert die Datenstruktur den Ableger. Erwartet ein Thread ein Element, ohne dass ein anderer Thread etwas in die Queue gesetzt hat, blockiert sie ebenfalls den Holer. Durch diese Funktionsweise benötigt die SynchronousQueue keine Kapazität, denn Elemente werden, falls platziert, direkt konsumiert und müssen nicht zwischengelagert werden.
Die PriorityXXX-Klassen implementieren im Gegensatz zu den übrigen kein FIFO-Verhalten.
4.4.4PriorityQueue
Eine Prioritätswarteschlange ist eine Datenstruktur, die vergleichbar wie ein SortedSet die Elemente sortiert. Wenn etwa Nachrichten in ein System kommen, sind diese in der Regel nicht alle gleich wichtig, sondern unterscheiden sich in ihrer Priorität. Elemente höherer Priorität sollen zuerst verarbeitet werden. Das Fundament bildet eine Queue mit einem modifizierten FIFO-Prinzip, das deswegen nicht nur pur FIFO ist (»Wer zuerst kommt, mahlt zuerst«), weil Elemente, die schon am Anfang stehen, von später kommenden Elementen mit höherer Priorität verdrängt werden können.
PriorityQueue ist eine Implementierung einer solchen Prioritätswarteschlange. Damit die Priorisierung möglich ist, müssen die Elemente eine natürliche Sortierung besitzen (String oder Wrapper-Objekte haben diese zum Beispiel), oder ein Comparator muss angegeben werden. PriorityQueue verbietet das null-Element, und Elemente dürfen durchaus doppelt vorkommen (wie eine Liste); daher kann auch SortedSet nicht die Aufgabe einer Prioritätswarteschlange übernehmen, da eine Menge Elemente nur einmal enthalten kann.
Bleibt die Frage, ob Elemente hoher Priorität vorne oder hinten stehen, denn das beeinflusst die Implementierung. Eine Queue hat einen Kopf, und dort steht das kleinste Element. Das ist entgegen der Intuition, denn wir sprechen immer von »hoher Priorität«, nur bei der Datenstruktur ist es so, dass sich die hohe Priorität in »kleiner in der Ordnung« übersetzt. Sehr anschaulich zeigt es das nächste Beispiel, in dem wir einige Integer-Objekte in die PriorityQueue einsortieren; da Integer die Schnittstelle Comparable implementiert, ist dadurch eine natürliche Ordnung gegeben.
Listing 4.12com/tutego/insel/util/queue/PriorityQueueDemo.java, main()
q.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8, 1 ) );
System.out.println( q ); // [1, 2, 1, 9, 3, 8, 3]
System.out.println( q.remove() ) ; // 1
System.out.println( q ); // [1, 2, 3, 9, 3, 8]
System.out.println( q.remove() ) ; // 1
System.out.println( q ); // [2, 3, 3, 9, 8]
System.out.println( q.remove() ) ; // 2
System.out.println( q ); // [3, 8, 3, 9]
System.out.println( q.remove() ) ; // 3
System.out.println( q.remove() ) ; // 3
System.out.println( q.remove() ) ; // 8
System.out.println( q ); // [9]
System.out.println( q.remove() ) ; // 9
System.out.println( q ); // []
Beim Entnehmen mit remove() liefert die PriorityQueue immer das kleinste Element und entfernt es aus der Sammlung. Wichtig ist zu verstehen, dass der Iterator über die Elemente (anschaulich durch toString()) keine sortierte Sammlung zeigt – daher darf eine PriorityQueue nicht als sortiertes Set gesehen werden, sondern eben als java.util.Queue, bei der nur Anfrage-Operationen am Kopf erlaubt sind. Dass dabei zum Beispiel die 9 vor der 8 steht, ist ein Interna, das zwar irgendwie interessant, aber für den Entwickler irrelevant ist, da nur Kopfoperationen wie element(), remove(), peek(), poll(), remove() erlaubt sind. Während das kleinste Element entnommen und entfernt wird, sortiert sich die interne Datenstruktur um, wobei dies auch die Reihenfolge der 8 und 9 in unserem Beispiel verändert, aber hier dringt nur die interne Arbeitsweise nach außen, die uns nicht interessiert.
Comparator für wichtige Strings
Um mit der Klasse PriorityQueue und den Vergleichen warm zu werden, wollen wir mit einem Comparator beginnen, der allen Zeichenketten mit den Wörtern »wichtig«, »important« und »sofort« eine höhere Priorität einräumt als anderen Zeichenketten. In die Rückgabe eines Comparator übersetzt, bedeutet das, dass die höher priorisierten Zeichenketten »kleiner« als die Zeichenketten ohne Signalwörter sind. Ein s1 = "Wichtig! Essen ist fertig" ist damit kleiner als s2 = "Bier ist kalt!", und ein compare(s1, s2) würde –1 liefern.
Listing 4.13com/tutego/insel/util/queue/ImportanceComparator.java, main()
import java.util.Comparator;
import java.util.regex.Pattern;
class ImportanceComparator implements Comparator<String> {
private static final Pattern IMPORTANT_PATTERN =
Pattern.compile( "(?i)(wichtig|important|sofort)" );
@Override public int compare( String s1, String s2 ) {
boolean isS1Important = IMPORTANT_PATTERN.matcher( s1 ).find(),
isS2Important = IMPORTANT_PATTERN.matcher( s2 ).find();
// Wenn beide Strings wichtig oder beide Strings unwichtig sind,
// dann ist die Rückgabe 0.
if ( isS1Important == isS2Important )
return 0; // wichtigkeit(s1) == wichtigkeit(s2)
// Andernfalls ist einer der Strings wichtig und der andere unwichtig
if ( isS1Important )
return –1; // wichtigkeit(s1) > wichtigkeit(s2) -> s1 < s2
// else if ( isS2Important )
return +1; // wichtigkeit(s2) > wichtigkeit(s1) -> s1 > s2
}
}
Die Pattern-Klasse aus dem regex-Paket hilft uns bei der Frage, ob ein Teil-String im String vorkommt. Der Vorteil der Pattern-Klasse ist, dass sie den Code für die Abfrage reduziert, denn andernfalls müssten wir dreimal mit equalsIgnoreCase(…) arbeiten.
Die Funktionalität vom Comparator testet ein kleines Beispielprogramm:
Listing 4.14com/tutego/insel/util/queue/ImportanceComparatorDemo.java, main()
String s1 = "Schönes Wetter heute.";
String s2 = "Chices Kleid!";
// Beides nicht wichtig, daher ist das Ergebnis 0
System.out.println( comp.compare( s1, s2 ) ); // 0
String s3 = "Sofort nach den Blumen schauen!";
// Zweiter String wichtiger als der erste String
System.out.println( comp.compare( s1, s3 ) ); // 1
// Erster String wichtiger als der zweite String
System.out.println( comp.compare( s3, s1 ) ); // –1
String s4 = "Wichtig! An Lakritz denken!";
// Beide Strings gleich wichtig
System.out.println( comp.compare( s3, s4 ) ); // 0
List<String> list = new ArrayList<>();
Collections.addAll( list, s1, s2, s3, s4, s1 );
System.out.println( list );
Collections.sort( list, comp );
System.out.println( list );
Das Beispielprogramm endet mit einer Liste, die nach der Sortierung mit dem Comparator folgende Ausgabe liefert:
Chices Kleid!, Schönes Wetter heute.]
Die wichtigen Zeichenketten stehen vorne in der Liste. Dort stehen sie genau richtig, damit die Prioritätswarteschlange sie direkt abholen kann.
Wichtige Meldungen in der Prioritätswarteschlange
Für die Prioritätswarteschlange ist das Element mit der höchsten Priorität das wichtigste und steht vorne, am Kopf.
Listing 4.15com/tutego/insel/util/queue/ImportancePriorityQueue.java, main()
// PriorityQueue<String> queue = new PriorityQueue<>( 11, comp );
PriorityQueue<String> queue = new PriorityQueue<>( comp ); // Java 8
queue.add( "Schönes Wetter heute." );
System.out.println( queue );
// [Schönes Wetter heute.]
queue.add( "Sofort nach den Blumen schauen!" );
System.out.println( queue );
// [Sofort nach den Blumen schauen!, Schönes Wetter heute.]
queue.add( "Chices Kleid!" );
System.out.println( queue );
// [Sofort nach den Blumen schauen!, Schönes Wetter heute., Chices Kleid!]
queue.remove();
System.out.println( queue );
// [Chices Kleid!, Schönes Wetter heute.]
queue.add( "Wichtig! An Lakritz denken!" );
System.out.println( queue );
// [Wichtig! An Lakritz denken!, Schönes Wetter heute., Chices Kleid!]
Im Konstruktor von PriorityQueue geben wir Comparator an, der für die Vergleiche herangezogen wird und die Elemente an den Kopf setzt.
Bemerkung
Bei unserer Implementierung kann es passieren, dass Elemente in der Queue verhungern, wenn sich wichtigere Elemente immer vorschieben.
extends AbstractQueue<E>
implements Serializable
PriorityQueue()
Erzeugt eine neue PriorityQueue mit der Anfangsgröße von elf Elementen. Die Elemente werden nach ihrer natürlichen Ordnung sortiert.PriorityQueue(Collection<? extends E> c)
Erzeugt eine neue PriorityQueue, die mit den Elementen aus c vorkonfiguriert wird. Die Elemente werden nach ihrer natürlichen Ordnung sortiert.PriorityQueue(int initialCapacity)
Erzeugt eine neue PriorityQueue mit der Anfangsgröße initialCapacity. Die Elemente werden nach ihrer natürlichen Ordnung sortiert. Die Initialkapazität ist eine Größenabschätzung, die für die Performanz bei vielen Elementen wichtig ist.PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
Erzeugt eine neue PriorityQueue mit der Anfangsgröße initialCapacity. Die Elemente werden mit einem Comparator verglichen.PriorityQueue(Comparator<? super E> comparator)
Erzeugt eine neue PriorityQueue mit der Anfangsgröße von elf Elementen. Die Elemente werden mit einem Comparator verglichen.PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)
Erzeugt eine neue PriorityQueue, die mit den Elementen aus c vorkonfiguriert wird. Die Sortiereigenschaft, entweder natürlich oder mit einem Comparator, wird aus der übergebenen PriorityQueue bzw. dem SortedSet übernommen.
Die Klasse PriorityQueue übernimmt die Operationen aus der Schnittstelle Queue und fügt nur eine neue Methode hinzu:
Comparator<? super E> comparator()
Liefert den Comparator der PriorityQueue oder null, falls die natürliche Ordnung verwendet wird.
Wichtig zu wissen ist, dass die Elemente entweder eine natürliche Ordnung haben müssen oder sich ein Comparator um die Vergleiche kümmern muss – der Comparator kann später nicht mehr verändert werden! Daher gibt es auch nur eine comparator()-Methode zum Holen, aber das Zuweisen eines Comparator geschieht immer nur einmal im Konstruktor.
