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: Public domain.
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 der Stack-Operationen
Autor: Ulrich Helmich 2019, Lizenz: Public domain.
- 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.
Verständisübung
Skizzieren Sie den int-Stack, der sich nach folgenden Operationen ergibt. Geben Sie auch die Rückgabewerte der Operationen Top() und Empty() mit an:
- Push(5)
- Push(12)
- Push(3)
- Top()
- Pop()
- Top()
- Push(18)
- Push(4)
- Empty()
- Push(6)
Hier ein Lösungsvorschlag zur Selbst-Kontrolle:
Lösungsvorschlag
Autor: Ulrich Helmich 2026, Lizenz: Public Domain
2. Grundsätzliche Überlegungen zur Implementierung Top
Implementation über ein Array
Wir implementieren einen Stack mithilfe eines int-Arrays aus zehn Elementen. Die folgende Abbildung zeigt dieses Array nach der Init()-Operation sowie nach drei Push()-Operationen:
Ein int-Stack nach Init() und drei Push()-Operationen
Autor: Ulrich Helmich 2026, Lizenz: Public Domain
Die Hilfs-Variable TOS (für Top of Stack) wird mit dem Wert -1 initialisiert. Nach der ersten Push()-Operation hat diese Variable den Wert 0. Das heißt, in dem Arrayelement mit dem Index 0 steht das oberste Stack-Element, in unserem Fall die Zahl 5.
Mit dem zweiten Push()-Befehl wird die Zahl 5 in das nächste Arrayelement (Index 1) geschrieben, und der dritte Push()-Befehl schreibt die Zahl 3 in das dritte Arrayelement (Index 2). Am Ende des dritten Push()-Befehls hat TOS den Wert 2, denn dort befindet sich das oberste Stack-Element.
Interessant ist nun die Arbeitsweise des Pop()-Befehls:
Der int-Stack nach Pop() und Push(18)
Autor: Ulrich Helmich 2026, Lizenz: Public Domain
Der TOS-Zeiger wird einfach um den Wert 1 dekrementiert und erhält dadurch wieder den Wert 1. Die Zahl 3 in dem Arrayelement mit dem Index 2 kann ohne weiteres bestehen bleiben. Beim nächsten Push()-Befehl wird sie einfach mit dem neuen Wert (hier: 18) überschrieben.
Selbstverständlich könnte man diesen Wert auch mit 0 überschreiben, dann sähe das Array "ordentlicher" aus. Der Benutzer des Arrays sieht die Zahlen jedoch nicht und kann auch nicht mit Top() darauf zugreifen, von daher ist es völlig egal, ob man den gelöschten Wert mit 0 überschreibt oder einfach den alten Wert stehen lässt.
3. Die Implementierung im Detail Top
public class Stack
{
private int[] stapel;
private int tos;
public Stack()
{
stapel = new int[10];
tos = -1;
}
public void push(int x)
{
if (tos < 9)
{
tos++;
stapel[tos] = x;
}
}
Hier sehen wir den Java-Quelltext einer Klasse Stack mit den Attributen, dem Konstruktor und der Methode push().
Der Stack wird durch das int-Array stapel realisiert. Die Hilfsvariable tos speichert den Index des jeweils obersten Stackelements. Am Anfang wird tos auf den Wert -1 gesetzt, nach dem ersten Aufruf von push() hat tos dann den Wert 0.
Die push()-Methode kontrolliert zunächst, ob noch genügend Platz in dem Array vorhanden ist. Solange tos kleiner als 9 ist, ist das der Fall. Dann wird tos um eins erhöht, und anschließend wird das Arrayelement mit dem Index tos mit dem neuen Wert belegt.
Die pop-Methode
public void pop()
{
if (!empty()) tos--;
}
Zunächst wird die sondierende Methode empty() aufgerufen. Wenn der Stack nicht leer ist, kann pop() durchgeführt werden. In dieser Java-Implementierung wird der Wert von tos einfach dekrementiert. Der alte Wert des entfernten Stackelements wird dabei nicht mit 0 überschrieben – wie bereits im vorherigen Abschnitt erläutert.
Die top-Methode
public int top()
{
if (!empty())
return stapel[tos];
else
return -1;
}
Die top()-Methode muss eine int-Zahl als Ergebnis zurückliefern, auch dann, wenn der Stack leer ist und top() nicht ausgeführt werden kann.
In einem professionellen Java-Programm würde man in diesem Fall eine Exception auslösen. Für den Unterricht in der gymnasialen Oberstufe reicht es aber aus, einen Fehlerwert zurückzuliefern, in diesem Fall den Wert -1.
Das funktioniert natürlich nur dann zuverlässig, wenn die Stackelemente selbst nicht negativ sein können, also nur positive Zahlen oder die 0 enthalten.
Die empty-Methode
Auch die Implementierung 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 flexibel. In der Programmierpraxis müssen häufig andere Daten gespeichert werden, zum Beispiel Adressen von Studierenden (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, Objekte beliebiger Klassen zu speichern. Dazu müssen wir die Implementierung 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[10];
tos = -1;
}
public void push(Object x)
{
if (tos < 9)
{
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 Stackelemente können jetzt Objekte beliebiger Klassen verwaltet werden. Möglich wird dies durch die Klasse Object. Sie ist die Oberklasse aller Java-Klassen. Das heißt, jede Java-Klasse ist direkt oder indirekt 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 dieser Klasse 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 komplizierter wird es dann beim Zurückholen der Bruch-Objekte aus dem Stack, wie man an der letzten Anweisung des Konstruktors sieht.
Im Stack-Objekt s werden Referenzen vom Typ Object gespeichert. Die referenzierten Objekte selbst bleiben aber weiterhin Objekte der Klasse Bruch. Wenn man nun s.top() aufruft, erhält man eine Referenz vom Typ Object zurück. Diese kann nicht ohne Weiteres einer Variablen vom Typ Bruch zugewiesen werden.
Hier ist ein sogenanntes Typecasting erforderlich, genauer gesagt eine explizite Typumwandlung der Referenz. Dazu schreibt man den gewünschten Datentyp in Klammern vor den Ausdruck, der die Referenz vom Typ Object liefert:
Bruch oben = (Bruch) s.top();
Durch diesen Typecast wird das ursprüngliche Objekt nicht verändert. Der Compiler akzeptiert nun die Zuweisung an die Variable oben. Zur Laufzeit wird allerdings überprüft, ob es sich tatsächlich um ein Objekt der Klasse Bruch handelt. Ist dies nicht der Fall, kommt es zu einer Laufzeitexception.
Seit Java 5 gibt es mit den sogenannten generischen Typen (Generics) eine elegantere Möglichkeit, solche Stacks zu implementieren. Dabei kann bereits bei der Erzeugung eines Stacks festgelegt werden, welche Art von Objekten er speichern soll. Auf das Typecasting kann dann verzichtet werden. Wer sich für dieses Thema interessiert, kann sich den nächsten Abschnit durchlesen, der eigentlich für Studierende der Informatik im ersten und zweiten Semester geschrieben wurde.
Diese Ergänzungsseite wurde für Studierende der Informatik in den beiden ersten Semestern geschrieben. Die Themen:
Seitenanfang -
Allgemeines -
Abstrakte Datentypen -
Stack -
Queue -
Dictionary -
List -
ADTs im Abitur