Fachkonzept - Stapel

Stapel

Stapel kennst du aus dem täglichen Leben: Tellerstapel, Bücherstapel, .... Wir gehen im Beispiel davon aus, dass wir Bücher als Stapel organisieren wollen.

Die entscheidenden Eigenschaften eines Stapels sind:

• Man hat (in der Regel) nur auf das oberste Stapelobjekt einen direkten Zugriff.
• Man legt (in der Regel) ein neues Stapelobjekt oben auf den Stapel.
• Man nimmt (in der Regel) das oberste Stapelobjekt weg.
• Das letzte hinzugefügte Stapelelement ist das erste, das weggenommen wird.

Stapel als Datentyp

Ein Stapel ist eine Datenstruktur, die als Behälter für Datenobjekte dient und nach dem LIFO-Prinzip (last in, first out) arbeitet.

Folgende Stapeloperationen werden normalerweise zur Verarbeitung eines Stapels zur Verfügung gestellt:

• isEmpty(): prüft, ob der Stapel leer ist
• top(): liefert das oberste Datenobjekt (sofern der Stapel nicht leer ist)
• push(Buch b): legt das übergebene Datenobjekt oben auf den Stapel
• pop(): liefert das oberste Stapelobjekt und entfernt es aus dem Stapel (sofern der Stapel nicht leer ist)

Modellierung

Man kann einen Stapel auf ganz unterschiedliche Weise modellieren und implementieren. Eine Möglichkeit besteht darin, ein Stapel-Objekt zu nutzen, das die Methoden zur Manipulation des Stapels zur Verfügung stellt. Das Stapel-Objekt kennt das oberste Buch. Jedes Buch auf dem Stapel kennt das darunter liegende Buch.

Zusätzlich zu den Attributen, die Objekte vom Typ Buch haben, benötigen diese noch ein Attribut, um die Referenz next auf das darunter liegende Objekt zu speichern. Im Klassendiagramm ergibt sich dadurch eine Beziehung zwischen Buch und Buch. Man nennt eine Beziehung zwischen Objekten des gleichen Datentyps eine reflexive Beziehung oder rekursive Beziehung.

Die obige Modellierung besitzt die Schwäche, dass sie nicht direkt in anderen Projekten wiederverwendet werden kann, da der Datentyp Buch in der Klasse Stapel angepasst werden muss. Außerdem benötigen Elemente des Datentyps Buch ein zusätzliches Attribut, das zu deren eigentlicher Modellierung nicht passt. Wenn man beispielsweise ein Buch modellieren wollte, würde man nicht auf die Idee kommen, dass ein Buch seinen Nachfolger kennen soll. Erst im Kontext eines Stapels 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 Stapel-Klasse und sind dafür verantwortlich, die zu verwaltenden Objekte nicht unnötig aufzublähen.

Der Stapel 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 beschrieben.