In der Informatik bezeichnet ein Stapelspeicher oder Kellerspeicher (kurz Stapel oder Keller, häufig auch mit dem englischen Wort Stack bezeichnet) eine häufig eingesetzte dynamische Datenstruktur. Sie wird von den meisten Mikroprozessoren direkt mithilfe von Maschinenbefehlen unterstützt.

Funktionsprinzip

Ein Stapel kann eine theoretisch beliebige, in der Praxis jedoch begrenzte Menge von Objekten aufnehmen. Elemente können nur oben auf den Stapel gelegt und auch nur von dort wieder gelesen werden. Elemente werden übereinander gestapelt und in umgekehrter Reihenfolge vom Stapel genommen. Dies wird auch Last-In-First-Out-Prinzip (LIFO) genannt.

Dazu werden folgende Operationen zur Verfügung gestellt:

push (auch „einkellern“)

legt das Objekt oben auf den Stapel.

pop („auskellern“)

liefert das oberste Objekt und entfernt es vom Stapel. Bei manchen Prozessoren wie dem MOS Technology 6502 wird diese Aktion dagegen pull („herunterziehen“) genannt.

peek („nachsehen“)

liefert das oberste Objekt, ohne es zu entfernen (zuweilen auch top genannt, also „oben“).

In der Automatentheorie werden Stapel benutzt, um bestimmte Problemklassen theoretisch betrachten zu können (siehe Kellerautomat). Sie unterscheidet deshalb genauer zwischen einem echten Kellerspeicher, bei dem kein Element außer dem obersten gelesen werden kann, und einem Stapelspeicher, bei dem jedes Element betrachtet, aber nicht verändert werden kann. In der Praxis spielt diese Unterscheidung jedoch kaum eine Rolle; beinahe jede Implementierung ist ein Stapel. Daher werden die Begriffe im Allgemeinen synonym verwendet.

Es gibt viele Variationen des Grundprinzips von Stapeloperationen. Jeder Stapel hat einen festen Speicherort im Speicher, an dem er beginnt. Wenn Datenelemente zum Stapel hinzugefügt werden, wird der Stapelzeiger verschoben, um die aktuelle Ausdehnung des Stapels anzuzeigen, die sich vom Ursprung weg ausdehnt.

Stapelzeiger können auf den Ursprung eines Stapels oder auf einen begrenzten Adressbereich entweder über oder unter dem Ursprung zeigen, abhängig von der Richtung, in die der Stapel wächst. Der Stapelzeiger kann jedoch den Ursprung des Stapels nicht überschreiten. Mit anderen Worten, wenn der Ursprung des Stapels bei der Speicheradresse 1000 liegt und der Stapel nach unten in Richtung der Speicheradressen 999, 998 usw. wächst, darf der Stapelzeiger niemals über 1000 auf 1001, 1002 usw. hinaus erhöht werden. Wenn eine Pop-Operation auf dem Stapel bewirkt, dass sich der Stapelzeiger über den Ursprung des Stapels hinaus bewegt, tritt ein Stapelunterlauf auf. Wenn eine Push-Operation bewirkt, dass der Stapelzeiger über die maximale Ausdehnung des Stapels hinaus erhöht oder verringert wird, tritt ein Stapelüberlauf auf.

Einige Laufzeitumgebungen, die stark von Stapeln abhängig sind, bieten möglicherweise zusätzliche Vorgänge, zum Beispiel

duplicate („duplizieren“)

Das oberste Element wird eingeblendet und dann erneut gedrückt (zweimal), sodass jetzt eine zusätzliche Kopie des vorherigen obersten Elements mit dem Original darunter oben liegt.

swap oder exchange („tauschen“)

Die beiden obersten Gegenstände auf dem Stapel tauschen Plätze aus.

rotate oder roll („rotieren“)

Die n obersten Elemente werden rotierend auf dem Stapel verschoben. Wenn beispielsweise n = 3 ist, werden die Elemente 1, 2 und 3 auf dem Stapel an die Positionen 2, 3 bzw. 1 auf dem Stapel verschoben. Viele Varianten dieser Operation sind möglich, wobei die häufigste als Linksdrehung und Rechtsdrehung bezeichnet wird.

Stapel werden oft so dargestellt, dass sie von unten nach oben wachsen. Sie können auch visualisiert werden, wie sie von links nach rechts wachsen, so dass "ganz oben" zu "ganz rechts" wird, oder sogar von oben nach unten wachsen. Das wichtige Merkmal ist, dass sich der Boden des Stapels in einer festen Position befindet. Die Abbildung in diesem Abschnitt ist ein Beispiel für eine Wachstumsvisualisierung von oben nach unten: Die Oberseite (28) ist der Stapel "unten", da der Stapel "oben" (9) der Ort ist, an dem Elemente geschoben oder herausgeschoben werden.

Ein Stapel wird in Computern normalerweise durch einen Block von Speicherzellen dargestellt, wobei sich der "untere" an einer festen Stelle befindet und der Stapelzeiger die Speicheradresse der aktuellen "oberen" Zelle im Stapel enthält. Die obere und untere Terminologie werden verwendet, unabhängig davon, ob der Stapel tatsächlich in Richtung niedrigerer Speicheradressen oder in Richtung höherer Speicheradressen wächst.

Wenn Sie ein Element auf den Stapel schieben, wird der Stapelzeiger um die Größe des Elements angepasst, also entweder dekrementiert oder inkrementiert, abhängig von der Richtung, in der der Stapel im Speicher wächst, indem er auf die nächste Speicherzelle zeigt und das neue oberste Element in den Stapelbereich kopiert. Abhängig von der genauen Implementierung kann der Stapelzeiger am Ende einer Push-Operation auf die nächste nicht verwendete Position im Stapel oder auf das oberste Element im Stapel zeigen. Wenn der Stapel auf das aktuell oberste Element zeigt, wird der Stapelzeiger aktualisiert, bevor ein neues Element auf den Stapel verschoben wird. Wenn es auf die nächste verfügbare Position im Stapel zeigt, wird es aktualisiert, nachdem das neue Element auf den Stapel verschoben wurde.

Illustration

Ein Stapelspeicher ist mit einem Stapel von Umzugskisten vergleichbar. Es kann immer eine neue Kiste oben auf den Stapel gepackt werden (entspricht push) oder eine Kiste von oben heruntergenommen werden (entspricht pop). Der Zugriff ist im Regelfall nur auf das oberste Element des Stapels möglich. Ein Hinzufügen oder Entfernen einer Kiste weiter unten im Stapel ist nicht möglich. Es gibt aber in manchen Implementierungen Befehle, um die obersten Elemente zu vertauschen (SWAP, ROT).

Geschichte

Die Verwendung eines Stapelspeichers zur Übersetzung von Programmiersprachen wurde 1957 von Friedrich L. Bauer und Klaus Samelson unter dem Namen „Kellerprinzip“ patentiert und etwa zur selben Zeit unabhängig vom australischen Philosophen Charles Hamblin entwickelt. Die lange ausgebliebene internationale Anerkennung und Ehrung ihrer Leistung erfolgte erst im Jahr 1988. Bauer erhielt den renommierten Computer Pioneer Award (IEEE) für Computer Stacks. Samelson war bereits 1980 verstorben.

Anwendungen

Mit Stapelspeichern kann man Terme und Syntaxen einfach auf richtige Verschachtelung prüfen. Dies wird oft z. B. bei der Verarbeitung von BB-Codes und XML-Dokumenten benötigt.

Abstrakter Datentyp

Bei der Implementierung eines Stapelspeichers als abstrakter Datentyp in einer einfach verketteten Liste wird der Zeiger auf Daten gespeichert, anstelle die Daten in jedem Knoten zu speichern. Das Programm weist den Speicher für die Daten zu und die Speicheradresse wird an den Stapelspeicher übergeben. Der Kopfknoten und die Datenknoten sind im abstrakten Datentyp gekapselt. Eine aufgerufene Funktion kann nur den Zeiger auf den Stapelspeicher sehen. Der Datentyp enthält auch einen Zeiger auf die Oberseite und den Zähler für die Anzahl der Elemente im Stapel.

struct StackNode {
    void *dataPointer;
    StackNode *link;
};

struct Stack {
    int count;
    StackNode *top;
};

Programmierung

Compiler bzw. Interpreter für Programmiersprachen nutzen gewöhnlich push-Operationen vor dem Aufruf eines Unterprogramms, um an dieses Parameter zu übergeben. Weil der Compiler die Typen der Parameter kennt, können sie unterschiedliche Größen haben. Ähnlich können so auch Ergebnisse des Unterprogramms zurückgegeben werden. Für lokale Variablen des Unterprogramms wird dieser Mechanismus nochmal erweitert, indem auch für sie auf dem Stapelspeicher Platz reserviert wird. Dadurch wird das Unterprogramm dann rekursiv aufrufbar. Bei der Umwandlung eines rekursiven Unterprogramms in ein iteratives Unterprogramm muss dieser Mechanismus häufig explizit implementiert werden.

Programmiersprachen, die auf eine prozessbasierte virtuelle Maschine aufsetzen, zum Beispiel Java, P-Code-Pascal, optimieren den kompilierten Zwischencode für die Verwendung eines Stapels, um zur Laufzeit die Interpretation dieses Zwischencodes zu beschleunigen.

#include <memory>
#include <stdexcept>
#include <utility>

using namespace std;

template <typename T>
class stack {
    struct item {
        T value;
        unique_ptr<item> next = nullptr;

        item(T& _value): value(_value) {}
    };

    unique_ptr<item> _peek = nullptr;
    size_t _size = 0;

public:
    // erzeugt einen leeren Stack
    stack() {}

    // erzeugt einen Stack mit n Elementen von T
    stack(size_t n, T _value) {
        for (size_t i = 0; i < n; ++i)
            push(_value);
    }

    // Kopierkonstruktor
    stack(stack<T>& rhs) {
        *this = rhs;
    }

    // Zuweisungsoperator
    stack& operator=(stack<T>& rhs) {
        // Überprüfe ob ein Stack sich selbst zugewiesen wird
        if (this == &rhs)
            return *this;

        item* traverse = rhs._peek.get();

        // Absteigen zum ersten Element, dann zum zweiten etc.
        while (traverse != nullptr) {
            push(traverse->value);
            traverse = traverse->next.get();
        }

        return *this;
    }

    void push(T& _value) {
        unique_ptr<item> temp = make_unique<item>(_value);
        temp.swap(_peek);
        // next des letzten Stackelements ist ein nullptr
        _peek->next = move(temp);
        _size++;
    }

    T pop() {
        if (_peek == nullptr)
            throw underflow_error("Nothing to pop.");

        T value = _peek->value;
        _peek = move(_peek->next);
        _size--;

        return value;
    }

    T& peek() {
        if (_peek == nullptr)
            throw underflow_error("Nothing to peek.");

        return _peek->value;
    }

    size_t size() {
        return _size;
    }
};

#include <stdbool.h>
#include <stddef.h>

#define LEN 100

int data[LEN];
size_t count = 0;

bool is_empty() {
    return count == 0;
}

bool is_full() {
    return count == LEN;
}

void push(int value) {
    if (is_full())
        return;

    data[count] = value;
    count++;
}

int pop() {
    if (is_empty())
        return 0;

    count--;
    return data[count];
}

int peek() {
    if (is_empty())
        return 0;

    return data[count - 1];
}

size_t size() {
    return count;
}

class Stack<T> {
    private class Item {
        T value; // Das zu verwaltende Objekt
        Item next; // Referenz auf den nächsten Knoten

        Item(T value, Item next) {
            this.value = value;
            this.next = next;
        }
    }

    private Item peek;

    // Prüft, ob der Stapel leer ist
    public boolean empty() {
        return this.peek == null;
    }

    // Speichert ein neues Objekt
    public void push(T value) {
        this.peek = new Item(value, this.peek);
    }

    // Gibt das oberste Objekt wieder und entfernt es aus dem Stapel
    public T pop() {
        T temp = this.peek.value;

        if (!empty())
            this.peek = this.peek.next;

        return temp;
    }

    // Gibt das oberste Objekt wieder
    public T peek() {
        return !empty() ? this.peek.value : null;
    }
}

class Stack:

    def __init__(self):
        self._data = []

    def is_empty(self):
        return len(self._data) == 0

    def push(self, element):
        self._data.append(element)

    def pop(self):
        if self.is_empty():
            return None

        return self._data.pop()

    def peek(self):
        if self.is_empty():
            return None

        return self._data[-1]

    def __str__(self):
        return self._data.__str__()


def main():
    my_stack = Stack()
    print(my_stack.is_empty())
    my_stack.push(5)
    my_stack.push(3)
    print(my_stack.is_empty())
    print(my_stack)
    print(my_stack.peek())
    my_stack.pop()
    print(my_stack.peek())


if __name__ == "__main__":
    main()

// Bindet den Datentyp stack in das Programm ein
#include <stack>
#include <iostream>

using namespace std;

int main()
{
    // Initialisiert einen Stapel mit dem Elementtyp string
    auto myStack = stack<string>();

    // Legt nacheinander 3 Elemente auf den Stapel
    myStack.push("Kreuz Bube");
    myStack.push("Herz Dame");
    myStack.push("Karo König");

    // Ausgabe auf der Konsole ("Karo König")
    cout << "Die Höhe des Stapels ist " << myStack.size()
         << " und die oberste Karte des Stapels ist " << myStack.top() << endl;

    // Entfernt das oberste Element ("Karo König")
    myStack.pop();

    // Ausgabe auf der Konsole ("Herz Dame")
    cout << "Die Höhe des Stapels ist " << myStack.size()
         << " und die oberste Karte des Stapels ist " << myStack.top() << endl;

    // Legt ein Element oben auf den Stapel
    myStack.push("Karo Ass");

    // Ausgabe auf der Konsole ("Karo Ass")
    cout << "Die Höhe des Stapels ist " << myStack.size()
         << " und die oberste Karte des Stapels ist " << myStack.top() << endl;
}

Verwandte Themen

Eine First-In-First-Out-Datenstruktur nennt sich Warteschlange (englisch Queue). Beide Strukturen zeigen ein unterschiedliches Verhalten, haben aber dieselbe Signatur (d. h. Methoden-Struktur), weswegen sie oft zusammen unterrichtet werden.

Eine andere Art Speicher zu verwalten ist die dynamische Speicherverwaltung, die zur Laufzeit entstehende Speicheranforderungen bedienen kann. Dieser Speicher wird oft als Heap bezeichnet und wird eingesetzt, wenn die Lebensdauer der zu speichernden Objekte unterschiedlich ist und nicht dem eingeschränkten Prinzip des Stapelspeichers oder der Warteschlange entspricht.

Siehe auch

• Feld (Datentyp)
• Liste (Datenstruktur)
• Floodfill
• Deque
• Stacktrace

Literatur

• Patent DE1094019: Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens. Angemeldet am 30. März 1957, veröffentlicht am 1. Dezember 1960, Erfinder: Friedrich Ludwig Bauer, Klaus Samelson (Erteilt 12. August 1971).‌

Weblinks

Einzelnachweise

1. ↑ Friedrich L. Bauer, Gerhard Goos: Informatik. Eine einführende Übersicht. Erster Teil. 3. Auflage. Springer, Berlin 1982, ISBN 3-540-11722-9, S. 222. „Die Bezeichnung ‚Keller‘ hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingeführt.“
2. ↑ Patent DE1094019: Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens. Angemeldet am 30. März 1957, veröffentlicht am 1. Dezember 1960, Erfinder: Friedrich Ludwig Bauer, Klaus Samelson.‌
3. ↑ GeeksforGeeks: Abstract Data Types
4. ↑ www.geeksforgeeks.org: Stack Data Structure (Introduction and Program)
5. ↑ Universität Ulm: Einfacher Stack: in C++ und im C-Stil
6. ↑ www.geeksforgeeks.org: Stack Class in Java
7. ↑ Microsoft Docs: stack Class