Home

Vorlesung Informatik 2 - Teil B: Theorie

3.3 Java Klassen für Stack und Queue

In Java gibt es fertige Klassen für Stack und Queue:

java.util.Stack<T>:
    push(x:T):T
    pop():T
    peek():T
    size(): int
    empty(): boolean

Für Warteschlangen gibt es das Interface Queue:

interface Queue<T>
   offer(x:T) boolean                          add(x:T): boolean                                    
   poll(): T                                   remove(): T    
   peek(): T                                   element() T          
geben null/false zurück                    werfen eine Exception     
Die Methode add/remove/element reagieren mit einem Fehler (Exception), wenn die Operation nicht erlaubt ist, z.B. remove aus einer leeren Queue. 

Die Methoden in der rechten Spalte melden keinen Fehler, sondern geben einfach null oder false zurück.

 
Eine einfache Implementierung von Queue ist die Klasse LinkedList, man kann also z.B. schreiben: 

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

Wie wir bei unseren Implementierungen schon gesehen haben, gibt es mehrere Arten von Queue, deshalb hat man zunächst die abstrakte Klasse AbstractQueue eingeführt. Sie hat die abstrakten Methoden offer/poll/peek  sowie die fertigen Methoden add/remove/element welche offer/poll/peek rufen.

Von AbstractQueue abgeleitet gibt es die folgenden Klassen:

  • ArrayBlockingQueue: eine begrenzte und blockierende Warteschlange, die mit einem Array implementiert ist.
  • DelayQueue: eine blockierende Warteschlange, die nur nach einer bestimmten Zeit wieder ein Element aufnimmt.
  • PriorityQueue: eine Warteschlange mit Elementen unterschiedlicher Priorität, die in der Reihenfolge ihrer Priorität herausgegeben werden. Prioritätswarteschlangen implementiert man als Heap, das ist ein spezieller Baum den wir erst später kennenlernen werden.
  • PriorityBlockingQueue: eine blockierende Prioritätswarteschlange begrenzter Länge.
  • ConcurrentLinkedQueue:  eine Queue auf Basis einer verketteten Liste, die von verschiedenen Threads benutzt werden kann (thread-safe).
  • SynchronousQueue: eine blockierende Warteschlange, die auf einen anderen Thread wartet, d.h. Elemente können erst eingefügt werden wenn ein anderer Thread sie entfernen will. Sie erleichtern das Synchronisieren von parallel laufenden Threads.

Lehrvideo  (YouTube)