Datenstruktur: Stack

Ein Stack, auch Stapel oder Kellerspeicher genannt, ist eine recht einfache Datenstruktur zur Speicherung von Daten. Der Stack funktioniert auch wie ein Stapel im "echten Leben": Neue Elemente werden oben auf den Stapel drauf gelegt und es wird immer nur auf das oberste Element zugegriffen. Man spricht hierbei von dem Last-In First-Out (LIFO) Prinzip.

Aufgrund dieser Einfachheit der Struktur besitzt der Stack auch nur drei wesentliche Methoden die im nachfolgenden erklärt werden. Ein Stapel hat immer eine maximale Größe, die gerne mit N beschrieben wird.

bool isEmpty() gibt true zurück, wenn der Stapel leer ist, d.h. er kein Element besitzt. Sonst wird false zurückgegeben.

void push(Element e) legt das Element e oben auf den Stapel. Voraussetzung: Der Stapel muss weniger als N Elemente besitzen. Andernfalls gibt es einen Stackoverflow (Stapelüberlauf)

Element pop() entfernt das zuletzt eingefügte Element, also das oberste, und gibt es dann zurück. Voraussetzung: Der Stapel darf nicht leer sein.

Dies sind die wesentlichen Funktionen eines Stacks. Oft bietet es sich auch an noch weitere Funktionen zu implementieren. Beispiele dafür sind:

int size() gibt die aktuelle Größe des Stapels zurück.

int getMaxSize() gibt die maximale Größe N des Stapels zurück.

Element top() gibt das oberste Element zurück.