Home > Informatik > Stufe Q1 > Referenzen

15.2 Ein dynamischer Stack

Allgemeines - dynamischer Stack - sortierte Liste - NRW-Liste - doppelt verkettete Liste

Die Grundidee

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

Wir wollen in diesem Abschnitt nun den ADT Stack mit Hilfe von Referenzen implementieren. Dazu erst mal ein kleines Bild:

Ein dynamischer Stack mit 2 Elementen: tos --> 28 --> 61

Eine Variable namens tos zeigt auf das "oberste" Element des Stack. Dieses Element besteht aus zwei Komponenten:

  1. dem eigentlichen Inhalt, hier einer int-Zahl
  2. einer Referenz / einem Zeiger auf das nächste Stack-Element

Die Referenz wird in dem Bild durch einen Pfeil dargestellt.

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

Implementation in Java

Betrachten wir nun eine einfache Implementierung des ADT Stack in Java, die Gebrauch von Referenzen macht.

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

Die Methode push entwickeln wir zunächst mithilfe eines Kästchenschemas:

Die push()-Operation als Kästchen-Schema
Schritt 0

Schritt 0 stellt die Ausgangssituation dar: Bereits zwei Elemente x1 und x2 befinden sich in dem Stack. Dabei wurde x1 zuerst gepusht, x2 danach. Der Zeiger tos verweist also auf x2.

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 unserem Bild wird das Objekt x durch x3 repräsentiert. Der next-Zeiger von x3 zeigt zunächst auf null.

Schritt 2

Der next-Zeiger des neuen obersten Elementes wird auf das bisherige 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 x2. Jetzt muss er auf das neue "oberste" Element x3 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:

Zeigerumbiegen bei der pop()-Methode

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 kann kein Attribut next besitzen. Bei einem leeren Stack würde diese  also zu einem Laufzeitfehler führen. 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;
    }
Übung 15.2-1 (PC, 3 Punkte)

Schreiben Sie selbst ein Testprogramm, dass den hier vorgestellten dynamischen Stack auf Herz und Nieren testet. Alle Methoden müssen mehrmals ausprobiert werden, und mit dem Objekt-Inspektor oder einer eigenen show-Methode können Sie sich den Stack nach jeder Operation anschauen, ob er auch tatsächlich so aufgebaut ist, wie er theoretisch sein sollte.

2 Punkte für ein Testprogramm ohne eigene show-Methode,

3 Punkte für ein Testprogramm mit einer eigenen show-Methode für den Stack.

 
Übung 15.2-2 (PC, 7 Punkte)

Implementieren Sie auf ähnliche Weise eine dynamische Queue (4 Punkte) und schreiben Sie ein entsprechendes Testprogramm ohne / mit eigener show-Methode (2 / 3 Punkte).

Weiter mit einer dynamischen Liste...