Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

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.

Struktur einer Schlange

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

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:

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.

Objektdiagramm einer Schlange

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.

Klassendiagramm einer Schlange

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.

Verbesserte Modellierung einer Schlange - Objektdiagramm

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.

Verbesserte Modellierung einer Schlange - Klassendiagramm

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.

X

Fehler melden

X

Suche