Vorlesung Informatik 2 - Teil B: Theorie
3.1 Stack
Die einfachste Datenstruktur ist der Stack oder Stapel.
Ein Stapel von Containern im Hafen verdeutlicht gut, was ein Stack ist. Der Kran kann immer nur auf den obersten Container zugreifen oder einen Container vom Stapel abheben. Genau dass sind die beiden Algorithmen auf einem Stack:
- push: legt ein weiteres Objekt oben auf den Stapel
- pop: holt das oberste Objekt vom Stapel.
Wird auch als LIFO bezeichnet: Last In First Out.
In der reinen Lehre hat ein Stack genau diese Methoden.
In der Praxis kommen meist noch einige dazu, z.B. könnte eine Stack-Klasse so aussehen:
class Stack<T>:
- push( x: T): void - legt x auf den Stapel
- pop( ): T
- entfernt
das oberste Objekt vom Stapel und gibt
es zurück
- peek(): T - gibt das oberste Objekt des Stapels zurück ohne es vom Stapel zu entfernen,
- size(): int - liefert die Anzahl Objekte iom Stapel,
- isEmpty(): boolean - liefert true, wenn der Stapel leer ist,
- clear(): void - leert den Stack
Anwendungsbeispiele:
- Der System-Stack enthält lokalen Variablen der gerade aktiven Methoden.
- Kartenstapel in einem Kartenspiel.
- Breadcrumb-Navigation im Browser
- Zeilen-Editor mit zwei Stacks (Zeichen links/rechts vom Cursor)
Implmentierungen:
1. Mit einem Array
Wir halten die Elements in einem Array und merken uns die Länge des Stack in einer weiteren Variable:
class MeinArrayStack<T>{
private T[] array = (T[])new Object[100]; // Der generische Typ T lässt sich nicht instanziieren
private int laenge=0;
public void push(T x){
if(laenge>=array.length) // hier müssen wir reagieren, z.B. den Array verdoppeln?
array[laenge++] = x;
}
Die komplette Implementierung ist eine der Übungsaufgaben.
Eine andere Implementierung arbeitet mit einer einfach verketteten Liste:
class MeinListenStack<T>{
private class Eintrag<T>{ // innere Klasse-------------------
T inhalt;
Eintrag next; // Zeiger auf den nächsten Eintrag der verketten Liste
}// Ende der inneren Klasse Eintrag ---------------------------
private Eintrag oben;
public push(T x){
oben=new Eintrag(x,oben);
}
Die Stack-Methoden haben die Komplexität O(1).
Auch diesen Stack implementieren wir als Aufgabe in den Übungen.
Vorteil: die Liste wächst dynamisch solange noch Hauptspeicher frei ist.
Die toString-Methode für diese Implementierung sieht z.B. so aus:
public String toString(){
String s = "Stack:";
Eintrag nadel = oben; // lokale Hilfsvariable
while(nadel!=null){
s+="\n"+nadel.inhalt;
nadel = nadel+next;
}
}