15.2 Ein dynamischer Stack

Die Grundidee

In der Folge 14 hatten wir Abstrakte Datentypen (ADTs) kennengelernt, unter anderem den für das Abitur in NRW wichtigen ADT Stack. Wir hatten diesen ADT dann mit Hilfe eines Arrays implementiert.

Wir wollen in diesem Abschnitt nun den ADT Stack mit Hilfe von Referenzen implementieren. Das Grundprinzip einer solchen dynamischen Implementierung machen wir uns mit dem folgenden Bild einmal klar:

Ein dynamischer Stack mit zwei Elementen
Autor: Ulrich Helmich, Lizenz: siehe Seitenende.

Die Abbildung zeigt einen dynamischen Stack, also einen Stack, der nicht mit Hilfe eines statischen Arrays implementiert ist, sondern mit Zeigern.

Die Abbildung ist eine Momentaufnahme des Stacks nachdem folgende Operationen auf den Stack ausgeführt worden sind:

1. Init()
2. Push(61)
3. Push(28)

Eine Variable namens tos zeigt auf das zuletzt Eingefügte Element 28 des Stacks. Bei der Array-Implementation bestandt dieses Stack-Element aus einer "Zelle" eines Arrays, die Variable tos verwaltete dann den Index des "obersten" Elementes.

Bei der dynamischen Zeiger-Implementation verwaltet die Variable tos dagegen die Speicheradresse des obersten Stack-Elements. Der genaue Inhalt von tos ist in der Abbildung nicht mit angegeben, es handelt sich aber um eine achtstellige Hexadezimalzahl, die eine Stelle in dem ca. 4 Gigabyte großem Speicher adressiert. Mit

System.out.println(tos);

könnte man sich diese Adresse in der Konsole auch anzeigen lassen.

Wie sind nun die einzelnen Stack-Element in dem Speicher des Rechners organisiert? Schauen wir uns die beiden "Kästchen" in der Abbildung einmal näher an. Jedes Stack-Element besteht aus zwei Komponenten:

1. dem eigentlichen Inhalt, hier einer int-Zahl (28, 61).
2. einem Zeiger auf das nächste Stack-Element.

Dieser Zeiger, der meistens die Bezeichnung next hat, ist nichts anderes als eine Variable, die eine hexadezimale Speicheradresse wie 45d28aff enthält, nämlich die Adresse des nächsten Stack-Elements. Zeiger werden in einem solchen Kästchenschema in der Regel durch gerade oder gebogene Pfeile dargestellt.

Das nachfolgende Element des Stacks ist genauso aufgebaut: Wieder besteht die erste Komponente aus dem eigentlichen Wert(hier 61), und die zweite Komponente ist eine Referenz auf das nächste Stack-Element. Da dieses nicht existiert, hat next hier den Wert null.

Der Wert null ist nicht mit der Zahl 0 zu verwechseln. Die Angabe null heißt so viel wie: "Es existiert noch kein Speicherplatz, an dem die Daten zu finden" sind oder "Es wurde noch kein Speicherplatz für diese Daten reserviert".

Wir wollen nun einmal die Push()-Operation durchspielen und ein drittes Element in den vorhandenen Stack einführen. Die beiden bereits vorhandenen Elemente bezeichnen wir jetzt einmal ganz allgemein als x₁ und x₂, wobei x₂ zuletzt mit Push() eingefügt wurde.

Schritt 0

Hier sehen wir die Ausgangssituation: Der Stack besteht aus den beiden Elementen x₁/next und x₂/next, und der Zeiger tos zeigt auf das "oberste" bzw. zuletzt hinzugefügte Element x₂/next.

Schritt 1

Es wird ein neues Stack-Element x₃/next erzeugt, das zunächst völlig unabhängig vom bereits vorhandenen Stack ist.

Ein neuer Zeiger neu zeigt auf das neue Element, und der next-Zeiger dieses neuen Elementes hat den Wert null, zeigt also ins "Nirgendwo".

Schritt 2

Nun wird der next-Zeiger von x₃/next auf das "oberste" Element des alten Stacks gesetzt. Das kann durch eine einfache Zuweisung wie

neu.next = tos;

geschehen. Beide Variablen enthalten Speicheradressen, und daher kann die in tos stehende Adresse ohne Probleme in die Variable neu hineinkopiert werden.

Schritt 3

Das neue Element ist nun mit dem alten Stack verbunden, es befindet sich an "oberster" Stelle. Der tos-Zeiger dagegen verweist noch auf das alte oberste Element x₂. Durch eine Zuweisung wie

tos = neu;

wird der Stack nun aktualisiert, so dass tos auf das zuletzt zugefügte Element x₃ zeigt.

Damit haben wir schon Einiges über eine mögliche Implementation des dynamischen Stacks in einer beliebigen Programmiersprache gelernt. Schauen wir uns nun eine konkrete Implementation in Java an, die Gebrauch von Referenzen macht.

Implementation in Java

public class Stack
{
    public class Knoten
    {
       Object wert;
       Knoten next;
       
       public Knoten(Object w)
       {
          wert = w;
          next = null;
       }
    }
    
    private Knoten tos;
    
    public Stack()
    {
        tos = null;
    }
    
    public boolean isEmpty()
    {
       return (tos == null);
    }
    
    public void push(Object x)
    {
        Knoten neu = new Knoten(x);
        neu.next = tos;
        tos = neu;
    }
    
    public void pop()
    {
       if (!isEmpty())
          tos = tos.next;
    }
    
    public Object top()
    {
       if (!isEmpty())
          return tos.wert;
       else
          return null;
    }
}

Untersuchen wir nun die einzelnen Methoden genauer. Vorher wollen wir uns aber die Klasse Knoten anschauen, die lokal in der Klasse Stack implementiert wurde - so etwas ist in Java durchaus möglich. Andere Klassen können dann allerdings nicht auf die Klasse Knoten zugreifen.

Die Klasse Knoten

    public class Knoten
    {
       Object wert;
       Knoten next;
       
       public Knoten(Object w)
       {
          wert = w;
          next = null;
       }
    }

Objekte der Klasse Knoten bestehen (wie bereits oben weiter erläutert) aus zwei Komponenten:

1. dem eigentlichen Wert, hier einem Objekt wert der Klasse Object
2. einer Referenz next auf den Nachfolger-Knoten

Methoden hat diese Klasse nicht, nur den einen Konstruktor. Als Parameter nimmt dieser Konstruktor nur die eigentlichen Daten entgegeben (Object w).

Der Konstruktor Stack()

    private Knoten tos;
    
    public Stack()
    {
        tos = null;
    }

Das Attribut tos ist von zentraler Bedeutung für den Stack. Es zeigt ständig auf das oberste Stack-Element. Das erklärt ja auch den Namen: "tos" steht für "top of stack". Wenn ein neuer Stack erzeugt wird, zeigt tos noch auf keine spezielle Stelle des Speichers, daher ist die Zuweisung

   tos = null;

sinnvoll. Mehr muss der Konstruktor nicht leisten.

Die sondierende Methode isEmpty()

Der Quelltext, um festzustellen, ob der Stack leer ist, ist recht einfach:

    public boolean isEmpty()
    {
       return (tos == null);
    }

Das Ergebnis des Vergleichs tos == null wird als Wert zurückgeliefert, entweder true oder false.

Die manipulierende Methode push()

Über diese Methode haben wir bereits weiter oben in der "Einleitung" gesprochen. Wir wollen uns jetzt aber die konkrete Implementation näher anschauen.

Schritt 1

Es wird ein neues Stack-Element angelegt, und zwar mit dem Befehl

Knoten neu = new Knoten(x);

Der Parameter x wird einfach an den Konstruktor von Knoten weitergereicht. In der Abbildung 2 wird das Objekt x durch x₃ repräsentiert. Der next-Zeiger von x₃ zeigt zunächst auf null.

Schritt 2

Der next-Zeiger des neuen Elementes wird auf das bisherige zuletzt hinzugefügte ("oberste") Element "umgebogen", und zwar durch den Befehl

neu.next = tos;

Schritt 3

Der tos-Zeiger zeigt immer noch auf das alte "oberste" Element, also auf x₂. Jetzt muss er auf das neue "oberste" Element x₃ umgebogen werden:

tos = neu;

Das war's. So einfach kann man die push()-Methode gestalten, wenn man mit Zeigern bzw. Referenzen arbeitet.

Letzter Test

Hat man einen solchen Quelltext entwickelt, muss man noch testen, ob er wirklich für alle denkbaren Fälle arbeitet. Was ist beispielsweise, wenn der Stack noch leer ist?

public void push(Object x)
{
   Knoten neu = new Knoten(x);
   neu.next = tos;
   tos = neu;
}

Auch hier muss zunächst ein neuer (erster) Knoten erzeugt werden; die erste Zeile kann also so bleiben, wie sie ist. Dann wird der next-Zeiger des neuen Knotens auf den Wert von tos gesetzt. Bei einem leeren Stack hatte tos den Wert null, und wenn der Stack ein einziges Element enthält, zeigt der next-Zeiger dieses Elementes ebenfalls auf null. Also muss auch die zweite Zeile nicht verändert werden.

Schließlich muss tos immer auf das zuletzt hinzugefügte Element zeigen. Diese Vorgabe wird durch die dritte Zeile auch dann erfüllt, wenn der Stack vorher leer war.

Fazit: Die eben entwickelte push()-Methode funktioniert auch dann, wenn der Stack leer ist.

Die manipulierende Methode pop()

Schauen Sie sich zunächst den Quelltext an:

    public void pop()
    {
       if (!isEmpty())
          tos = tos.next;
    }

Rein theoretisch könnte man ja einfach den Zeiger tos auf das nächste Stack-Element setzen:

Das Bild veranschaulicht, warum man hier auch von "Zeigerumbiegen" spricht. Allerdings funktioniert die Anweisung

tos = tos.next;

nicht, wenn der Stack leer ist. Dann hat tos nämlich den Wert null, und eine Referenz mit dem Wert null zeigt auf keinen Speicherbereich. Daher kann tos auch kein Attribut next referenzieren. Bei einem leeren Stack würde diese  also zu einem Laufzeitfehler führen, und das Programm könnte abstürzen. Daher muss immer vorher geprüft werden, ob der Stack leer ist. Wenn der Stack nämlich leer ist, muss pop() überhaupt nichts machen.

Die sondierende Methode top()

Auch hier müssen wir sicherstellen, dass der Stack nicht leer ist, denn ein tos-Zeiger, der auf null zeigt, kann kein Attribut wert haben:

    public Object top()
    {
       if (!isEmpty())
          return tos.wert;
       else
          return null;
    }

Übungen