Lektion 29:

Die Klasse StackAsFixedVector

  Wir 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:

void push(int i) // ein Element oben drauflegen
int top() // das oberste Element lesen
void pop() // das oberste Element entfernen
bool empty() // ist der Stack leer?

Damit ergibt sich bereits dieser Code:

class StackAsFixedVector
{
public:
   void push(int i); // ein Element oben drauflegen
   int top(); // das oberste Element lesen
   void pop(); // das oberste Element entfernen
   bool empty(); // ist der Stack leer?
};

 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:

const int STACK_SIZE=5;
class StackAsFixedVector
{
private:
   int data[STACK_SIZE];
public:
   void push(int i); // ein Element oben drauflegen
   int top(); // das oberste Element lesen
   void pop(); // das oberste Element entfernen
   bool empty(); // ist der Stack leer?
};

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.

const int STACK_SIZE=5;
class StackAsFixedVector
{
private:
   int data[STACK_SIZE];
   int topIndex;
public:
   void push(int i); // ein Element oben drauflegen
   int top(); // das oberste Element lesen
   void pop(); // das oberste Element entfernen
   bool empty(); // ist der Stack leer?
};

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:

   int top() // das oberste Element lesen
   {
      return data[topIndex];
   };

Die Methode top würde jetzt die 7 ausgeben.

Und gleich die nächste Methode:

   void pop() // das oberste Element entfernen
   {
      topIndex=topIndex-1;
   };

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:

   void push(int i) // ein Element oben drauflegen
   {
      topIndex=topIndex+1;
      data[topIndex]=i;
   };

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).

   bool empty() // ist der Stack leer?
   {
      return 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