Zum Inhalt
wannacode

Stack, Queue und verkettete Liste

Kurz gesagt: Ein Stack gibt das zuletzt hinzugefügte Element zuerst zurück (LIFO), eine Queue das zuerst hinzugefügte (FIFO), und eine verkettete Liste hält jedes Element in einem Knoten, der auf den nächsten zeigt.

Problem

„Rückgängig“ macht das Falsche rückgängig

Ein Texteditor hält die Aktionen in einer Liste. Strg+Z soll die letzte rückgängig machen, macht aber die erste rückgängig:

List<String> actions = new ArrayList<>();
actions.add("Text getippt");
actions.add("Titel fett gemacht");
actions.add("Foto eingefügt");


// Strg+Z: die letzte Aktion rückgängig machen.
String undone = actions.remove(0);
System.out.println("Rückgängig: " + undone);
System.out.println("Übrig: " + actions);
Ausgabe
Rückgängig: Text getippt
Übrig: [Titel fett gemacht, Foto eingefügt]

Die Korrektur ist actions.remove(actions.size() - 1). Aber jeder, der diesen Code anfasst, muss sich merken, an welchem Ende er entfernt. Und an der Kasse im Laden ist es umgekehrt: Wer zuerst kam, wird zuerst bedient. Gibt es eine Collection, die das Ende selbst kennt?

Die Idee

Stack: der Letzte liegt oben

Ein Stack ist wie ein Stapel Teller. Du legst oben drauf und nimmst von oben. Was zuletzt hineinkam, kommt zuerst heraus. Das heißt LIFO: last in, first out.

Der Button „Zurück“ im Browser ist ein Stack:

Deque<String> history = new ArrayDeque<>();
history.push("Startseite");
history.push("Laptops");
history.push("Laptop 14 Zoll");
System.out.println("Jetzt: " + history.peek());


history.pop();
System.out.println("Zurück: " + history.peek());
System.out.println(history);
Ausgabe
Jetzt: Laptop 14 Zoll
Zurück: Laptops
[Laptops, Startseite]
  • push legt oben drauf, pop entfernt das oberste und gibt es zurück, und peek schaut das oberste nur an.
  • Deque ist das Interface und ArrayDeque die Klasse. Beide liegen in java.util.
  • println gibt den Stack von oben nach unten aus.
Genauer, für Neugierige
  • pop auf einem leeren Stack bricht das Programm mit java.util.NoSuchElementException ab. peek auf einem leeren Stack gibt null zurück.
  • Java hat auch eine ältere Klasse Stack. Sie funktioniert, aber die Java-Dokumentation empfiehlt ArrayDeque:
Stack<String> stack = new Stack<>();
stack.push("Google");
stack.push("Apple");
stack.push("Microsoft");
System.out.println("Oben: " + stack.peek());
while (!stack.isEmpty()) {
    System.out.println("Entnommen: " + stack.pop());
}
Ausgabe
Oben: Microsoft
Entnommen: Microsoft
Entnommen: Apple
Entnommen: Google

Probier es aus

Was bleibt rückgängig zu machen?

Was gibt das Programm aus?

Deque<String> undo = new ArrayDeque<>();
undo.push("Schriftart");
undo.push("Farbe");
undo.push("Größe");
undo.pop();
undo.push("Unterstreichung");
while (!undo.isEmpty()) {
    System.out.println(undo.pop());
}
Antwort

Die Idee

Queue: Wer zuerst kommt, wird zuerst bedient

Eine Queue (Warteschlange) ist wie die Schlange an der Kasse. Du stellst dich hinten an, und der Erste wird bedient. Das heißt FIFO: first in, first out.

Druckaufträge warten in einer Queue:

Queue<String> printer = new ArrayDeque<>();
printer.offer("rechnung.pdf");
printer.offer("vertrag.docx");
printer.offer("foto.jpg");
System.out.println("Nächster: " + printer.peek());


while (!printer.isEmpty()) {
    System.out.println("Drucke " + printer.poll());
}
System.out.println("Warteschlange: " + printer);
Ausgabe
Nächster: rechnung.pdf
Drucke rechnung.pdf
Drucke vertrag.docx
Drucke foto.jpg
Warteschlange: []
  • offer stellt hinten an, poll entfernt den ersten und gibt ihn zurück, und peek schaut den ersten an.
  • Der Typ ist das Interface Queue, und die Klasse ist wieder ArrayDeque. Sie kann beides: Stack sein und Queue sein. Der Name kommt von double-ended queue, einer Queue mit zwei Enden.
  • poll und peek auf einer leeren Queue geben null zurück.
Genauer, für Neugierige
  • Es gibt auch add, remove() und element(). Sie tun dasselbe, werfen aber bei einer leeren Queue eine Exception, statt null zurückzugeben.
  • In älteren Beispielen ist die Queue eine LinkedList. Das geht auch, weil LinkedList ebenfalls Queue implementiert:
Queue<String> clients = new LinkedList<>();
clients.offer("Kunde 1");
clients.offer("Kunde 2");
System.out.println("Bedient: " + clients.poll());
System.out.println("Wartend: " + clients);
Ausgabe
Bedient: Kunde 1
Wartend: [Kunde 2]
  • ArrayDeque nimmt null nicht als Element an. Sonst hätte poll keine Möglichkeit zu sagen „sie ist leer“.

Probier es aus

Der Nächste an der Kasse

Die Kassiererin ruft den nächsten Kunden. Welche Methode nimmt ihn aus der Queue?

Queue<String> checkout = new ArrayDeque<>();
checkout.offer("Jonas");
checkout.offer("Maria");
String next = checkout.();
System.out.println("Du bist dran, " + next);

Sieh es dir an

Eine verkettete Liste von innen

ArrayList hält die Elemente nebeneinander in einem Array. Darum verschiebt das Einfügen vorne alle anderen. Es geht auch anders: Jedes Element steckt in einem eigenen Objekt, das den Wert und einen Pfeil zum nächsten hält. So ein Objekt heißt Knoten:

class Node {
    String value;
    Node next;


    Node(String value, Node next) {
        this.value = value;
        this.next = next;
    }
}

Eine Liste aus Knoten heißt verkettete Liste. Es reicht, den ersten Knoten zu halten, head. Jeden nächsten findest du, indem du dem Pfeil next folgst. Der letzte zeigt auf null.

Node head = null;
head = new Node("Kaffee", head);
head = new Node("Milch", head);
head = new Node("Brot", head);


for (Node n = head; n != null; n = n.next) {
    System.out.println(n.value);
}
Schritt für Schritt, in Worten
  1. Die Liste ist leer: head zeigt auf null.
  2. Ein neuer Knoten: next ist der alte head (null), und head rückt auf den Knoten.
  3. Der zweite Knoten zeigt auf den ersten. Im Speicher bewegt sich nichts: Nur die Pfeile ändern sich.
  4. Auch der dritte Knoten kommt nach vorne: Der zuletzt hinzugefügte ist der erste.
  5. n beginnt bei head und gibt jeden Knoten aus.
  6. n erreicht null: Die Schleife endet.
  • Einfügen vorne: ein neuer Knoten, dessen next auf den alten ersten zeigt, und head zeigt auf den neuen. Zwei Pfeile, und du verschiebst nichts.
  • Durchlaufen: Du beginnst bei head und folgst next, bis du bei null ankommst.
  • Der Preis: Knoten haben keine Indizes. Zum fünften Element kommst du, indem du durch die ersten vier gehst.

Die Idee

LinkedList, und was wann

Java hat eine fertige verkettete Liste: LinkedList. Sie implementiert sowohl List als auch Deque, hat also add, get und remove, aber auch addFirst, addLast und getFirst:

LinkedList<String> route = new LinkedList<>();
route.add("Nürnberg");
route.add("Leipzig");
route.addFirst("München");
route.addLast("Berlin");
System.out.println(route);


route.remove("Leipzig");
System.out.println("Nach der Änderung: " + route);
System.out.println("Von " + route.getFirst() + " nach " + route.getLast());
Ausgabe
[München, Nürnberg, Leipzig, Berlin]
Nach der Änderung: [München, Nürnberg, Berlin]
Von München nach Berlin

Was wann:

  • Eine Liste nach Nummer: ArrayList. Das ist die übliche Wahl.
  • Ein Stack oder eine Queue: ArrayDeque.
  • LinkedList: selten. Sie kann beides, ist aber meist langsamer als die beiden.
Genauer, für Neugierige
  • Warum verliert LinkedList, sogar beim Einfügen? Jeder Knoten ist ein eigenes Objekt irgendwo im Speicher, und der Prozessor liest Daten am schnellsten, wenn sie nebeneinander liegen. Das Array hinter ArrayList und ArrayDeque ist genau das. In der Praxis gewinnt LinkedList nur, wenn du oft in der Mitte einfügst oder entfernst, über einen Iterator, der schon dort ist.
  • LinkedList hält Pfeile in beide Richtungen, zum nächsten und zum vorigen. Darum sind auch getLast und removeLast schnell. Der Knoten aus dieser Karte hat nur next. So eine Liste heißt einfach verkettet.

Probier es aus

Finde den Fehler

Die Methode soll die Knoten zählen. Für die Liste Brot → Milch → Kaffee gibt sie 2 statt 3 zurück. Und bei einer leeren Liste bricht sie mit NullPointerException ab. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Übung

Stacks und Queues im Einsatz

Löse die Aufgaben in deinem Editor. Die Collection ist ein private-Feld der Klasse.

1. Ein Spielzeugzug. Eine Klasse Train mit den Methoden addWagon(String wagon) und removeWagon(). Der Zug ist ein Stack: Der zuletzt angekoppelte Wagen wird zuerst abgekoppelt. removeWagon() gibt den abgekoppelten Wagen zurück, oder null, wenn keiner da ist. Füge count() hinzu. Kopple drei Wagen an und zwei ab.

Ausgabe
Abgekoppelt: Wagen 3
Abgekoppelt: Wagen 2
Wagen: 1

2. Eine Buslinie. Eine Klasse BusRoute mit einer Queue von Haltestellen und den Methoden addStop(String stop) und getNextStop(), die die nächste Haltestelle zurückgibt, oder null, wenn die Strecke zu Ende ist. Füge „Hauptbahnhof“, „Rathaus“ und „Universität“ hinzu und fahr die Strecke ab.

Ausgabe
Nächster Halt: Hauptbahnhof
Nächster Halt: Rathaus
Nächster Halt: Universität
Ende der Strecke.

3. Ein Börsenticker. Eine Klasse StockTicker hält die letzten N Preise einer Aktie. Der Konstruktor bekommt das Symbol und N. updatePrice(double price) fügt einen Preis hinzu, und wenn es mehr als N Preise sind, entfernt es den ältesten. Füge getLastPrice() und average() für die gespeicherten Preise hinzu. Für SAP mit N = 3 übergib die Preise 150, 152, 149 und 155. Tipp: Deque hat peekLast().

Ausgabe
SAP: letzter Preis 155.0 €
Durchschnitt der letzten 3: 152.0 €

4. Ausgeglichene Klammern. Ein Code-Editor prüft, ob die Klammern (), [] und {} in der richtigen Reihenfolge geschlossen sind. Schreib isBalanced(String text) mit einem Stack: Eine öffnende Klammer legst du auf den Stack, bei einer schließenden nimmst du die oberste herunter und prüfst, dass sie von derselben Art ist. Am Ende muss der Stack leer sein. Lies drei Zeilen ein.

Eingabe
(1 + [2 * 3])
(1 + 2]
((5)
Ausgabe
(1 + [2 * 3]) -> ja
(1 + 2] -> nein
((5) -> nein

5. Deine eigene verkettete Liste. Eine Klasse MyLinkedList mit den Knoten aus der Lektion und den Methoden add(String value) (am Ende), remove(String value), contains(String value), size() und toString(). In remove findest du den Knoten vor dem gesuchten und lenkst sein next um. Prüf den Fall, dass der erste entfernt wird, gesondert.

Ausgabe
[Rechnung, Bericht, Besprechung]
Enthält Bericht: true
Nach dem Entfernen: [Rechnung, Besprechung]
Größe: 2

Weitere Aufgaben

  • Rückgängig und Wiederholen. Halte zwei Stacks: undo und redo. Eine neue Aktion kommt in undo und leert redo. „Rückgängig“ verschiebt die oberste von undo nach redo, und „Wiederholen“ verschiebt sie zurück.
  • Wörter rückwärts. Lies einen Satz ein und gib ihn mit den Wörtern in umgekehrter Reihenfolge aus, über einen Stack: „Heute ist Freitag“ wird zu „Freitag ist Heute“.
  • Zwei Kassen. Kunden kommen nacheinander und gehen zu der Kasse mit der kürzeren Schlange. Gib aus, wer an welcher Kasse bedient wurde.
  • Die verkettete Liste umdrehen. Füge MyLinkedList eine Methode reverse() hinzu, die die Pfeile umdreht, ohne neue Knoten anzulegen.

Test

Teste dich

1. Du legst A auf einen Stack, dann B, dann C. Was kommt bei pop zuerst heraus?
2. Welche Aufgabe passt zu einer Queue?
3. Was gibt poll() bei einer leeren ArrayDeque zurück?
4. Warum ist das Einfügen am Anfang einer verketteten Liste schnell?
5. Was ist in einer verketteten Liste langsam?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·