2.4. Stapel

2.4. Stapel
	Kapitel 2. Einfache Datentypen und einfache Containertypen

Schauen wir doch einmal kurz in unserem Geschirrschrank nach unseren besten Tellern. Was sehen wir? Wir haben sie im Schrank aufeinandergestapelt. Wenn wir vor einem feudalen Mahl einen^[19] Teller benötigen, welchen nehmen wir dann? Wir nehmen immer den obersten vom Stapel, nie einen in der Mitte und schon gar nicht den untersten. Wenn wir einen Teller nach nach dem Abwasch wieder in den Schrank stellen, wohin stellen wir ihn? Wir stellen ihn immer als obersten Teller oben auf den Stapel.

Solche Strukturen, bei denen Elemente in einer linearen Abfolge gespeichert sind, und die Einfügen und Löschen immer nur an einer der Seite der Folge erlauben, kommen nicht nur im täglichen Leben, sondern auch in der Algorithmik recht häufig vor. Sie heißen Stapel (engl. stack), und das Ablegen bzw. Wegnehmen von Elementen wird als Push bzw. Pop bezeichnet. Eine andere Bezeichnung für Stapel ist Keller.

Weil Elemente immer nur ganz oben auf dem Stapel (engl. top of stack) eingefügt oder von dort herunter genommen werden, ist das jeweils letzte Element, das in die Struktur eingebracht wurde, immer das erste, das wieder herausgeholt wird. Man sagt daher, dass Stapel nach dem LIFO-Prinzip („last in first out“) arbeiten.

Abbildung 2.17. Ein Stack

LEDA bietet als Implementierung für Stapel die Klassen stack und b_stack an. Bei ersterer handelt es sich um Stapel, die beliebig viele Elemente stapeln können. Zweitere ist dann besonders nützlich, wenn wir im Voraus wissen, dass nur eine bestimmte, begrenzte Anzahl von Elementen jemals auf dem Stapel gestapelt wird („bounded stack“).

Wozu überhaupt einen Stapel benutzen?

Der aufmerksame Leser wird jetzt sagen: „Wozu brauche ich denn diese speziellen Klassen überhaupt? Ich kann das alles doch auch mit einer list machen, die ich dank dieses Tutoriums nun so gut beherrsche. Da kann ich doch einfach mit push() und pop() am Anfang der Liste etwas einfügen bzw. wegnehmen; sie verhält sich dann doch genau wie ein Stapel! Wozu soll ich mich jetzt hier also mit überflüssigen Stapeln herumquälen?“ Diese Einwände sind durchaus berechtigt, wenn wir nur auf die Funktionalität schauen.^[20] Aber es gibt mindestens drei gute Gründe für den Gebrauch eines „echten“ Stapels:

Ein Programm wird lesbarer und Fehler sind darin leichter zu finden, wenn expliziter Gebrauch von spezialisierten Datenstrukturen gemacht wird.
Einfachere Schnittstellen (wie im Falle der Klasse stack) ermöglichen spezialisierte Implementierungen der Struktur, die besonders zeit- oder platzeffizient sind. So ist z. B. die Klasse stack mit Hilfe der besonders platzsparenden Klasse slist implementiert.
Die Verwendung einer spezialisierten Datenstruktur führt oft zu größerer Einsicht in die Problemstellung, aus der heraus sich dann weitere Verbesserungen der Implementierung ergeben können. Es könnte z. B. durch den Gebrauch eines Stapels auffallen, dass dieser während der gesamten Laufzeit nur eine im Voraus bekannte Anzahl an Elementen speichern wird. Dann wäre ein b_stack die Struktur der Wahl und seine Verwendung hätte eine Verbesserung der Platzeffizienz zur Folge.

Das sollte uns nun Ansporn genug sein, den guten, alten Stapeln ein wenig Zeit zu widmen.

^[19]Natürlich speisen wir i. d. R. bei einem feudalen Mahl nicht allein. Dann nehmen wir eben die obersten Teller vom Stapel.

^[20]Und viele LEDA-Benutzer schenken tatsächlich den Klassen stack und b_stack und den verwandten Klassen queue und b_queue keine Beachtung und verwenden einfach immer die Klasse list.


2.3.8. Einfach verkettete Listen (Klasse slist)		2.4.1. Stapel mit unbeschränkter Elementanzahl (Klasse stack)