14.3 Der ADT Stack

Inhalt

Das LIFO-Prinzip

Ein Stack bzw. Stapel arbeitet nach dem LIFO-Prinzip: Last in, first out. Das Element, das zuletzt eingefügt wurde, wird als erstes wieder entfernt.

Ein anschauliches Beispiel für einen solchen Stack ist ein Tellerstapel in der Kantine. Die Studenten legen ihre benutzten Teller oben auf den Stapel. Der volle Stapel wird in die Küche gefahren und dann von oben her wieder abgebaut.

Ein Stapel Teller
Photo: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

Der ADT Stack wird durch folgende Operationen definiert:

Diese fünf Operationen beschreiben die Arbeitsweise eines Stacks vollständig. Veranschaulichen wir uns die Arbeitsweise der Stack-Operationen:

Arbeitsweise der Stack-Operationen
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

• Nach Aufruf der Init() -Operation ist der Stack zwar vorhanden, aber er enthält noch keine Elemente, er ist leer.
  Stellen Sie sich einfach einen leeren und sehr schmalen Einkaufskorb vor, in dem Sie die Artikel nicht nebeneinander legen können, sondern übereinander stapeln müssen. Der Korb ist vorhanden, aber leer.
• Nach Aufruf von Push(12) enthält der Stack genau ein Element, nämlich die Zahl 12.
• Nach Aufruf von Push(8) sind schon zwei Elemente im Stack enthalten. Die 8 wurde zuletzt zugefügt.
• Nach Push(17) befinden sich drei Element im Stack, die 17 ist das zuletzt zugefügte Element.
  Wenn man sich einen solchen Stack anschaulich als Stapel vorstellt, befindet sich die 17 jetzt "oben" im Stack, also als "oberstes" Element, während die 12 das "unterste" Element ist. Die abstrakte Definition des ADT Stack verlangt aber nicht nach einer solchen anschaulichen Darstellung, von "oben" und "unten" ist hier nicht die Rede.
• Wenn Pop() aufgerufen wird, wird die 17 wieder entfernt - sie war ja die zuletzt zugefügte Zahl.
• Nach dem Aufruf von Empty() verändert sich der Stack nicht, allerdings wird der Wert FALSE zurück geliefert, denn der Stack ist ja noch nicht leer.
• Wenn Top() aufgerufen wird, verändert sich der Stack ebenfalls nicht. Aber der Inhalt des zuletzt zugefügten ("obersten") Stackelements wird zurück geliefert.
• Wenn nochmals Pop() aufgerufen wird, enthält der Stack nur noch das Element 12.
• Nach Push(5) besteht der Stack wieder aus zwei Elementen. Die 5 wurde zuletzt gepusht, also findet sie sich "oben" im Stack wieder.

2. Grundsätzliche Überlegungen zur Implementierung ^Top

Im Informatik-Unterricht wird eigentlich zuerst immer die Möglichkeit besprochen, den ADT Stack mit Hilfe eines Arrays zu implementieren. Das ist die einfachste und schnellste Möglichkeit, hat aber auch den Nachteil, dass ein Array eine statische Datenstruktur ist, deren Größe vor dem Compilieren festgelegt werden muss. Hat der Array also eine Größe von 100 Elementen, können Sie auch nur maximal 100 Elemente speichern und nicht 102 oder 200.

Implementation über einen Array

Ein Array kann alle möglichen Datenobjekte speichern, nicht nur int- oder double-Zahlen, sondern auch Strings, andere Arrays oder sogar Objekte anderer Klassen. Aber man soll ja die Sache einfach anfangen, daher beschränken wir uns zunächst auf einen Array namens stapel, der 100 int-Zahlen speichern kann, und zwar so, dass der Benutzer dieses Arrays den Eindruck hat, einen Stack vor sich zu haben.

stapel = new int[100];

Wie könnte ein solcher Array aussehen, nachdem fünf Zahlen mit dem push()-Befehl abgespeichert worden sind. Betrachten wir dazu das folgende Bild:

Der Stack nach Ausführung der Operationen push(23), push(15), push(78), push(35), push(99).
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

Das Bild veranschaulicht die Push() -Operation bzw. den push()-Befehl unserer Stack-Klasse.

Nach dem Erzeugen des neuen int-Arrays stapel sind die Arrayelemente mit lauter Nullen gefüllt, wie man mit Hilfe des Objektinspektors von BlueJ leicht überprüfen kann.

Nach Ausführung der fünf push()-Befehle sind die ersten fünf Elemente (0..4) des Arrays mit den entsprechenden Werten belegt. Die zuletzt hinzugefügte Zahl befindet sich an fünfter Stelle im Array, hat also den Index 4. Diese Zahl 4 wird auch in dem Attribut tos der Klasse Stack bzw. des Objektes stapel gespeichert, das quasi als "Zeiger" auf das oberste Stackelement angesehen werden kann.

Der Stack nach Ausführung der zusätzlichen Operation push(18)
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

Wenn eine weitere Zahl - hier die 18 - gepusht wird, wird sie in das nächste freie Arrayelement geschrieben, und tos wird um 1 inkrementiert (sofern nicht bereits das Ende des Arrays erreicht ist).

Also bitte aufpassen: tos hat nicht den Wert 18, sondern den Wert 5, nämlich den Index des "obersten" Stack-Elements. An diesem Index befindet sich dann der eigentliche Wert des Stack-Elementes, nämlich 18.

Der Stack nach Ausführung der Operationen pop()
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

Wenn jetzt die Operation Pop() bzw. die Methode pop() aufgerufen wird, passiert nichts Spektakuläres. Es reicht, wenn tos dekrementiert wird. Ein Löschen des rechten Stack-Elements (18) zum Beispiel durch Überschreiben mit einer Null ist nicht nötig.

Angenommen, als Nächstes wird die Operation Top() aufgerufen, welche den Wert des obersten Stack-Elementes zurückliefert. Dann wird einfach nachgeschaut, auf welches Arrayelement tos zeigt. Da tos den Wert 4 hat und somit auf die 99 verweist, wird von Top() auch der korrekte Wert 99 zurückgeliefert. Dass rechts neben der 99 eine 18 steht, interessiert überhaupt nicht und hat keine Auswirkungen auf den Ablauf der Operationen.

Der Stack nach einer zweiten pop()-Operation
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

Jetzt wurde Pop() ein zweites Mal aufgerufen. Der Zeiger tos wird noch einmal dekrementiert, und alle Werte, die rechts von tos stehen, sind völlig uninteressant.

Jetzt wird push(28) aufgerufen
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

Wenn jetzt Push(28) aufgerufen wird, schreibt die Push() -Operation den Wert 28 in das Arrayelement, das sich rechts von tos befindet. Egal, was vorher in diesem Arrayelement stand, wird der alte Wert überschrieben. Die 18 rechts neben tos interessiert nicht; Top() liefert den korrekten Wert 28 zurück.

3. Die Implementierung im Detail ^Top

public class Stack
{
   private int[] stapel;
   private int   tos;

   public Stack()
   {
      stapel = new int[100];
      tos   = -1; 
   }

   public void push(int x)
   {
      if (tos < 99)
      {
         tos++;
         stapel[tos] = x;
      }  
   }

Hier sehen wir den Java-Quelltext einer Klasse Stack mit den Attributen, dem Konstruktor und der Methode push() .

Ein Stack ist zwar ein abstrakter Datentyp, aber letzten Endes muss er mit Hilfe von konkreten Datentypen und Datenstrukturen implementiert werden, anders geht es nicht. In unserem Beispiel wurde der ADT Stack mit Hilfe des Arrays stapel (einer Datenstruktur ) und der int-Variablen tos (einem primitiven Datentyp ) implementiert. Am Anfang ist der Array leer, nach dem ersten Aufruf von push() enthält er genau ein Element und so weiter.

Es ist dabei wichtig, den Überblick über die Anzahl der "tatsächlichen" Arrayelemente zu behalten. Durch die Initialisierung des Arrays mit

stapel = new int[100];

passen zwar 100 Elemente in den Array, dies ist aber nur die maximale Zahl, die untergebracht werden kann. Das Attribut tos speichert dagegen die tatsächliche Anzahl der enthaltenen Elemente und gleichzeitig den Index des "obersten" Stack-Elementes.

Da der Stack am Anfang leer ist, müsste tos in dem Konstruktor eigentlich auf den Wert 0 gesetzt werden. Nun ist es aber so, dass das erste Arrayelement auch den Index 0 hat - das ist halt das Dumme bei Arrays.

Die Anweisung tos = 0 würde also bedeuten, dass das Element mit dem Index 0 bereits einen Wert besitzt. Der Stack wäre damit also nicht leer. Aus diesem Grund wurde in dem obigen Quelltext tos mit dem Wert -1 initialisiert. Damit sollte eindeutig klar sein, dass der Stack noch leer ist und dass auch das Element mit dem Index 0 noch nicht belegt ist.

Die push-Methode im Detail

Schauen wir uns nun die push -Methode genauer an:

public void push(int x)
{
   if (tos < 99)
   {
      tos++;
      stapel[tos] = x;
   }  
}

Alternativ wäre folgende Kurzform der Methode möglich:

public void push(int x)
{
   if (tos < 99)
      stapel[++tos] = x;
}

Durch das Voransetzen des ++ - Operators wird tos zuerst inkrementiert, erst dann wird dem Arrayelement stapel[tos] der Wert von x zugewiesen. Durch die Beschränkung auf eine Anweisung entfallen dann auch die beiden Klammern in der if-Anweisung.

Am Anfang ist der Stack leer, tos hat den Wert -1. Nun wird eine Zahl gepusht, zum Beispiel die 23. Die Bedingung tos < 99 ist erfüllt, also wird tos inkrementiert, hat jetzt den Wert 0. In dem Arrayelement mit dem Index 0 wird nun die erste Zahl, die 23, gespeichert.

Beim Speichern der nächsten Zahl ist die Bedingung tos < 99 immer noch erfüllt, also wird tos inkrementiert, hat dann den Wert 1. Im Arrayelement mit dem Index 1, also im zweiten Arrayelement, wird dann die zweite Zahl gespeichert, die 15.

Und so geht das weiter, bis der Array voll ist. Angenommen, von den hundert Arrayelementen sind alle belegt, und es soll eine weitere Zahl gepusht werden. Die "oberste" Zahl befindet sich jetzt in dem Arrayelement mit dem Index 99, also in dem letzten Arrayelement. Entsprechend hat tos den Wert 99. Die Bedingung   tos < 99 ist damit nicht mehr erfüllt, und das Speichern wird abgebrochen.

Die pop-Methode

Die Operation Pop() entfernt das Element vom Stack, das zuletzt hinzugefügt wurde. Betrachten wir nun die Array-Implementation eines Stacks, der aus genau 6 Elementen besteht.

Die wichtigsten Proteinkomplexe der Lichtreaktion
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

Der Schlüssel zum Verständnis der pop -Methode ist der Zeiger bzw. das Attribut tos . Es reicht völlig aus, tos um 1 zu dekrementieren:

public void pop()
{
   if (!empty()) tos--;
}

Wenn der Stack nicht leer ist, also noch mindestens 1 Element enthält (die sondierende Methode empty() wird gleich besprochen), kann man tos einfach dekrementieren. Die Zahl 18 an Index 5 in unserem Beispiel muss nicht gelöscht oder mit 0 überschrieben werden. Wichtig ist nur, dass tos zurückgesetzt wird. Alle Elemente rechts von tos interessieren überhaupt nicht.

Unser Beispiel-Stack würde nach dem Ausführen der Methode pop dann so aussehen:

Die wichtigsten Proteinkomplexe der Lichtreaktion
Autor: Ulrich Helmich 2019, Lizenz: siehe Seitenende.

An der Tatsache, dass die Zahl 18 noch in dem Stack enthalten ist, darf man sich nicht stören. Für die Stackverwaltung existiert das Element mit der 18 nicht mehr, da tos auf die 99 zeigt. Alles was sich rechts von tos befindet, existiert quasi nicht mehr für das Programm.

Angenommen, tos zeigt auf 23, also auf das Element mit dem Index 0. Die Bedingung !empty() wäre dann true , da der Stack noch nicht leer ist (er enthält ja noch das erste Element mit dem Index 0). Also würde tos dekrementiert und hätte anschließend den Wert -1, so wie direkt nach Ausführung des Konstruktors (bzw. der Init() -Operation).

Die top-Methode

Das ist jetzt eine ganz einfache Sache:

public int top()
{
   if (!empty())
      return stapel[tos];
   else
      return -1;
}

Wir gehen jetzt mal davon aus, dass nur positive int-Zahlen in dem Stack gespeichert werden. In diesem Fall kann eine negative Zahl als Ergebnis von Top() zurückgegeben werden, falls der Stack leer ist. Würden dagegen auch negative int-Zahlen im Stack gespeichert, müsste man sich etwas besseres einfallen lassen, eventuell sogar eine richtige Fehlerbehandlungs-Routine mit try und catch .

Die empty-Methode

Auch die Implementation der Empty() -Operation bzw. der empty() -Methode ist sehr einfach:

public boolean empty()
{
   return (tos == -1);
}

Das ist wohl die bisher kürzeste Methode der ganzen Stack-Klasse. Wenn der Stack leer ist, hat tos den Wert -1. Die Bedingung tos == -1 ist dann wahr, und daher liefert empty() den Wert true zurück.

4. Die Implementierung eines universellen Stacks ^Top

Bisher kann unser Stack nur int-Zahlen speichern. Das ist nicht besonders elegant und hilfreich. In der Programmierpraxis müssen meistens andere Daten gespeichert werden, zum Beispiel Adressen von Studenten (bei einem Verwaltungsprogramm), Gegenstände einer Heldin (bei einem Spiel) und so weiter. Wenn wir also schon einen Stack programmieren, sollte dieser möglichst universell sein, also in der Lage sein, alle möglichen Objekte zu speichern. Dazu müssen wir die Implementation des Stacks ein wenig abändern. Die wenigen Änderungen sind im folgenden Quelltext gelb bzw. grün markiert:

public class Stack
{
    private Object [] stapel;
    private int tos;
    
    public Stack()
    {
        stapel = new Object [100];
        tos = -1;
    }
    
   public void push(Object  x)
   {
      if (tos < 99)
      {
         tos++;
         stapel[tos] = x;
      }  
   }
   
   public void pop()
   {
      if (!empty()) tos--;
   }
   
   public Object top()
   {
      if (!empty())
         return stapel[tos];
      else
         return null ;
   }
   
   public boolean empty()
   {
      return (tos == -1); 
   }
}

Der Trick: Als Stack-Elemente werden Objekte der Klasse Object verwaltet. Die Klasse Object ist die Mutterklasse aller Java-Klassen. Das heißt, jede Java-Klasse ist letzten Endes von der Klasse Object abgeleitet.

Dass ein solches Vorgehen funktioniert, zeigt der folgende Quelltext:

public class Test
{
    Stack s;
    
    public Test()
    {
       s = new Stack();
       s.push(new Bruch(3,4));
       s.push(new Bruch(5,8));
       s.push(new Bruch(1,7));
    }
    Bruch oben = (Bruch) s.top();
}

Wir stellen uns dazu eine Klasse Bruch vor. Objekte der Klasse Bruch enthalten zwei Attribute, nämlich einen Zähler und einen Nenner; Einzelheiten dazu interessieren hier nicht weiter (Datenkapselung). Wichtig ist nur, dass solche Bruch -Objekte in dem Stack -Objekt s gespeichert werden können.

Etwas kompliziert wird es dann bei der "Wiedergewinnung" von Stack -Objekten, wie man an der letzten Quelltextzeile sieht.

Im Stack -Objekt s sind eigentlich nur Objekte der Klasse Object gespeichert, aber keine Objekte der Klasse Bruch . Wenn man also s . top() aufruft, bekommt man kein Bruch -Objekt zurückgeliefert, sondern ein Object -Objekt. Um daraus ein Bruch -Objekt zu machen, ist ein sogenanntes Typecasting erforderlich, quasi eine erzwungene Typenumwandlung. Dazu schreibt man den gewünschten Datentyp in Klammern vor die Anweisung, die ein Objekt der Klasse Object liefert:

Bruch oben = (Bruch) s.top();

In den neueren Java-Versionen gibt es zwar Möglichkeiten, solche Dinge zu vereinfachen, aber damit würden wir uns jetzt zu lange aufhalten. Wer sich für dieses Thema interessiert, sollte nach "generischen Datentypen in Java" recherchieren. Ein guter Einstieg für Experten ist der Wikipedia-Artikel Generische Programmierung in Java.

Aufgaben / Abitur ^Top

Im Zentralabitur Informatik des Landes NRW spielt der ADT Stack eine wesentliche Rolle. Aus diesem Grund habe ich eine Extra-Seite zum Thema "ADTs im Abitur NRW" geschrieben. Im Anschluss an die allgemeinen Ausführungen gibt es hier eine Seite mit anspruchsvolleren Aufgaben zum Thema Stack.

Alle Klausurkandidaten und vor allem alle Leute, die Informatik im Abitur wählen, sollten diese Aufgaben durcharbeiten. Natürlich sind auch leistungsstarke GK-Schüler, die noch Zeit haben und Punkte brauchen, eingeladen, diese Aufgaben zu bearbeiten.