26.5 Der abstrakte Datentyp Schlange (Queue)
 
  Der abstrakte Datentyp Schlange (Warteschlange) ist das Pendant zum Keller. So wie der Keller in der Literatur auch als Stack bekannt ist, so kennt man die Warteschlange auch unter ihrem engl. Namen Queue. So wie der Keller das Prinzip FIFO realisiert, realisiert die Schlange das Prinzip LIFO

Auch hier kennen wir neben dem Konstruktor 4 Operationen

  • Man kann fragen, ob die Schlange leer ist.
  • Man kann etwas in die Warteschlange einfügen.
  • Man kann fragen, was das zuerst eingegebene Etwas einer nicht leeren Schlange ist.
  • Man kann , wenn die Schlange nicht leer ist, das erste Element der Schlange entnehmen, es ist dies das Element, das am längsten in der Schlange ist.

Auch für diese Operationen gibt es standardisierte Bezeichnungen. isEmpty, enqueue, dequeue und head. Wir implementieren diese Operationen als Methoden auf dem abstrakten Datentyp Schlange.
 

isEmpty() Die Methode isEmpty() liefert true, falls die Schlange leer ist, also kein Element enthält und liefert false, falls sie nicht leer ist, also bereits Elemente sich in der Warteschlange befinden.
enqueue(e) Mit der Methode enqueue(e) lassen sich Elemente in die Warteschlange einfügen.
head() Die Methode head(): e gibt den Wert des Elementes der Schlange aus, das sich am längsten in ihr befindet und als nächstes entfernt werden kann.
dequeue() Die Methode dequeue() schließlich entfernt das Element, das sich am längsten in der Schlange befindet.
  In die obere Zeile gibt man die Elemente ein, die man in die Warteschlange einfügen möchte. Die Kommentare werden im unteren Ausgabefeld angezeigt.
Realisierung Wie beim Keller fällt auch hier auf, dass die Schlange-Operationen sich in den Methoden von FIFO wieder finden. Dies lässt sich im folgenden Quelltext leicht nachvollziehen. Wir modellieren also eine Klasse Schlange, in dem wir auf die Klasse FIFO aus dem Paket listen zugreifen.


Abb: 26.8.1 UML-Klassendiagramm Schlange
 

Download:
Schlange.java
package listen.adt;
import listen.*;

public  class Schlange {
  private FIFO fifo;

  public Schlange(){
    fifo = new FIFO();

  public void enqueue(Object wert){
    fifo.haengeAn(wert);
  }

  public void dequeue(){
    fifo.loescheElement();
  }

  public Object head() {
    return fifo.getKopfWert();
  }

  public boolean isEmpty() {
    return fifo.isEmpty();
  }

}
API Wir legen die Klasse Schlange im Paket listen.adt ab. Die KLasse  Schlange.class muss im Verzeichnis adt liegen.
 
zu 26.9 Übungen
zur Startseite www.pohlig.de  (C) MPohlig 2005