Stapelspeicher
Der Stack ist eine der wichtigsten Datenstrukturen in der Informatik. Um zu verstehen, wie ein Stapel funktioniert, stellen Sie sich ein verdecktes Spielkartenspiel vor. Wir können nur leicht auf die oberste Karte zugreifen. Wenn wir uns die oberste Karte ansehen wollen, können wir zwei Dinge tun: Wir können einen Blick auf sie werfen, sie aber auf dem Stapel liegen lassen, oder wir können sie abspringen lassen. Wenn wir den obersten Gegenstand abspringen lassen, nehmen wir ihn vom Stapel. Wenn wir eine weitere Karte oben auf den Stapel legen wollen, schieben wir sie.
Ein Stapel wird als LIFO-Sammlung (last-in-first-out) bezeichnet. Das bedeutet, dass das letzte Ding, das wir hinzugefügt (geschoben) haben, das erste Ding ist, das abgezogen (gepusht) wird. Wenn die letzte Karte, die wir auf unseren Kartenstapel gelegt haben, ein Ass war, dann ist die erste Karte, die wir von oben abgezogen haben, dasselbe Ass.
Zwei Aktionen auf einem Stapel: Push und Pop.
Geschichte
Der Stapel wurde erstmals 1955 vorgeschlagen und dann 1957 von dem Deutschen Friedrich L. Bauer patentiert. Dasselbe Konzept wurde unabhängig voneinander, etwa zur gleichen Zeit, vom Australier Charles Leonard Hamblin entwickelt.
Andere Operationen
In modernen Computersprachen wird der Stack in der Regel mit mehr Operationen als nur "push" und "pop" implementiert. Einige Implementierungen haben eine Funktion, die die aktuelle Länge des Stacks zurückgibt. Eine weitere typische Hilfsoperation ist "top" (auch als "peek" bekannt), die das aktuelle oberste Element des Stapels zurückgeben kann, ohne es zu entfernen. Eine weitere häufige Operation ist "dup", die eine Kopie des Elements am oberen Ende des Stapels erstellt.
Verwandte Seiten
- Stapelmaschine
