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 Array. Strg+Z soll die letzte rückgängig machen, macht aber die erste rückgängig:

const actions = [];
actions.push("Text getippt");
actions.push("Titel fett gemacht");
actions.push("Foto eingefügt");

// Strg+Z: die letzte Aktion rückgängig machen.
const undone = actions.shift();
console.log(`Rückgängig: ${undone}`);
console.log("Übrig:", actions);

Ausgabe

Rückgängig: Text getippt
Übrig: [ 'Titel fett gemacht', 'Foto eingefügt' ]

Die Korrektur ist actions.pop(). 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:

const history = [];
history.push("Startseite");
history.push("Laptops");
history.push("Laptop 14 Zoll");
console.log(`Jetzt: ${history.at(-1)}`);

history.pop();
console.log(`Zurück: ${history.at(-1)}`);
console.log(history);

Ausgabe

Jetzt: Laptop 14 Zoll
Zurück: Laptops
[ 'Startseite', 'Laptops' ]

JavaScript hat keine eigene Klasse für einen Stack: Ein Array ist ein Stack, wenn du nur am Ende hineinlegst und herausnimmst.

• push legt oben drauf, pop() entfernt das oberste und gibt es zurück, und at(-1) schaut das oberste nur an.
• Oben ist das Ende des Arrays. Beide Operationen sind schnell, weil sich am Ende nichts verschiebt.
• console.log gibt den Stack von unten nach oben aus: Das oberste steht zuletzt.

Genauer, für Neugierige

• pop() und at(-1) auf einem leeren Array brechen das Programm nicht ab. Sie geben undefined:

const history = [];
console.log(history.pop());
console.log(history.at(-1));

Ausgabe

undefined
undefined

Prüf also history.length, bevor du etwas nimmst.

Probier es aus

Was bleibt rückgängig zu machen?

Was gibt das Programm aus?

const undo = [];
undo.push("Schriftart");
undo.push("Farbe");
undo.push("Größe");
undo.pop();
undo.push("Unterstreichung");
while (undo.length > 0) {
  console.log(undo.pop());
}

Antwort

Unterstreichung
Größe
Farbe
Schriftart

Schriftart
Farbe
Größe

Schriftart
Farbe
Unterstreichung

Unterstreichung
Farbe
Schriftart

Prüfen

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:

const printer = [];
printer.push("rechnung.pdf");
printer.push("vertrag.docx");
printer.push("foto.jpg");
console.log(`Nächster: ${printer[0]}`);

while (printer.length > 0) {
  console.log(`Drucke ${printer.shift()}`);
}
console.log("Warteschlange:", printer);

Ausgabe

Nächster: rechnung.pdf
Drucke rechnung.pdf
Drucke vertrag.docx
Drucke foto.jpg
Warteschlange: []

JavaScript hat keine eigene Klasse für eine Queue. Ein Array wird zur Queue, wenn du hinten anstellst und vorne herausnimmst:

• push stellt hinten an, shift entfernt den ersten und gibt ihn zurück, und printer[0] schaut den ersten an.
• shift auf einem leeren Array gibt undefined. Es bricht das Programm nicht ab.

Aber shift hat seinen Preis. Es rückt alle anderen einen Platz nach vorne, wie das Einfügen vorne in der Lektion über Arrays. Bei ein paar Druckaufträgen merkst du das nicht. Bei einer Queue mit Zehntausenden Elementen ist es um ein Vielfaches langsamer als einfaches Lesen der Reihe nach. Dann nimmst du die verkettete Liste aus der nächsten Karte, die sowohl den ersten als auch den letzten Knoten hält.

Genauer, für Neugierige

• shift auf einer leeren Queue:

const clients = ["Kunde 1"];
console.log(`Bedient: ${clients.shift()}`);
console.log(clients.shift());

Ausgabe

Bedient: Kunde 1
undefined

• Die Engine V8 macht shift manchmal schnell, indem sie den Anfang des Arrays verschiebt statt der Elemente. Bei großen Arrays passiert das nicht. Verlass dich nicht darauf.

Probier es aus

Der Nächste an der Kasse

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

const checkout = [];
checkout.push("Jonas");
checkout.push("Maria");
const client = checkout.();
console.log(`Du bist dran, ${client}`);

Prüfen

Sieh es dir an

Eine verkettete Liste von innen

Ein Array 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 {
  constructor(value, 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.

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

for (let n = head; n !== null; n = n.next) {
  console.log(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

Das Array, und was wann

JavaScript hat keine fertige verkettete Liste. Ein Array kann an beiden Enden hinzufügen und entfernen: push und pop hinten, unshift und shift vorne:

const route = [];
route.push("Nürnberg");
route.push("Leipzig");
route.unshift("München");
route.push("Berlin");
console.log(route);

route.splice(route.indexOf("Leipzig"), 1);
console.log("Nach der Änderung:", route);
console.log(`Von ${route[0]} nach ${route.at(-1)}`);

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: ein Array. Das ist die übliche Wahl.
• Ein Stack: ein Array mit push und pop.
• Eine Queue: ein Array mit push und shift, solange sie klein ist. Eine große Queue mit Tausenden Elementen: eine verkettete Liste wie die aus der vorigen Karte, die auch den letzten Knoten hält.

Genauer, für Neugierige

• unshift ist wie shift: Es verschiebt alle Elemente um einen Platz, ist also vorne an einem großen Array langsam.
• Warum ist ein Array meist schneller als eine verkettete Liste, sogar beim Einfügen? Jeder Knoten ist ein eigenes Objekt irgendwo im Speicher, und der Prozessor liest Daten am schnellsten, wenn sie nebeneinander liegen. Ein Array ist genau das.
• Der Knoten aus dieser Karte hat nur next. So eine Liste heißt einfach verkettet.

Probier es aus

Finde den Fehler

Die Funktion 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 TypeError ab. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1function count(head) {2 let count = 0;3 let n = head;4 while (n.next !== null) {5 count++;6 n = n.next;7 }8 return count;9}

Prüfen

Übung

Stacks und Queues im Einsatz

Löse die Aufgaben in deinem Editor. Die Collection ist ein privates Feld der Klasse, mit einem # vorne.

1. Ein Spielzeugzug. Eine Klasse Train mit den Methoden addWagon(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(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(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: at(-1) ist der letzte Preis. Gib die Preise mit zwei Nachkommastellen aus, mit toFixed(2).

Ausgabe

SAP: letzter Preis 155.00 €
Durchschnitt der letzten 3: 152.00 €

4. Ausgeglichene Klammern. Ein Code-Editor prüft, ob die Klammern (), [] und {} in der richtigen Reihenfolge geschlossen sind. Schreib isBalanced(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(value) (am Ende), remove(value), contains(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.

• Eine schnelle Queue. Füge MyLinkedList ein Feld für den letzten Knoten hinzu, damit auch add am Ende schnell ist. Jetzt ist sie eine Queue ohne shift: add hinten, den ersten vorne entfernen.

Test

Teste dich

1. Du legst A auf einen Stack, dann B, dann C. Was kommt bei pop zuerst heraus?

ACB

2. Welche Aufgabe passt zu einer Queue?

Die letzte Aktion rückgängig machenDruckaufträge, die in der Reihenfolge ihres Eingangs gedruckt werdenDer Button „Zurück“ im Browser

3. Was gibt shift() bei einem leeren Array zurück?

0undefinedDas Programm bricht mit einem Fehler ab

4. Warum ist das Einfügen am Anfang einer verketteten Liste schnell?

Weil die Liste sich selbst sortiertWeil du einen neuen Knoten anlegst und zwei Pfeile umsetzt, ohne die anderen Elemente anzufassenWeil die Elemente im Speicher nebeneinander liegen

5. Was ist in einer verketteten Liste langsam?

Ein Element über seine Nummer holen, zum Beispiel das fünfhundertsteDas erste Element entfernenAm Anfang hinzufügen

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Polymorphie · Interfaces ohne interface · Exceptions · Arrays: push, splice und sort
• Geht weiter in: Hashcodes und Hashfunktionen · Klassen und Daten in Klassen · Command · Speicherkomplexität
• Aufgaben zum Thema: Collections