Stack

Hast Du Dich schon einmal gefragt, wie die Rückgängig- oder Wiederholen-Funktion in Word oder Photoshop implementiert sein könnte? Dann hast Du hier mit dem Artikel über den Stack Deine Antwort!

Stack in der Informatik

Im Bereich der Informatik gehört der Stack zu den abstrakten Datentypen (ADT) und beschreibt eine Datenstruktur, bei der man zu jeder Zeit nur das oberste Element abrufen kann. Auf Deutsch nennt sich der Stack deshalb auch oft „Stapelspeicher“ oder „Kellerspeicher“.

Stack Definition

Ein Stack ist im Grunde eine spezielle Form der linearen Liste. Allerdings kann man bei einem Stack nicht auf tiefer liegende Elemente zugreifen, sofern man nicht alle Elemente darüber entfernt. Das LIFO-Prinzip beschreibt genau diese Eigenschaft eines Stacks.

Stack LIFO-Prinzip

Stelle Dir einen Stapel Bücher auf deinem Tisch vor. Zu einer gegebenen Zeit kannst Du ohne Weiteres nur jenes Buch entnehmen, welches zuletzt oben auf den Stapel gelegt wurde.

Genau das beschreibt das Last-in-first-out-Prinzip, oder kurz: LIFO-Prinzip.

Bei einem Stack gibt es drei gängige Operationen, die zum Einsatz kommen.

• Push-Operation: Man legt ein neues Element auf den Stapel.
• Pop-Operation: Man entnimmt das oberste Element vom Stapel.
• Peek-Operation: Man sieht sich das oberste Element auf dem Stapel an, ohne es jedoch zu entnehmen.

Doch wo wird ein Stack überhaupt in der Praxis verwendet?

Praktische Anwendungen für Stacks

Praktische Anwendung findet der Stack vor allem dort, wo man Daten nur temporär speichern möchte.

Ein Beispiel ist die Ausführung eines Programms, die aus verschachtelten Funktionsaufrufen besteht. Diese Aufrufe legt das Programm auf einem Call Stack ab und weiß somit jederzeit, in welcher Funktion es sich gerade befindet und welche Elternfunktion diese aufgerufen hat.

Ein weiterer Anwendungsfall für den Stack ist die Tiefensuche (Depth-first search). Das ist ein Algorithmus, um einen Knoten in einer Baumstruktur zu finden, und häufig verwendet auch dieses Verfahren die Stack-Datenstruktur.

Zeitkomplexität bei Stack-Operationen

Grundsätzlich ist die Zeitkomplexität eines Algorithmus immer abhängig von der Implementierung des Entwicklers. Bei den Stack-Operationen pop, push und peek ist eine konstante Zeitkomplexität möglich, d.h. ihre Laufzeit ändert sich nicht mit der Menge an Elementen im Stack.

Das lässt sich auch logisch leicht nachvollziehen: Dem Stack ist es egal, wie viele Elemente sich in der Tiefe der Datenstruktur befinden. Laut LIFO-Prinzip kann er ohnehin nur die oberste Position ansteuern.

Stack in bekannten Frameworks

In gängigen Frameworks ist normalerweise eine Implementierung der Stack-Datenstruktur bereits vorhanden. Als Beispiele sollen im Folgenden die Java- und C#-Implementierungen dienen.

Stack: Java-Implementierung

In Java gibt es bereits die Klasse java.util.Stack, welche den Stack Datentyp implementiert. Laut Java-Dokumentation sollten Entwickler diese Klasse allerdings nicht mehr verwenden und stattdessen auf eine Implementierung der Deque-Schnittstelle zurückgreifen.

Java: Stack- und Queue – Vergleich

Die Queue ist eine andere häufig verwendete Datenstruktur, für die in Java die Schnittstelle Queue im Namensraum java.util.queue existiert. Die Implementierung einer Queue-Klasse lässt sich wie beim Stack ebenfalls leicht über die ArrayDeque-Klasse realisieren.

Die Queue ist dem Stack sehr ähnlich, nur dass die vordersten Elemente wie bei einer Warteschlange im echten Leben zuerst an der Reihe sind. Damit funktioniert die Queue im Gegensatz zum Stack nach dem FIFO-Prinzip: Was zuerst reinkommt, kommt auch zuerst wieder raus.

C# Stack-Implementierung

Die C# Stack-Implementierung befindet sich im Namensraum System.Collections.Generic. Die nicht-generische Implementierung unter System.Collections soll laut Microsoft-Dokumentation nicht mehr verwendet werden.

In C# ist der Stack als Array implementiert. Diese Art der Implementierung wollen wir uns als nächstes ansehen.

Java: Array-Stack Implementierung

Das Java-Framework bietet zwar eine Stack Implementierung an, wie wir gesehen haben. Es lohnt sich aber, zur Übung selbst einen Stack mit einem Array zu implementieren.

Die folgende Implementierung verwendet eine feste Array-Größe, und somit ist auch die Menge an Elementen im Stack darauf begrenzt. Außerdem verzichtet die Implementierung der Einfachheit halber auf die Überprüfung, ob der Zugriff auf das Array in einer Methode valide ist oder ob eine Exception geworfen werden sollte.

public class Stack {
    private Object[] elements;
    private int count;

    public Stack(int capacity) {        
        // Array initialisieren
        elements = new Object[capacity];
    }

    public void push(Object item) {
        // Element on top hinzufügen    
        elements[count] = item;

        // Top Zeiger hochzählen
        count++; 
    }

    public Object pop() { 
        // Oberstes Element nehmen        
        Object item = elements[count - 1];
        
        // Im Array die Position auf null setzen        
        elements[count - 1] = null;

        // Top Zeiger runterzählen        
        count--;        
    
        return item;
    }

    public Object peek() {
        // Oberstes Element nehmen und zurückgeben
        Object item = elements[count - 1];
        return item;
    }
}

Rekursion und Stack

Eine rekursiv implementierte Methode ruft sich immer wieder selbst auf, bis das gewünschte Ergebnis errechnet ist. Dadurch wird diese Methode durch das Programm mehrfach auf dem Call Stack abgelegt.

Als Beispiel soll uns hier die rekursive Berechnung der Fakultät dienen:

public static void main(String[] args) {
    fakultaet(4);
}   

long fakultaet(int n) {
    if (n > 1) {
        return fakultaet(n - 1);
    }

    return 1;
}

Die Methode fakultaet(int) ist rekursiv implementiert. Wie wird sich der Aufruf von fakultaet(4) nun im Call Stack widerspiegeln?

Wenn Du den Programmablauf durchgehst, erkennst Du, dass der letzte Aufruf fakultaet(1) ist. Dieser bildet somit das oberste Element im Stack. Bei dem Rücksprung zum Aufrufer wird der Stack dann Element für Element wieder aufgelöst.