Stapel

Einführung

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. Objekte der Klasse Stack (Keller, Stapel) verwalten beliebige Objekte nach dem Last-In-First-Out-Prinzip, d.h., das zuletzt abgelegte Objekt wird als erstes wieder entnommen.

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. (Quelle http://de.wikipedia.org/wiki/Stapelspeicher)

Aufbau

Ein Stapel sollte über folgende Methoden bzw. Konstruktoren verfügen:

Konstruktor

• Stack(): Ein leerer Stapel wird erzeugt.

Methoden

• boolean isEmpty(): Die Anfrage liefert den Wert true, wenn der Stapel keine Objekte enthält, sonst liefert sie den Wert false.

• void push(Object pObject): Das Objekt pObject wird oben auf den Stapel gelegt. Falls pObject gleich null ist, bleibt der Stapel unverändert.

• void pop(): Das zuletzt eingefügte Objekt wird von dem Stapel entfernt. Falls der Stapel leer ist, bleibt er unverändert.

• Object top(): Die Anfrage liefert das oberste Stapelobjekt. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurück gegeben.

Beispiel

Veranschaulichen wir uns die Arbeitsweise der Stack-Operationen:

1. Nach Aufruf der Stack()-Operation ist der Stack zwar vorhanden, aber er enthält noch keine Elemente.

2. Nach Aufruf von Push(12) enthält der Stack genau ein Element, nämlich die Zahl 12.

3. Nach Aufruf von Push(8) sind schon zwei Elemente im Stack enthalten. Die 8 wurde zuletzt zugefügt, befindet sich also oben im Stack.

4. Wenn Pop() aufgerufen wird, wird die 8 wieder entfernt - sie war ja die zuletzt zugefügte Zahl.

5. Nach Push(15) besteht der Stack wieder aus zwei Elementen. Die 15 wurde zuletzt gepusht, also findet sie sich oben im Stack wieder.

6. Nach Push(13) besteht der Stack sogar aus drei Elementen. Und wieder ist die zuletzt gepushte Zahl ganz oben im Stack.