Java Stack – Wie du einen Stapelspeicher implementierst

Keylearnings:

• Was ist ein Stack bzw. Stapelspeicher?
• Was bedeutet LIFO?
• Die Java Stack push Operation.
• Die Java Stack pop Operation.
• Die Java Stack peek Operation.
• Wie du einen Stack mit Hilfe von Bordmitteln implementierst!

Ich war sauer! Sogar stink sauer!

Offenbar arbeitet mein Zahnarzt mit einem Stack.

Ich war als erstes da und kam als letztes dran.

Der Typ, der erst kurz vor Feierabend kam, durfte hingegen sofort ins Sprechzimmer. So eine Frechheit!

Und genau über diese Frechheit wollen wir uns in diesem Artikel unterhalten.

Denn es gibt eine Datenstruktur, die nach dem gleichen Prinzip arbeitet. Nämlich der sogenannte Stapelspeicher, der neudeutsch auch Stack genannt wird.

Der Stack bzw. Stapelspeicher ist eine Datenstruktur, bei der immer nur auf den zuletzt gespeicherten Datensatz zugegriffen werden kann.

Dieses Verarbeitungsprinzip wird LIFO Prinzip (Last in First out) genannt.

Wir können uns einen Stack bildlich wie einen Turm aus übereinander gestapelten Bauklötzen vorstellen. In jedem dieser Bauklötze können Daten gespeichert werden.

Einen Turm kann man vergrößern indem man einen weiteren Stein auf den Turm legt. Diese Operation nennt man Push.

Oder man kann den Turm verkleinern indem man den obersten Stein entfernt. Bei dieser Operation spricht man von einem Pop.

Bei einem Stack dürfen wir immer nur mit dem obersten Stein arbeiten, auf alle anderen Steine haben wir keinen Zugriff.

Die Anwendungsgebiete des Stack

Vielleicht denkst du jetzt „Boah, was für ein Quatsch!“ damit kann man doch keinen Blumentopf gewinnen.

Aber das ist nicht richtig!

Überleg dir z.B. mal wie der Zurückknopf in deinem Internetbrowser funktioniert.

Nehmen wir an du hast nacheinander drei Seiten besucht.

Und bist jetzt hier gelandet, möchtest aber wieder zurück zu der zuerst besuchten Seite.

Was machst du?

Du drückst dreimal auf den Zurückknopf des Internetbrowsers und landest wieder auf der zuerst besuchten Seite.

Aber woher weiß dein Browser, auf welchen Seiten du warst?

Ganz einfach! Er verwendet einen Stack.

Mit Hilfe eines Stapelspeichers ist das ganz einfach!

Immer bevor du eine Seite verlässt, wird die Adresse der Seite mittels einer Push-Operation auf einen Stack gelegt.

Der erste Push findet in dem Moment statt, an dem du Seite 1 verlässt und Seite 2 besuchst, dann wir die Adresse von Seite 1 auf dem Stack abgelegt und der Stack besteht aus einem einzelnen Element.

Weiter geht’s mit dem verlassen der Seite 2 und dem Besuch von Seite 3. Wieder das gleiche Spielchen, nur wird diesmal Seite 2 auf den Stack gelegt. Unser Stapelspeicher enthält jetzt zwei Elemente.

Und zu guter letzt der Wechsel von Seite 3 auf die Seite, auf welcher du dich gerade befindest, der einen Push von Seite 3 auslöst und die Anzahl der Elemente auf dem Stack auf insgesamt drei erhöht.

Dir gefällt aber Seite 1 am besten und willst wieder dahin zurück.

Also betätigst du den Zurückknopf deines Browsers, der einen Pop auf den Stack auslöst und so die Adresse von Seite 3 erhält.

Ein Pop entfernt den obersten Datensatz des Stacks, daher sieht der Stapelspeicher danach wie folgt aus:

Leider ist auch Seite 3 nicht zufriedenstellend, weshalb du erneut den Zurückknopf betätigst. Oben auf dem Stapel liegt jetzt die Adresse von Seite 2, auf die der Browser ein Pop ausführt und die Seite anzeigt.

Wieder wird der oberste Datensatz des Stacks entfernt und der Stapelspeicher enthält jetzt nur noch einen einzigen Datensatz.

Eine erneute Verwendung des Zurückknopfes bringt dich wieder an den Anfang, also zu Seite 1, und der Stapelspeicher des Browsers ist wieder leer.

Stack auf Basis einer verketteten Liste

Was ist notwendig um einen Stack aufzubauen?

1. Wir benötigen genauso viele „Datenbehälter“ wie unser Stack hoch ist.
2. Wir müssen Zugriff auf den obersten Datenbehälter haben.
3. Wir müssen von jedem Datenbehälter auf den jeweils darunterliegenden Behälter zugreifen können.

Das erinnert an die Knoten einer verketteten Liste, die ganz ähnliche Eigenschaften haben.

In jedem Knoten werden Daten und eine Referenz auf den Nachfolger gespeichert.

Hier nochmal zur Erinnerung:

1: public class Knoten {

2:	private String data;
3:	private Knoten next;

4:	public String getData() {
5:		return data;
6:	}
	
7:	public Knoten(String data, Knoten next) {
8:		this.data = data;
9:		this.next = next;
10:	}

11:	public void setData(String data) {
12:		this.data = data;
13:	}
14:	public Knoten getNext() {
15:		return next;
16:	}

17:	public void setNext(Knoten next) {
18:		this.next = next;
19:	}	
20: }

Die Klasse Knoten enthält zwei Objektvariablen (Zeile 2 und 3), zum einen eine Variable data für die zu speichernden Daten, die wir als vom Typ String annehmen, und zum anderen einen Verweis next auf das nächste Speicherelement.

Über den Konstruktor können wir sowohl die Daten, als auch das Nachfolgeelement festlegen. Des Weiteren enthält unsere Klasse noch die üblichen getter- und setter-Methoden.

Fein! Beginnen wir mit der Arbeit und bauen hieraus einen Stack.

Überlegen wir uns zunächst, welche Elemente wir für den Aufbau eines Stacks benötigen.

Da wir alle Operationen immer auf das oberste Element im Stack anwenden, benötigen wir auf jeden Fall eine Variable vom Typ Knoten, mit dem wir das oberste Element referenzieren können.

Und das ist es eigentlich auch schon alles.

Wir wollen uns das Leben allerdings noch etwas leichter machen und unserem Stack eine maximale Höhe zuordnen und die Anzahl der Elemente, die unser Stapelspeicher enthält zählen.

Daher sieht die Grundstruktur unserer Stack-Klasse StackSpeicher wie folgt aus:

1: public class StackSpeicher {

2:	private final static int MAX_HOEHE = 10;
3:	private Knoten obersterKnoten = null;
4:	private int aktuelleHoehe = 0;

}

In Zeile zwei definieren wir mit Hilfe des Schlüsselwortes final eine Konstante MAX_HOEHE, mit der wir die Höhe unseres Stacks mit 10 beschränken.

Die in Zeile drei deklarierte Variable obersterKnoten verwenden wir um eine Referenz auf das oberste Element des Stapels zu speichern.

Aufgabe der Variable aktuelleHoehe ist es, zu jedem Zeitpunkt die Höhe des Stacks zu protokollieren. Diese Variable müssen wir bei einem Push inkrementieren und bei einem Pop dekrementieren.

Okay, kümmern wir uns als nächstes um die push Methode.

Die Java Stack Push Operation

Die Push Operation erzeugt einen neuen Knoten und legt diesen auf dem Stack ab. Hierbei müssen wir darauf achten, dass die maximal zulässige Höhe des Stacks noch nicht erreicht ist.

Daher benötigen wir  eine Java Exception, die geworfen wird sobald versucht wird einen Knoten auf einen bereits vollen Stapel zu legen.

public class OverflowException extends Exception {

	public OverflowException(){
		System.out.println("Der Stack ist voll");
	}
	
}

Die OverflowException werfen wir wenn ein Push ausgeführt wird und die maximal Höhe des Stapels bereits erreicht ist, d.h. aktuelleHoehe == MAX_HOEHE gilt.

public void push(String daten) throws OverflowException{
1:   if (aktuelleHoehe == MAX_HOEHE)
2:		throw new OverflowException();
		
3:   Knoten knoten = new Knoten(daten,obersterKnoten);
4:   obersterKnoten = knoten;
5:   aktuelleHoehe++;
6:}

Damit sind auch bereits die Zeilen eins und zwei erklärt.

Die echte Action passiert in den Zeilen drei bis fünf.

Mit der Push Operation wollen wir einen neuen Knoten auf den Stack legen, den wir in Zeile drei erzeugen.

Der Konstruktor des Knoten erwartet im ersten Argument die Daten, welche auf den Stapel gelegt werden sollen, die wir über den String Parameter daten an die push Methode übergeben. Das zweite Argument setzt den Nachfolger des neu erzeugten Knoten.

Da wir den neuen Knoten oben auf den Stapel legen, hat dieser den bisher obersten Knoten (obersterKnoten) als Nachfolger.

In Zeile vier machen wir den neu angelegten Knoten zum neuen obersten Knoten, und da sich mit jedem Push die Höhe des Stapels um Eins erhöht, wird in Zeile fünf die Variable aktuelleHoehe inkrementiert.

Damit haben wir die Möglichkeit Daten auf den Stack zu legen. Um die Daten vom Stack auslesen zu können beschäftigen wir uns als nächstes mit der Pop-Operation.

Die Java Stack Pop Operation

Auch bei einem Pop kann was schief gehen! Ein ahnungsloser Anwender könnte beispielsweise versuchen einen Pop auf einen leeren Stack durchzuführen. Auch das sollten wir mit Hilfe einer Java Exception abfangen.

 public class UnderflowException extends Exception{
	
	public UnderflowException(){
		System.out.println("Der Stapel ist leer!");
	}
	
}

Diese UnderflowException werfen wir, wenn ein Pop auf einen leeren Stack stattfindet, d.h. aktuelleHoehe == 0 gilt. In diesem Fall werfen wir die Exception in Zeile drei.

1: public String pop() throws UnderflowException{
2:	if (aktuelleHoehe == 0){
3:		throw new UnderflowException();
4:	}
		
5:	String daten = obersterKnoten.getData();		
6:	obersterKnoten= obersterKnoten.getNext();
8:      aktuelleHoehe--;
9:	return daten;
10:}

Auch in der Pop() Methode geschehen die wichtigen Dinge in den Zeilen fünf bis sieben.

Ziel der Pop-Methode ist es die Daten des obersten Knoten zurück zuliefern und anschließend vom Stapel zu entfernen.

Das Zurückliefern der Daten erfordert lediglich einen Aufruf der getter Methode getData() in Zeile fünf. Hier speichern wir die Daten in der String Variable daten, die wir in Zeile sieben als Rückgabewert zurück liefern.

Um den Knoten zu entfernen setzen wir, in Zeile sechs, den obersten Knoten des Stacks auf den Nachfolger des bisher obersten Knoten. Da dieser Knoten danach nicht mehr referenziert wird, gibt der Garbage Collector den Speicher frei.

Jetzt fehlt uns nur noch eine Kleinigkeit. Oft wollen wir nur lesend auf den Stapelspeicher zugreifen ohne den obersten Knoten des Stacks zu entfernen. Diese Operation nennt man Peek.

Die Java Stack Peek Operation

Die Peek Operation ist schnell implementiert.

Wir müssen lediglich die Pop Methode kopieren und die Stelle, an der der oberste Knoten angepasst wird entfernen. Und das sieht dann wie folgt aus:

1: public String peek() throws UnderflowException{
2:	if (aktuelleHoehe == 0){
3:		throw new UnderflowException();
4:	}	
5:	   return obersterKnoten.getData();
6:	}
7: }

Wieder beginnen wir mit einer java Exception, die den Fall abfängt, dass ein Peek auf einen leeren Stack stattfindet.

Anschließend müssen nur noch die Daten des oberen Knoten als Rückgabewert zurück geliefert werden, was wir durch einen Aufruf der entsprechenden getter Methode in Zeile fünf bewerkstelligen.

Machen wir eine Probefahrt!

So wir sind fertig! Trauen wir uns einen Testlauf zu machen.

Wir wollen unseren Stapelspeicher an dem Beispiel von oben Testen, bei dem wir wie in einem Browser drei Seiten auf dem Stack ablegen, die wir anschließend mit Hilfe dreier Pop’s wieder entfernen.

Beginnen wir mit dem Test der Push-Operation und legen nacheinander die Seiten eins, zwei und drei auf dem Stack ab.

Um zu sehen, ob ein Push erfolgreich war geben wir mit Hilfe eines Peek’s nach jedem Push das oberste Element des Stapels aus.

Da sowohl die push() als auch die peek Methode eine Java Exception wirft, müssen wir unsere Aufrufe in eine try-catch Kontrollstruktur einbetten. Hier der entsprechende Code:

1:      StackSpeicher stack = new StackSpeicher();
2:	try {
3:	        stack.push("Seite 1");
4:		System.out.println(stack.peek());
5:		stack.push("Seite 2");
6:		System.out.println(stack.peek());
7:		stack.push("Seite 3");
8:		System.out.println(stack.peek());
9:	} catch (OverflowException e) {
10:		System.out.println("Überlauf");
11:	} catch (UnderflowException e) {
12:		System.out.println();
13:	}

In Zeile Eins erzeugen wir zunächst eine Instanz unseres Stapelspeichers.

Innerhalb der try-catch Kontrollstruktur wird dann abwechselnd die push() und die peek() Methode aufgerufen. D.h. wir legen Seite 1 auf den Stapel, lesen das oberste Element aus und geben es auf dem Bildschirm aus. Dasselbe wiederholen wir dann mit Seite 2 und Seite 3.

Schauen wir uns die Progammausgabe an. Welches Ergebnis hast du erwartet?

Seite 1
Seite 2
Seite 3

Wie beabsichtigt lag nachdem ersten Push Seite 1, nachdem zweiten Push Seite 2 und nachdem letzten Push Seite 3 ganz oben auf dem Stapel.

Unser Stapel sieht am Ende des obigen Programms also folgendermaßen aus:

Der Test der Push- und Peek-Operationen kann also positiv gewertet werden.

Fehlt noch der Test der Pop-Operation. Versuchen wir also alle drei Elemente des Stapels mittels der Pop() Methode aus dem Stapel zu entfernen und auf dem Bildschirm auszugeben.

System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());

Schauen wir uns wieder das Ergebnis an:

Seite 3
Seite 2
Seite 1

Genau wie es das LIFO Prinzip vorschreibt, wird der Datensatz den wir als letztes in die Datenstruktur eingefügt haben als erstes ausgegeben.

Glückwunsch! Das bedeutet wir haben erfolgreich einen Stack gebaut.

Fazit: Der Java Stack ist eine einfache aber dafür sehr leistungsfähige Datenstruktur, die in der Praxis vielfache Anwendung findet. Ich habe mich in diesem Artikel bemüht ein grundlegendes Verständnis dieser Datenstruktur zu vermitteln. In der Praxis kannst du dir einen Menge Arbeit ersparen indem du auf die fertigen Klassen zurückgreifst, die Java zur Verfügung stellt.

Und wie du diese benutzt, Zeige ich dir im folgenden Video:

Ich freue mich auf deine Fragen im Kommentarbereich.

Hat dir der Artikel gefallen? Dann folge uns am besten gleich auf Facebook!