Wie du eine verkettete Liste verwendest um einen Stack zubauen.

Heute möchte ich auf folgende Leserfrage antworten.

Hey Kim, wie kann man aus einer verketteten Liste einen Stack bauen?

Eine sehr gute Frage, deren Beantwortung uns ein tieferes Verständnis der beiden Datenstrukturen Stack und der verketteten Liste verschafft.

Und in der Tat ist die verkettete Liste ein hervorragendes Fundament für einen Stack. Aber warum nur?

Diese Frage wollen wir als erstes beantworten.

Warum ist die verkettete Liste als Grundlage für einen Stack ideal?

Rufen wir uns die wichtigsten Eigenschaften dieser beiden Datenstrukturen nochmal in Erinnerung!

Der Stack

Der Stack ist eine Datenstruktur, die nach dem sogenannten LIFO (Last in First Out) Prinzip arbeitet. Wir können also nur auf den Datensatz zugreifen, den wir als letztes eingefügt haben.

Veranschaulichen können wir einen Stack als einen Stapel von Bauklötzen.

Den einzigen Bauklotz, den wir entfernen können ohne dass der gesamte Stapel in sich zusammenfällt ist der Bauklotz, der ganz oben auf dem Stapel liegt.

Der Stack hat im Wesentlichen zwei Operationen.

Zum einen die push Operation, um einen neuen Datensatz auf den Stack zu legen, und zum anderen die pop Operation um den obersten Datensatz vom Stapel zunehmen.

Außerdem besitzt ein Stack optional noch die peek Methode, mit welcher der Inhalt des obersten Datensatzes ausgelesen werden kann ohne diesen aus dem Stapel zu entfernen.

Die verkettete Liste

Die verkettete Liste besteht aus einer Verkettung von sogenannten Knoten.

Ein Knoten ist ein Behälter, der Daten aufnehmen kann und außerdem einen Verweis auf den entsprechenden Nachfolgeknoten enthält

Bei einer verketteten Liste können wir nicht wahlfrei auf deren Elemente zugreifen.

Um beispielsweise in obiger Abbildung auf den Knoten mit dem Wert Nudeln zu kommen. Müssen wir zunächst von dem ersten Knoten (Ei) auf den zweiten Knoten (Tomatensuppe) wandern um schließlich von diesem zum dritten Knoten (Nudeln) zu gelangen.

Hinweis: Die Standardklasse LinkedList besitzt eine Methode get, die den Anschein erweckt, als könnte man wahlfrei auf die Elemente der Liste zugreifen. Allerdings arbeitet diese Methode intern ebenfalls iterativ, d.h. genau wie oben beschrieben.

Für unsere Stack Implementierung verwenden wir die JAVA Standardklasse LinkedList.

Die beiden Operationen, die uns interessieren sind add, removeLast und getLast.

Mit Hilfe der add Methode können wir sehr einfach einen Datensatz an die Liste anhängen. Mittels removeLast geben wir die Daten des letzten Knotens aus und entfernen ihn aus der Liste.

Für die Realisierung der Peek-Operation verwenden wir die Methode getLast, die den Inhalt des letzten Knotens in der Liste zurück liefert ohne diesen zu löschen.

So wird aus einer verketteten Liste ein Stack

Okay, du fragst dich sicher: „Wie zum Geier können wir das Teil jetzt für unseren Stack verwenden?“

Ganz einfach! Was passiert, wenn wir den Stack umschmeißen?

Der umgestoßene Stapel erinnert doch nun wirklich sehr an eine verkettete Liste, bei der das oberste Element des Stack zum letzten Element der Liste geworden ist.

Wir können einen Stack also durch eine Liste abbilden indem wir einfach so tun als wäre das Listenende der Kopf unseres Stacks.

Hierbei müssen wir durch objektorientierte Datenkapselung dafür sorgen, dass wir nur die Daten am Ende der Liste modifizieren können.

Ein guter Startpunkt dies zu erreichen, ist sicher eine Klasse MeinStapelspeicher, die eine LinkedList als privates Attribut enthält.

public class MeinStapelspeicher {
   
 private LinkedList liste = new LinkedList();
		
}

Was brauchen wir noch?

Damit aus der Klasse MeinStapelspeicher ein echter Stack wird, müssen wir natürlich die Methoden push, pop und peek implementieren.

Denn diese drei Methoden entsprechen den Minimalanforderungen, die wir an einen Stack stellen.

Und das liefert uns eine Gelegenheit ein wichtiges Java Konzept einzuüben. Nämlich das Konzept der Java Interfaces.

Erinnerst du dich noch?

Mit Java Interfaces können wir dafür sorgen, dass eine Klasse gewissen Minimalanforderungen genügt.

Aber werden wir konkret! Unsere Klasse MeinStapelspeicher muss mindestens die Methoden push, pop und peek enthalten.

Definieren wir also ein Java Interface mit dem Namen Stapelspeicher, das die Methoden push, pop und peek enthält.

public interface Stapelspeicher{
	public String pop();
	public String peek();
	public void push(String data);
}

Innnerhalb von Java Interfaces können wir nur abstrakte Methoden, also Methoden ohne Rumpf definieren. Die Implementierung der Methoden muss in der Klasse, die das interface einbindet erfolgen.

Die beiden Methoden pop und peek sollen den Inhalt des obersten Stackelements zurückliefern und haben daher einen Rückgabewert vom Datentyp String.

Mit der push Methode legen wir einen Datensatz auf den Stack.
Die Methode hat keinen Rückgabewert, dafür aber einen String-Übergabeparameter, der die Daten, die auf den Stack gelegt werden sollen, enthält.

Um das Interface zu verwenden, müssen wir es über das Schlüsselwort implements in unsere MeinStapelspeicher Klasse einbinden.

class MeinStapelspeicher implements Stapelspeicher{

Was haben wir davon? Genau zwei Dinge!

Zum einen sollte deine Entwicklungsumgebung zumindest eine Warnung ausgeben, dass in der Klasse MeinStapelSpeicher die Methoden pop, peek und push fehlen.

In Eclipse sieht das ganze beispielsweise wie folgt aus:

Und zum anderen können wir Instanzen von MeinStapelspeicher, Variablen vom Typ Stapelspeicher zuweisen.

Stapelspeicher stapel = new MeinStapelspeicher();

Soweit so fein! Beginnen wir damit die Stackmethoden in der Klasse MeinStapelspeicher mit Leben zu füllen.

Wir beginnen mit der push Methode.

Hier haben wir lediglich den Übergabeparameter data ans Ende der verketteten Liste einzufügen. Das können wir sehr einfach mit Hilfe der LinkedList Methode add bewerkstelligen.

public void push(String data) {
	liste.add(data);
}

Nicht vielmehr muss bei der pop Methode getan werden.

Hier müssen wir den letzten Datensatz der Liste zurückliefern und anschließend entfernen. Hierfür stellt die LinkedList die Methode removeLast zur Verfügung.

public String pop() {
     return liste.removeLast();
}

Bei der peek Methode handelt es sich um eine abgeschwächte Pop-Operation, die den Inhalt des obersten Datensatzes des Stack ausgibt ohne diesen zu entfernen, wofür wir die LinkedList Methode getLast verwenden können.

public String peek() {
	return liste.getLast();
}

Im Grunde haben wir damit einen fertigen Stack gebaut. In der Praxis würde man den Fall, dass man einen pop auf einen leeren Stack macht noch mit einer Java Exception abfangen.

Um den Blick auf das Wesentliche nicht zu verlieren verzichten wir darauf!

Die Stunde der Wahrheit. Der Testlauf!

Jetzt wollen wir aber endlich wissen, ob es funktioniert. Schreiben wir also einen Testlauf in unserer main Methode, in der wir die Push-, Pop- und Peek-Operationen testen.

1: Stapelspeicher stapel = new MeinStapelspeicher();
		
2: stapel.push("Harry");
3: stapel.push("Fiona");
4: stapel.push("Laura");
		
5: System.out.println(stapel.peek());
6: System.out.println(stapel.pop());
7: System.out.println(stapel.pop());
8: System.out.println(stapel.pop());

In Zeile Eins legen wir zunächst eine Instanz unserer Klasse MeinStaplespeicher an.

Anschließend rufen wir in den Zeilen 2-4 drei Mal die Pushoperation auf und legen nacheinander die Strings Harry, Fiona und Laura auf den Stapel.

Danach sieht unser Stack folgendermaßen aus:

Als erstes haben wir Harry auf den Stack gelegt, weshalb er sich im Stapel ganz unten befindet. Danach kam Fiona und zuletzt Laura, die den Kopf des Stapels bildet.

In Zeile fünf testen wir die Peek-Operation und in den Zeilen sechs bis acht die Pop-Operation.

So wie unser Stapel aussieht, ist die Ausgabe, Laura, Laura, Fiona und Harry zu erwarten. Nach der letzten Pop-Operation in Zeile Acht ist unser  Stack leer.

Und in der Tat erhalten wir die erwartete Bildschirmausgabe:

Laura
Laura
Fiona
Harry

Herzlichen Glückwunsch wir haben erfolgreich einen Stapelspeicher programmiert.

Stack mit Array als Basisdatenstruktur

Bleibt als letztes noch zu klären warum wir kein Array als Basisdatenstruktur verwenden.

Hierfür sind zwei Gründe zu nennen:

1. Bei der verketteten Liste handelt es sich um eine dynamische Datenstruktur. Diese Eigenschaft „vererbt“ sich auf den Stack.
2. Bei einem Array müssen wir die Arrayposition, an welchem das oberste Element des Stack gespeichert ist in einem Klassenattribut manuell protokollieren.

Fazit: Die verkettete Liste eignet sich hervorragend als Basisdatenstruktur für einen Stack, da wir sehr einfach Daten an das Ende der verketteten Liste anfügen können. Wir verwenden den letzten Knoten der Liste als oberstes Element des Stack und sorgen bei der Implementierung dafür, dass dies das einzige Element der Liste ist, auf welches wir zugreifen können.

P.S. Natürlich hätten wir genauso gut auch das erste Element der verketteten Liste als oberstes Element des Stack verwenden können.

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

Hast auch du Fragen zum Thema programmieren lernen? Dann rein in die Kommentare damit!