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
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.
|
Download: Schlange.java |
|
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 |