Stapel

Einführung

In der Informatik bezeichnet ein Stapelspeicher oder Kellerspeicher (kurz Stapel oder Keller, häufig auch mit dem englischen Fachbegriff Stack bezeichnet) eine fundamentale, dynamische Datenstruktur. Sie dient der temporären Zwischenspeicherung von Datenobjekten in einer streng definierten Reihenfolge und ist ein zentraler Bestandteil der objektorientierten Anwendungsentwicklung.

Objekte der abstrakten Datenstruktur (ADT) Stack verwalten beliebige Elemente nach dem LIFO-Prinzip (Last-In-First-Out). Das bedeutet: Das Element, welches als letztes auf den Stapel gelegt wurde, wird als erstes wieder entnommen.

Alltagsanalogie: Ein Kellerspeicher lässt sich anschaulich mit einem Stapel von Umzugskisten oder einem Tellerstapel vergleichen. Es kann immer nur eine neue Kiste oben auf den Stapel gepackt werden (dies entspricht der Operation push). Ebenso kann immer nur die oberste Kiste heruntergenommen werden (entspricht der Operation pop). Der lesende oder schreibende Zugriff ist strukturell zwingend auf das oberste Element des Stapels beschränkt. Ein Hinzufügen oder Entfernen einer Kiste weiter unten im Stapel ist nicht möglich.

Visualisierung

Die Arbeitsweise der LIFO-Datenstruktur lässt sich durch die beiden Hauptoperationen – das Hinzufügen (Push) und das Entfernen (Pop) – am Kopfende des Stapels veranschaulichen.

Aufbau und Spezifikation (API)

Im Kontext der Softwaretechnologie wird diese abstrakte Datenstruktur formal über eine wohldefinierte Schnittstelle abgebildet, um die Kapselung der Daten zu gewährleisten[cite: 4]. Ein klassischer Stapel verfügt über die folgenden Methoden und Konstruktoren:

Konstruktor

Stack()
- Ein neuer, leerer Stapel wird erzeugt.

Methoden

boolean isEmpty()
- Die Anfrage liefert den Wert true, wenn der Stapel keine Objekte enthält. Andernfalls liefert sie den Wert false.
void push(Object pObject)
- Das Objekt pObject wird oben auf den Stapel gelegt. Falls pObject den Wert null hat, bleibt der Stapel unverändert.
void pop()
- Das zuletzt eingefügte (oberste) Objekt wird von dem Stapel entfernt. Falls der Stapel bereits leer ist, bleibt er unverändert (es tritt kein Fehler auf).
Object top()
- Die Anfrage liefert das oberste Stapelobjekt zurück, ohne es aus der Datenstruktur zu entfernen. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurückgegeben.

Laufzeitanalyse (Komplexität)

Eine effiziente Implementierung des Stacks (beispielsweise über eine einfach verkettete Liste, bei der stets am Kopfknoten eingefügt und gelöscht wird) garantiert hochperformante Zugriffszeiten. Da ausschließlich auf das oberste Element zugegriffen wird, müssen keine iterativen Suchvorgänge durchgeführt oder nachfolgende Elemente im Speicher verschoben werden. Es ergibt sich gemäß der Landau-Notation folgende Laufzeitkomplexität:

Operation	1. Best-Case	2. Average-Case	3. Worst-Case
`push(Object pObject)`	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]
`pop()`	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]
`top()`	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]
`isEmpty()`	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]	[math]\displaystyle{ \mathcal{O}(1) }[/math]

Beispiel: Arbeitsweise der Stack-Operationen

Die Veränderung des inneren Zustands eines Stacks lässt sich anhand einer sequenziellen Abfolge von Operationen nachvollziehen. In der folgenden Tabelle ist das jeweils oberste Element (Top) der Liste rechts angeordnet.

Schritt	Operation	Zustand des Stacks (Bottom → Top)	Erläuterung
1.	`Stack()`	`[ ]` (leer)	Nach Aufruf des Konstruktors ist der Stack initialisiert, enthält aber noch keine Elemente.
2.	`push(12)`	`[12]`	Nach Aufruf von `push(12)` enthält der Stack genau ein Element, nämlich die Zahl 12.
3.	`push(8)`	`[12, 8]`	Nach Aufruf von `push(8)` sind zwei Elemente im Stack enthalten. Die 8 wurde zuletzt hinzugefügt, befindet sich also oben im Stack.
4.	`pop()`	`[12]`	Wenn `pop()` aufgerufen wird, wird die 8 wieder entfernt – sie war die zuletzt hinzugefügte Zahl.
5.	`push(15)`	`[12, 15]`	Nach `push(15)` besteht der Stack wieder aus zwei Elementen. Die 15 wurde zuletzt gepusht, liegt also oben auf dem Stack.
6.	`push(16)`	`[12, 15, 16]`	Nach `push(16)` besteht der Stack aus drei Elementen. Wieder ist die zuletzt gepushte Zahl ganz oben im Stack. Ein Aufruf von `top()` würde nun `16` zurückgeben.

Implementierungsbeispiel (Java)

Für das tiefergehende Verständnis im Informatikunterricht ist nachfolgend eine klassische objektorientierte Implementierung des Stacks auf Basis einer einfach verketteten Liste (Knotenstruktur) dargestellt. Diese Implementierung ermöglicht das Anwenden dynamischer Datenstrukturen sowie die Untersuchung zur Effizienz und Korrektheit von Algorithmen[cite: 3].

public class Stack {
    
    // Verweis auf das oberste Element des Stapels
    private Node head;

    // Innere Knoten-Klasse zur Kapselung der Datenstruktur
    private class Node {
        Object content;
        Node nextNode;

        public Node(Object pContent) {
            content = pContent;
            nextNode = null;
        }
    }

    /**
     * Konstruktor: Ein leerer Stapel wird erzeugt.
     */
    public Stack() {
        head = null;
    }

    /**
     * Prüft, ob der Stapel leer ist.
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * Legt ein neues Objekt oben auf den Stapel.
     */
    public void push(Object pObject) {
        if (pObject != null) {
            Node newNode = new Node(pObject);
            newNode.nextNode = head; // Das neue Element zeigt auf den bisherigen Kopf
            head = newNode;          // Der Kopf wird auf das neue Element gesetzt
        }
    }

    /**
     * Entfernt das oberste Objekt vom Stapel.
     */
    public void pop() {
        if (!this.isEmpty()) {
            head = head.nextNode;    // Der Kopf rutscht ein Element nach unten (das alte Top-Element wird vom Garbage Collector entfernt)
        }
    }

    /**
     * Liefert das oberste Objekt des Stapels.
     */
    public Object top() {
        if (this.isEmpty()) {
            return null;
        } else {
            return head.content;
        }
    }
}