11.5 Queues (Schlangen)
 
In der Klassenbibliothek von Java gibt es seit Java 5 eine Schnittstelle java.util.Queue für FIFO-Datenstrukturen. Die Schnittstelle erweitert Collection und ist somit auch vom Typ Iterable.
interface java.util. Queue<E>
extends Collection<E>
|
|
boolean empty() |
|
E element() |
|
boolean offer( E o ) |
|
E peek() |
|
E poll() |
|
E remove() |
Zu den Klassen, die Queue implementieren, gehört auch LinkedList.
Listing 11.5
QueueTest.java
import java.util.*;
public class QueueTest
{
public static void main( String[] args )
{
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() );
}
}
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 stehen würde – 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:
|
Mit Ausnahme
|
Ohne Ausnahme
|
Einfügen
|
add()
|
offer()
|
Erfragen
|
element()
|
peek()
|
Löschen
|
remove()
|
poll()
|
11.5.1 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() auf Grund fehlender Daten nicht durchgeführt werden konnte. Die Konsumenten/Produzenten sind mit diesen Klassen ausgesprochen einfach zu implementieren.
Spannende Queue-Klassen sind:
|
ConcurrentLinkedQueue. Thread-sichere Queue durch verkettete Listen implementiert. |
|
DelayQueue. Queue, aus 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 maximalen Kapazität, abgebildet durch eine verkettete Liste. |
|
PriorityQueue. Hält Elemente sortiert und liefert bei Anfragen das jeweils kleinste Element. Vergleichbar mit 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, in der nur ein Element eingefügt werden kann. |
|
Die Priority-Klassen implementieren im Gegensatz zu den übrigen kein FIFO-Verhalten: first in first out. |
|