Kleines Nachschlagewerk Informatik
ADT Stack
Worum geht es?
Ein Stack ist eine simple Datenstruktur, die nur Einfügen und Auslesen ohne Möglichkeit der Positionsangabe (Adressierung) zulässt. Konkret ist es beim Stack so, dass das zuletzt eingefügte Element zuerst gelesen wird (LIFO - Last In First Out).

Aus diesem Grunde werden Stacks auch oft Stapelspeicher oder Kellerspeicher genannt.
Interface (minimal)
Ein Stack braucht mindestens zwei Methoden: das Einfügen und das Auslesen. Dabei ist es so, dass das Auslesen auch gleichzeitig zum Entfernen eines Elementes führt. Ein Auslesen des TOS (Top Of Stack) ohne Entfernen ist somit eine Kombination von Auslesen und Einfügen.

Für das Einfügen und das Auslesen haben sich die Methodennnamen push und pop eingebürgert.



Interface nach Vorgabe
Die Vorgaben des Ministeriums beruhen auf einer komfortableren Variante des Stacks. Zusätzlich bietet dieser Stack eine Methode isEmpty an, mit der geprüft werden kann, ob der Stack leer ist. Außerdem ist eine Abfrage des TOS ohne Entfernen mit der Methode top möglich. Im Gegenzug dazu entfernt pop nur das Element, gibt also keinen Wert zurück.



Anwendung
Stacks begegnet man



Achtung, alle oben genannten Beispiele nutzen i.A. das simple Interface (Lesen = Entfernen).