Home > Informatik > Stufe Q1 > ADTs

14.3 Der ADT Stack

Allgemeines - Abstrakte Datentypen - Stack - Queue - Dictionary - List - ADTs im Abitur - Axiome

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 drauf. Der volle Stapel wird in die Küche gefahren und dann von oben her wieder abgebaut.

Ein Stapel aus 14 Tellern, bei mir in der Küche photographiert.

Ein Stapel Teller

Der ADT Stack wird durch folgende Operationen definiert:

ADT Stack
  • Init(): Erzeugt einen leeren Stack.
  • Push(x): Das Element x wird hinzugefügt.
  • Pop(): Das zuletzt hinzugefügte Element wird entfernt.
  • Top(): Der Wert des zuletzt hinzugefügten Elementes wird zurückgeliefert.
  • Empty(): Falls der Stack leer ist, wird TRUE zurückgeliefert, sonst FALSE.

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

Arbeitsweise eines Stacks, Erklärung siehe folgenden Text.
  • Nach Aufruf der Init()-Operation ist der Stack zwar vorhanden, aber er enthält noch keine Elemente, er ist 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, befindet sich also "oben" im Stack.
  • Nach Push(17) befinden sich drei Element im Stack, die 17 ist das oberste Element.
  • 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 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

Wir speichern die Stack-Elemente in einem Array. Java würde auch andere Datentypen bzw. Klassen für diesen Zweck zur Verfügung stellen, zum Beispiel die KlasseArrayList, aber wir wollen hier ganz "klassisch/altmodisch" arbeiten und wählen einen Array. An sich sollte dieser Array alle möglichen Datenobjekte speichern können. Aber wir wollen uns zunächst einmal damit begnügen, int-Zahlen in dem Stack zu speichern.

stapel = new int[100];

Ein Array, der 100 int-Zahlen fasst, sollte uns für die Demonstration des Stack-Prinzips reichen.

Wenn die Operation Push(x) bzw. die Methode push() zum ersten Mal aufgerufen wird, so wird die Zahl x in dem Array-Element mit dem Index 0 gespeichert. Wird dannpush()mit dem Argument y aufgerufen, wird der Wert von y im nächsten Array-Element gespeichert, und beipush()mit dem Argument z wird der Wert von z dann im dritten Array-Element (Index = 2) gespeichert.

In einem Attribut tos wird dann gespeichert, an welchem Index sich das "oberste" (also das zuletzt hinzugefügte) Stack-Element befindet. Wurde dreimal die Methodepush()aufgerufen, so hat tos den Wert 2, denn das zuletzt hingefügte Stack-Element befindet sich im Array an der Position 2.

Bei jedem neuenpush()muss tos dann um 1 inkrementiert werden. Wird pop() aufgerufen, so wird tos entsprechend dekrementiert, falls das möglich ist. Wenn tos bereits den Wert 0 hat, ist eine Dekrementation natürlich nicht mehr möglich.

Die Array-Elemente, die sich rechts von tos befinden, können ignoriert werden. Ein Löschen dieser Elemente ist nicht notwendig.

Konkretisierung, Modell-Beispiel
Der Stack nach Ausführung der Operationen  push(23), push(15), push(78), push(35), push(99).

Der Stack nach Ausführung der Operationen push(23), push(15), push(78), push(35), push(99).

Das Bild veranschaulicht die Push()-Operation. Nach dem Erzeugen eines neuen int-Arrays sind die Array-Elemente mit lauter Nullen gefüllt, wie man mit Hilfe des Objektinspektors von BlueJ leicht überprüfen kann. Nach dem fünfmaligen Pushen sind die ersten fünf Element des Arrays mit den entsprechenden Zahlen belegt. Die zuletzt hinzugefügte Zahl befindet sich an fünfter Stelle im Array, hat also den Index 4. Genau diese Zahl - 4 - wird auch in dem Attribut tos gespeichert, das quasi als "Zeiger" auf das oberste Stackelement angesehen werden kann.

Der Stack nach Ausführung der zusätzlichen Operation push(18).

Der Stack nach Ausführung der zusätzlichen Operation push(18).

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

Der Stack nach Ausführung der Operationen pop().

Der Stack nach Ausführung der Operationen pop()

Wenn jetzt die Operation 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 Array-Element 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

Der Stack nach einer zweiten pop()-Operation.

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.

Jetzt wird push(28) aufgerufen

Wenn jetzt Push(28) aufgerufen wird, schreibt die Push()-Operation den Wert 28 in das Array-Element, das sich rechts von tos befindet. Egal, was vorher in diesem Array-Element 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" Array-Elemente 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 Array-Element auch den Index 0 hat. 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.

Hätte tos also nach Initialisierung des Stacks den Wert 0, könnte das so interpretiert werden, als ob das Element mit dem Index 0 bereits mit einem Wert belegt wäre. Um solche Missverständnisse zu vermeiden, wurde in unserem Beispiel tos auf den Anfangswert -1 gesetzt.

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 Array-Element stapel[tos] der Wert von x zugewiesen. Durch die Beschränkung auf eine Anweisung entfallen dann auch die beiden Klammern.

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 Array-Element 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 Array-Element mit dem Index 1, also im zweiten Array-Element, wird dann die zweite Zahl gespeichert, die 15.

Und so geht das weiter, bis der Array voll ist. Angenommen, von den hundert Array-Elementen sind alle belegt, und es soll eine weitere Zahl gepusht werden. Die "oberste" Zahl befindet sich jetzt in dem Array-Element mit dem Index 99, also in dem letzten Array-Element. 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.

Array-Implementation eines Stacks (6 Elemente) vor pop(). tos zeigt auf die 18.

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:

Bei pop() wird tos einfach dekrementiert.

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 eines Helden (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.

Seitenanfang -
Allgemeines - Abstrakte Datentypen - Stack - Queue - Dictionary - List - ADTs im Abitur - Axiome