Fachkonzept - Schlange

Warteschlangen

Warteschlangen kennst du aus dem täglichen Leben: vor der Kinokasse, .... Wir gehen im Folgenden Beispiel von einer Warteschlange von Kunden an einer Kinokasse aus.

Warteschlangen werden auch zur Verwaltung von Daten benutzt. Die entscheidenden Eigenschaften einer solchen Datenwarteschlange sind:

• Man hat (in der Regel) nur auf das erste Schlangenelement einen direkten Zugriff.
• Ein neues Schlangenelement wird (in der Regel) hinten angefügt.
• Man nimmt (in der Regel) das erste Schlangenelement weg.
• Das erste hinzugefügte Schlangenelement ist auch das erste, das weggenommen wird.

Schlange als Datentyp

Eine Schlange ist eine Datenstruktur, die als Behälter für Datenobjekte dient und nach dem FIFO-Prinzip (first in, first out) arbeitet.

Folgende Schlangenoperationen werden normalerweise zur Verarbeitung einer Schlange zur Verfügung gestellt:

• isEmpty(): liefert zurück, ob die Schlange leer ist
• first(): liefert das erste Schlangenelement (sofern die Schlange nicht leer ist)
• add(e): hängt das übergebene Element hinten an die Schlange an
• remove(): entfernt das erste Schlangenelement (sofern die Schlange nicht leer ist) und gibt es zurück

Modellierung

Man kann eine Warteschlange sehr ähnlich einem Stapel- modellieren und implementieren. Das Schlangen-Objekt stellt Methoden zum Zugriff auf die Schlange zur Verfügung und kennt das vorderste Objekt der Schlange. Jedes Schlangenobjekt kennt das nachfolgende Objekt.

Zusätzlich zu den Attributen, die Objekte vom Typ Kunde haben, benötigen diese noch ein Attribut, um die Referenz next auf das dahinter befindliche Objekt zu speichern. Im Klassendiagramm ergibt sich dadurch eine reflexive Beziehung Beziehung zwischen Kunde und Kunde.

Die obige Modellierung besitzt die Schwäche, dass sie nicht direkt in anderen Projekten wiederverwendet werden kann, da der Datentyp Kunde in der Klasse Schlange angepasst werden muss. Außerdem benötigen Elemente des Datentyps Kunde ein zusätzliches Attribut, das zu deren eigentlicher Modellierung nicht passt. Wenn man beispielsweise einen Kunden modellieren wollte, würde man nicht auf die Idee kommen, dass ein Kunde seinen Nachfolger kennen soll. Erst im Kontext einer Schlange wird diese Eigenschaft erforderlich.

Wenn es gewünscht ist, die Modellierung und damit die Implementierung wiederverwendbar zu machen, kann man eine zusätzliche Schicht von Elementen einfügen. Diese gehören logisch zur Schlange-Klasse und sind dafür verantwortlich, die zu verwaltenden Objekte nicht unnötig aufzublähen.

Die Schlange kann damit Objekte einer beliebigen Klasse verwalten. Da die Klasse Object in Java Oberklasse aller anderen Klassen ist, kann Object als gemeinsamer Datentyp benutzt werden.

Die Modellierung ist somit unabhängig von den zu verwaltenden Objekten. Die Implementierung kann folglich in anderen Projekten ohne Änderungen wiederverwendet werden. Man erkauft sich die erhöhte Flexibilität hier mit einer komplexeren Modellierung.

Möchte man den verbesserten Entwurf in Java umsetzen, bietet es sich an generische Klassen und eventuell auch innere Klassen zu verwenden. Wie dies funktioniert ist im Exkurs - Generische und innere Klassen des Projekts Keep or throw beschrieben.