3.5 Queues (Schlangen) und Deques

In der Klassenbibliothek von Java gibt es die Schnittstelle java.util.Queue für Datenstrukturen, die nach dem FIFO-Prinzip (First in, First out) arbeiten. Die verwandte Datenstruktur ist der Stack, der nach dem Prinzip LIFO (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 3.7: Queue- und Deque-Schnittstellen

3.5.1 Queue-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 3.11: com/tutego/insel/util/queue/QueueDemo.java, main()

Queue<String> queue = new LinkedList<String>();

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:

interface java.util.Queue<E>
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. Gefüllt wird die Liste statt mit add() – was durch Collection zur Verfügung stünde – mit 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. Die folgende Tabelle macht den Zusammenhang deutlich:

3.5.2 Deque-Klassen

Ein Deque (gesprochen »Deck«) bietet Queue-Operationen an beiden Enden an. Die Operationen schreibt eine Schnittstelle Deque vor. Da es jeweils die Queue-Operationen an beiden Enden gibt, erscheint die Schnittstelle erst einmal groß, was sie aber im Prinzip nicht ist.

»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.

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.

3.5.3 Blockierende Queues und Prioritätswarteschlangen

Die Schnittstelle java.util.concurrent.BlockingQueue erweitert die Schnittstelle java.util. Queue. Klassen, die BlockingQueue implementieren, 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 (und speziellere BlockingQueue)-Klassen sind:

• ConcurrentLinkedQueue: Thread-sichere 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: Queue beschränkt oder 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.

3.5.4 PriorityQueue

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 Ganzzahlen in die PriorityQueue einsortieren.

Listing 3.12: com/tutego/insel/util/queue/PriorityQueueDemo.java, main()

PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );
System.out.println( queue );  // [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  // [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  // [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  // [3, 8, 9]
queue.remove();
System.out.println( queue );  // [8, 9]
queue.remove();
System.out.println( queue );  // [9]
queue.remove();
System.out.println( queue );  // []

An der Ausgabe ist zu erkennen, dass die PriorityQueue zwar das kleinste Element richtig an der vordersten Stelle enthält, dass aber der Iterator über die Elemente (anschaulich durch toString()) keine sortierte Sammlung zeigt. Daher steht bei zwei Ausgaben auch die 9 vor der 8. Während dann das erste Element immer entnommen und entfernt wird, sortiert sich die interne Datenstruktur um, wobei dies auch die Reihenfolge der 8 und 9 verändert.

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 3.13: com/tutego/insel/util/queue/ImportanceComparator.java, main()

package com.tutego.insel.util.queue;

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 Teilstring 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 3.14: com/tutego/insel/util/queue/PriorityComparatorDemo.java, main()

ImportanceComparator comp = new ImportanceComparator();

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

[Sofort nach den Blumen schauen!, Wichtig! An Lakritz denken!, Schönes Wetter heute., 
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 3.15: com/tutego/insel/util/queue/ImportancePriorityQueue.java, main()

ImportanceComparator comp = new ImportanceComparator();
PriorityQueue<String> queue = new PriorityQueue<String>( 11, comp );

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!]

Der PriorityQueue fehlt leider ein Konstruktor, der ausschließlich den Comparator entgegennimmt. So müssen wir eine Initialkapazität angeben, eine Größenabschätzung, die für die Performanz bei vielen Elementen wichtig ist.

class java.util.PriorityQueue<E>
extends AbstractQueue<E>
implements Serializable

• PriorityQueue()
  Erzeugt eine neue PriorityQueue mit der Anfangsgröße von 11 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.
• PriorityQueue(int initialCapacity)
  Erzeugt eine neue PriorityQueue mit der Anfangsgröße initialCapacity. Die Elemente werden nach ihrer natürlichen Ordnung sortiert.
• PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
  Erzeugt eine neue PriorityQueue mit der Anfangsgröße initialCapacity. 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.

Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.