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[cite: 3]. Sie dient der Zwischenspeicherung von Datenobjekten in einer strikten Reihenfolge.

Objekte der abstrakten Datenstruktur 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.

Datei:Image 90523e.png

Veranschaulichung des LIFO-Prinzips mittels Push- und Pop-Operationen auf einem Stapel

Alltagsanalogie: Ein Kellerspeicher lässt sich anschaulich mit einem Stapel von Umzugskisten 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 im Regelfall streng auf das oberste Element des Stapels beschränkt. Ein Hinzufügen oder Entfernen einer Kiste weiter unten im Stapel ist strukturell nicht möglich.

Aufbau und Spezifikation (API)

Im Kontext der objektorientierten Programmierung wird die abstrakte Datenstruktur formal über eine wohldefinierte Schnittstelle abgebildet[cite: 3]. Ein 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.
Object top()
- Die Anfrage liefert das oberste Stapelobjekt zurück, ohne es 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 vorne am Kopf eingefügt und gelöscht wird) garantiert hochperformante Zugriffszeiten. Dies ist für die informationstechnische Verarbeitung von Datenstrukturen in der beruflichen Praxis essenziell[cite: 4]. 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 Arbeitsweise und Veränderung des inneren Zustands eines Stacks lässt sich anhand einer sequenziellen Abfolge von Operationen veranschaulichen. 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 der `Stack()`-Operation 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, also liegt sie 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.

Implementierungsbeispiel (Java)

Für das tiefergehende Verständnis im Leistungskurs oder der Fachinformatiker-Ausbildung ist nachfolgend eine klassische objektorientierte Implementierung des Stacks auf Basis einer einfach verketteten Liste (Knotenstruktur) dargestellt. Dies schult das exakte, strukturierte algorithmische Denken zur Lösung informationstechnischer Problemstellungen[cite: 3].

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

    // Innere Knoten-Klasse zur Kapselung der Daten
    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;
        }
    }
}