Home > Informatik > Stufe Q1 > ADTs > ADT Stack

14.3 Der ADT Stack / Studium

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

Für Studierende der Informatik und besonders interessierte Schüler(innen):

Ein generischer Stack mit Java

In der bisherigen Implementierung unseres Stacks konnten wir zwar Objekte beliebiger Klassen speichern, mussten beim Zurückholen eines Objekts aber einen expliziten Typecast durchführen. Außerdem konnte man versehentlich Objekte unterschiedlicher Klassen in demselben Stack speichern.

Seit Java 5 gibt es mit den Generics eine elegantere Lösung. Dabei wird die Klasse Stack mit einem Typparameter versehen. Dieser legt fest, welchen Datentyp die Elemente des Stacks besitzen sollen.

Die generische Stack-Klasse

Wir erweitern unsere bisherige Klasse Stack um den Typparameter T. Die wesentlichen Änderungen sind gelb markiert:

public class Stack<T>
{
    private T[] stapel;
    private int tos;

    public Stack()
    {
        stapel = (T[]) new Object[10];
        tos = -1;
    }

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

    public void pop()
    {
        if (!empty())
        {
            stapel[tos] = null;
            tos--;
        }
    }

    public T top()
    {
        if (!empty())
            return stapel[tos];
        else
            return null;
    }

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

Was bedeutet der Typparameter T?

Die Schreibweise Stack<T> bedeutet, dass die Klasse Stack mit einem noch nicht festgelegten Datentyp arbeitet. Der Buchstabe T steht dabei für Type. Er ist lediglich ein Platzhalter und könnte grundsätzlich auch anders heißen.

Erst bei der Deklaration einer Stack-Variablen wird der konkrete Datentyp angegeben. Möchten wir beispielsweise ausschließlich Objekte der Klasse Bruch speichern, schreiben wir:

				Stack<Bruch> s = new Stack<>();
				

Der Compiler weiß nun, dass in diesem Stack nur Objekte der Klasse Bruch beziehungsweise ihrer Unterklassen gespeichert werden dürfen. Versucht man, ein Objekt einer anderen, nicht kompatiblen Klasse einzufügen, meldet der Compiler einen Fehler.

Die leeren spitzen Klammern <> beim Konstruktoraufruf bezeichnet man als Diamond-Operator. Der Compiler übernimmt den benötigten Typparameter aus der Deklaration auf der linken Seite.

Ein Beispiel für die Verwendung

Unsere bereits bekannte Klasse Test sieht mit dem generischen Stack folgendermaßen aus:

public class Test
{
    private Stack<Bruch> 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 = s.top();
    }
}

Der entscheidende Unterschied zur bisherigen Implementierung liegt in der letzten Anweisung. Die Methode top() liefert jetzt eine Referenz vom Typ Bruch zurück. Ein expliziter Typecast ist daher nicht mehr erforderlich.

Ein weiterer Vorteil ist die Typsicherheit. Würden wir beispielsweise versuchen, mit s.push("Hallo"); einen String in den Stack einzufügen, würde der Compiler dies bereits vor der Ausführung des Programms verhindern. In der nicht-generischen Version des vorherigen Abschnitts hätte man dagegen ohne Probleme einen String in den Stack einfügen können.

Fazit

Mit generischen Klassen lassen sich Datenstrukturen entwickeln, die unabhängig von einem konkreten Datentyp eingesetzt werden können. Gleichzeitig überprüft der Compiler, ob die verwendeten Datentypen zueinander passen. Dadurch werden viele Programmierfehler bereits beim Übersetzen erkannt.

Unsere generische Stack-Klasse kann nun beispielsweise als Stack<Bruch>, Stack<String> oder Stack<Integer> verwendet werden. Für primitive Datentypen wie int sind Generics dagegen nicht direkt geeignet. Hier verwendet man die entsprechenden Wrapper-Klassen, beispielsweise Integer statt int.

Implementierung mit einer ArrayList

Mit einer ArrayList<T> wird die Implementierung eines generischen Stacks deutlich einfacher. Vor allem benötigen wir keine Hilfsvariable tos mehr, da die ArrayList ihre aktuelle Größe selbst verwaltet. Auch die maximale Kapazität von zehn Elementen entfällt.

Dies ist ein möglicher Quelltext einer solchen Stack-Klasse:

import java.util.ArrayList;

public class Stack<T>
{
    private ArrayList<T> stapel;

    public Stack()
    {
        stapel = new ArrayList<>();
    }

    public void push(T x)
    {
        stapel.add(x);
    }

    public void pop()
    {
        if (!empty())
            stapel.remove(stapel.size() - 1);
    }

    public T top()
    {
        if (!empty())
            return stapel.get(stapel.size() - 1);
        else
            return null;
    }

    public boolean empty()
    {
        return stapel.isEmpty();
    }
}

Erläuterung der Implementierung

Die Implementierung des generischen Stacks auf der Grundlage einer ArrayList ist deutlich einfacher als die bisherige Implementierung mit einem Array. Die ArrayList übernimmt die Verwaltung des Speicherplatzes und vergrößert ihre Kapazität bei Bedarf automatisch. Eine Hilfsvariable wie tos ist nicht mehr erforderlich.

Die vier Stackoperationen lassen sich direkt auf Methoden der ArrayList zurückführen. Die Methode push() hängt mit add() ein neues Element an das Ende der Liste an. Die Methode pop() entfernt mit remove() das letzte Listenelement, während top() mit get() auf dieses Element zugreift, ohne es zu entfernen. Die Methode empty() verwendet schließlich isEmpty(), um festzustellen, ob der Stack leer ist.

Da die ArrayList selbst eine generische Klasse ist, können wir den Typparameter T direkt übernehmen. Ein explizites Typecasting ist nicht mehr notwendig.

Diese Implementierung zeigt außerdem ein wichtiges Prinzip der objektorientierten Programmierung: Die öffentliche Schnittstelle der Klasse Stack bleibt unverändert, obwohl wir die interne Datenstruktur vollständig ausgetauscht haben. Für die Benutzer der Klasse spielt es keine Rolle, ob der Stack intern durch ein Array, eine ArrayList oder eine verkettete Liste realisiert wird.

Und genau das ist der Vorteil der abstrakten Datentypen. Es werden nur die Operationen definiert, nicht aber die Implementierung.

Die axiomatische Sichtweise

In dem Informatik-Lehrbuch "Programmierung und Datenstrukturen: Eine Einführung anhand von Beispielen" von Jörg NIEVERGELT (1986) wird der ADT Stack auf folgende Weise definiert:

Axiomatische Definition des ADT Stack nach NIEVERGELT

Bei dieser axiomatischen Spezifikation wird das Verhalten der Stack-Operationen durch mathematische Regeln, sogenannte Axiome, festgelegt. Ein Axiom ist eine grundlegende Aussage, die innerhalb des betrachteten Systems als gültig vorausgesetzt wird.

Wir wollen die sechs Axiome schrittweise "übersetzen". Fangen wir doch gleich mit dem ersten Axiom an.

empty(q0) = true;

Dabei muss man vorausschicken, dass q immer irgendein Stack ist; genauer ein Stackzustand. Ein besonderer Zustand eines Stacks ist q0, der leere Stack.

Das Axiom besagt also, dass der Aufruf von empty genau dann den Wert true liefert, wenn der Stack leer ist. Das hört sich doch schon mal ganz einleuchtend an.


Für alle Zustände q aus der Menge der möglichen Stackzustände Q und für alle Stackelemente x aus der Menge der möglichen Stackelemente X gelten die nächsten Axiome.

init(q) = q0;

Mit diesem Axiom wird die Tatsache beschrieben, dass nach der Initialisierung eines Stacks dieser leer ist, sich also im Zustand q0 befindet.

empty(push(q,x))= FALSE

Wenn man ein Element x auf den Stack q pusht und danach empty abfragt, so erhält man stets das Ergebnis false. Oder auf gut Deutsch: Ein Stack, in den man etwas hinein gepusht hat, kann nicht leer sein.

top(push(q,x))= x

Das ist ein sehr wichtiges Axiom. Hier wird nämlich festgelegt, wo bzw. wie im Stack ein Element x durch push gespeichert wird. Das zuletzt mit push gespeicherte Element wird beim Aufruf von top als Ergebnis zurück geliefert. Anschaulich kann man sich das so vorstellen, dass das Element "oben" auf den Stack gelegt wird, und dass top stets das "obere" Element zurück liefert. Wenn man auf eine räumliche Vorstellung verzichten will, kann man auch sagen: Mit top wird immer das zuletzt mit push hinzugefügte Element ermittelt. Dieses Art der Speicherverwaltung bezeichnet man auch als LIFO-Prinzip, Last in, First out.

pop(push(q,x))= q

Auch dieses Axiom ist sehr wichtig. Hier wird nämlich die Arbeitsweise von pop festgelegt. Wenn man ein Element x pusht und dann pop aufruft, hat man genau den gleichen Stackzustand q wie vorher. Anschaulich kann man sich das so vorstellen, dass das Element "oben" auf den Stack gelegt wird, und dass pop stets das "obere" bzw. das zuletzt mit push hinzugefügte Element löscht.

not empty(q) ==> push(pop(q),top(q)) = q

Das ist wohl das komplizierteste Axiom, es ist nicht ganz so einfach zu verstehen wie die vorherigen Axiome.

Wenn man das Element x, das top liefert (falls der Stack nicht leer ist), zunächst irgendwo speichert, dann pop aufruft und anschließend das gespeicherte Element wieder mit push im Stack speichert, ändert sich der Stack nicht.

Achtung: Die Formel

push(pop(q),top(q)) = q

geht davon aus, dass die Operation pop das oberste Stackelement entfernt und den dadurch entstandenen Stackzustand zurückliefert. Die Operation top liefert dagegen den Wert des obersten Elements, ohne den Stack zu verändern.

Bei manchen Java-Implementierungen ist das anders: Hier verändert pop() den Stack direkt und liefert gleichzeitig das entfernte Element zurück. Die Operation top heißt in der Java-Standardklasse Stack übrigens peek().

Die Stack-Implementationen auf dieser Homepage bzw. in diesem Kurs halten sich an die oben genannten Axiome. Die Methode pop() entfernt also das oberste Stackelement, liefert aber keinen Wert zurück (ist also eine void-Methode). Der oberste Wert wird durch die sondierende Methode top() geliefert, die den Stack aber nicht verändert, das oberste Element also nicht entfernt.