Lektion 29:Die Klasse StackAsFixedVectorWir schreiben uns jetzt die erste Containerklasse. Der abstrakte Datentyp Stack bietet sich an, weil er so einfach ist. Das Anhängsel "AsFixedVector" soll aussagen, wie der Stack implementiert ist. "Vector" ist ein anderes Wort für "Array", so wie "Array" in C++ verstanden wird. "FixedVector" sagt aus, daß die Größe des Vectors zur Laufzeit nicht verändert werden kann. Eine andere übliche Implementierung ist StackAsLinkedList. Der StackAsFixedVector ist schnell und speicherplatzsparend, hat aber den Nachteil, daß man die maximale Größe des Stacks bereits vorher kennen muß. Der StackAsLinkedList ist langsamer, kann aber beliebig groß werden. Der StackAsLinkedList wird die erste Anwendung einer verketteten Liste werden, doch dazu später mehr. Als Werte, die in diesem Stack gespeichert werden können, wähle ich den Typ int. Außerdem werden in der Klasse Stack alle Bezeichner englisch sein. Nicht, weil es notwendig wäre, sondern weil es üblich ist. Der Stack hat die Methoden:
Damit ergibt sich bereits dieser Code:
Soweit ist der Code für alle Stack-Klassen gleich. Wir sagen: Dies ist die Schnittstelle der Klasse. Die Schnittstelle besteht aus allen Methoden und Attributen, die public sind. (Attribute sollten nicht public sein, d.h. sie sollten nicht Teil der Schnittstelle sein.) Als zugrundeliegende Struktur, um die Daten zu speichern, wählen wir ein Array. Also wird der Stack ein Array als Attribut bekommen. Dazu müssen wir uns noch überlegen, wie groß das Array sein soll. Ich wähle willkürlich als Größe 5 aus:
Der Stack beinhaltet jetzt also ein Array der Größe 5. Die Fragezeichen sollen andeuten, daß die Werte der Array-Elemente noch nicht bekannt sind: 0 1 2 3 4 ----- ----- ----- ----- ----- ¦ ? ¦ ¦ ? ¦ ¦ ? ¦ ¦ ? ¦ ¦ ? ¦ ----- ----- ----- ----- ----- Damit allein läßt sich noch nicht viel anfangen. Es wird noch ein Attribut benötigt, das angibt, welches der 5 Array-Elemente das oberste ist. Das Attribut heißt topIndex und bezeichnet den Index des obersten Elements.
Wir betrachten einen Stack, in den schon die Zahlen 8, 5 und 7 in dieser Reihenfolge eingefügt wurden. Der topIndex wird als Pfeilchen dargestellt. Im Beispiel hat er den Wert 2. 0 1 2 3 4 ----- ----- ----- ----- ----- ¦ 8 ¦ ¦ 5 ¦ ¦ 7 ¦ ¦ ? ¦ ¦ ? ¦ ----- ----- ----- ----- ----- ^ Von dieser Darstellung ausgehend können wir jetzt die Methoden implementieren. Zunächst die einfachste Methode:
Die Methode top würde jetzt die 7 ausgeben. Und gleich die nächste Methode:
Nach Aufruf dieser Methode pop sieht der Stack so aus: 0 1 2 3 4 ----- ----- ----- ----- ----- ¦ 8 ¦ ¦ 5 ¦ ¦ 7 ¦ ¦ ? ¦ ¦ ? ¦ ----- ----- ----- ----- ----- ^ Das oberste Element ist jetzt die 5. Daß die 7 noch an ihrem Platz ist, stört nicht. Es hätte keinen Sinn, sie mit irgend einem Wert, z.B. der 0, zu überschreiben. Zur Übung führen wir gleich noch einmal die Methode pop aus: 0 1 2 3 4 ----- ----- ----- ----- ----- ¦ 8 ¦ ¦ 5 ¦ ¦ 7 ¦ ¦ ? ¦ ¦ ? ¦ ----- ----- ----- ----- ----- ^ Würde jetzt ein push(4) ausgeführt werden, dann müßte topIndex um eins nach rechts rücken, und dort müßte die 4 hineingeschrieben werden: 0 1 2 3 4 ----- ----- ----- ----- ----- ¦ 8 ¦ ¦ 4 ¦ ¦ 7 ¦ ¦ ? ¦ ¦ ? ¦ ----- ----- ----- ----- ----- ^ Das läßt sich so bewerkstelligen:
Jetzt hat der Stack zwei Elemente. Um jetzt festzustellen, woran man erkennt, daß der Stack leer ist, entnehmen wir mit pop einfach diese beiden Elemente: Erster Aufruf von pop: 0 1 2 3 4 ----- ----- ----- ----- ----- ¦ 8 ¦ ¦ 4 ¦ ¦ 7 ¦ ¦ ? ¦ ¦ ? ¦ ----- ----- ----- ----- ----- ^ Zweiter Aufruf von pop: -1 0 1 2 3 4 ----- ----- ----- ----- ----- ----- ¦ ? ¦ ¦ 8 ¦ ¦ 4 ¦ ¦ 7 ¦ ¦ ? ¦ ¦ ? ¦ ----- ----- ----- ----- ----- ----- ^ Es existiert gar kein Array-Element an der Stelle -1. Wenn jetzt jemand diesen Wert mit der Methode top auslesen möchte, dann ist nicht definiert, was passiert. Mit ein wenig Pech wird das Programm mit einer Schutzverletzung (das, wenn Windows Programme mit der Meldung 'Allgemeine Schutzverletzung' beendet) abgebrochen. Damit das nicht passiert existiert die Methode empty. Sie liefert true, wenn der topIndex den Wert -1 hat (sie ist eigentlich nur ein anderen Name für topIndex==-1).
Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern. [aktuelle Version] [inhalt] [index] [Fehlerkorrektur, Verbesserungsvorschlag] © Volkard Henkel <volkard@normannia.de>, last update: 08/25/00 |