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 List<string>();
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[0];
actions.RemoveAt(0);
Console.WriteLine("Rückgängig: " + undone);
Console.WriteLine("Übrig: " + string.Join(", ", actions));
Ausgabe
Rückgängig: Text getippt
Übrig: Titel fett gemacht, Foto eingefügt

Die Korrektur ist actions[^1] und actions.RemoveAt(actions.Count - 1): RemoveAt gibt das entfernte Element nicht zurück, darum liest du es vorher. 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:

Stack<string> history = new Stack<string>();
history.Push("Startseite");
history.Push("Laptops");
history.Push("Laptop 14 Zoll");
Console.WriteLine("Jetzt: " + history.Peek());


history.Pop();
Console.WriteLine("Zurück: " + history.Peek());
Console.WriteLine(string.Join(", ", 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.
  • Stack<T> liegt in System.Collections.Generic, wie List<T>.
  • string.Join geht den Stack von oben nach unten durch.
Genauer, für Neugierige
  • Pop und Peek auf einem leeren Stack brechen das Programm ab. TryPeek nicht: Es gibt false zurück, wenn der Stack leer ist, und gibt dir das oberste Element über out:
Stack<string> history = new Stack<string>();
if (history.TryPeek(out string page))
{
    Console.WriteLine("Jetzt: " + page);
}
else
{
    Console.WriteLine("Es gibt keine vorige Seite.");
}
history.Pop();
Fehler
Unhandled exception. System.InvalidOperationException: Stack empty.

Das Programm gibt zuerst „Es gibt keine vorige Seite.“ aus und bricht bei Pop ab. Für Pop gibt es auch TryPop.

  • C# hat auch eine ältere Klasse Stack ohne spitze Klammern, in System.Collections. Sie hält alles als object. Sie funktioniert, aber heute nimmst du Stack<T>:
Stack stack = new Stack();
stack.Push("Google");
stack.Push("Apple");
stack.Push("Microsoft");
Console.WriteLine("Oben: " + stack.Peek());
while (stack.Count > 0)
{
    Console.WriteLine("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?

Stack<string> undo = new Stack<string>();
undo.Push("Schriftart");
undo.Push("Farbe");
undo.Push("Größe");
undo.Pop();
undo.Push("Unterstreichung");
while (undo.Count > 0)
{
    Console.WriteLine(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 Queue<string>();
printer.Enqueue("rechnung.pdf");
printer.Enqueue("vertrag.docx");
printer.Enqueue("foto.jpg");
Console.WriteLine("Nächster: " + printer.Peek());


while (printer.Count > 0)
{
    Console.WriteLine("Drucke " + printer.Dequeue());
}
Console.WriteLine("Warteschlange: " + printer.Count);
Ausgabe
Nächster: rechnung.pdf
Drucke rechnung.pdf
Drucke vertrag.docx
Drucke foto.jpg
Warteschlange: 0
  • Enqueue stellt hinten an, Dequeue entfernt den ersten und gibt ihn zurück, und Peek schaut den ersten an.
  • Queue<T> liegt in System.Collections.Generic. Count sagt, wie viele warten, darum fragt die Schleife Count > 0.
  • Dequeue und Peek auf einer leeren Queue brechen das Programm ab. TryDequeue und TryPeek geben false zurück.
Genauer, für Neugierige
  • Die leere Queue:
Queue<string> clients = new Queue<string>();
clients.Enqueue("Kunde 1");
Console.WriteLine("Bedient: " + clients.Dequeue());
if (!clients.TryDequeue(out string next))
{
    Console.WriteLine("Niemand wartet.");
}
clients.Dequeue();
Fehler
Unhandled exception. System.InvalidOperationException: Queue empty.

TryDequeue sagt „Niemand wartet.“, und das letzte Dequeue bricht das Programm ab.

  • C# hat keine eigene Klasse für eine Queue mit zwei Enden. LinkedList<T> kann an beiden Enden hinzufügen und entfernen, darum nutzen ältere Beispiele sie als Queue:
LinkedList<string> clients = new LinkedList<string>();
clients.AddLast("Kunde 1");
clients.AddLast("Kunde 2");
clients.AddFirst("Kunde mit Termin");
Console.WriteLine("Bedient: " + clients.First.Value);
clients.RemoveFirst();
Console.WriteLine("Letzter: " + clients.Last.Value);
Console.WriteLine("Wartend: " + string.Join(", ", clients));
Ausgabe
Bedient: Kunde mit Termin
Letzter: Kunde 2
Wartend: Kunde 1, Kunde 2
  • Queue<string> nimmt auch null als Element an. Eine leere Queue erkennst du an Count oder an TryDequeue, nicht an null:
Queue<string> printer = new Queue<string>();
printer.Enqueue(null);
Console.WriteLine(printer.Count);
Ausgabe
1

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 Queue<string>();
checkout.Enqueue("Jonas");
checkout.Enqueue("Maria");
string next = checkout.();
Console.WriteLine("Du bist dran, " + next);

Sieh es dir an

Eine verkettete Liste von innen

List<T> 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
{
    public string Value;
    public Node Next;


    public Node(string value, Node next)
    {
        Value = value;
        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)
{
    Console.WriteLine(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<T>, und was wann

C# hat eine fertige verkettete Liste: LinkedList<T>. Sie fügt an beiden Enden mit AddFirst und AddLast hinzu, entfernt nach Wert mit Remove und gibt dir den ersten und den letzten Knoten über First und Last:

LinkedList<string> route = new LinkedList<string>();
route.AddLast("Nürnberg");
route.AddLast("Leipzig");
route.AddFirst("München");
route.AddLast("Berlin");
Console.WriteLine(string.Join(", ", route));


route.Remove("Leipzig");
Console.WriteLine("Nach der Änderung: " + string.Join(", ", route));
Console.WriteLine("Von " + route.First.Value + " nach " + route.Last.Value);
Ausgabe
München, Nürnberg, Leipzig, Berlin
Nach der Änderung: München, Nürnberg, Berlin
Von München nach Berlin

LinkedList<T> hat überhaupt keine Indizes. Zu einem Element nach Nummer kommst du nur über die Knoten, darum erlaubt der Compiler [ ] nicht:

Console.WriteLine(route[1]);
Kompilierfehler
error CS0021: Cannot apply indexing with [] to an expression of type 'LinkedList<string>'

Was wann:

  • Eine Liste nach Nummer: List<T>. Das ist die übliche Wahl.
  • Ein Stack: Stack<T>. Eine Queue: Queue<T>.
  • LinkedList<T>: selten. Wenn du beide Enden brauchst oder oft neben einem Knoten einfügst und entfernst, den du schon hast.
Genauer, für Neugierige
  • Warum ist LinkedList<T> meist langsamer, 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 List<T>, Stack<T> und Queue<T> ist genau das.
  • Die Knoten einer LinkedList<T> kannst du sehen: First ist ein LinkedListNode<string> mit Value, Next und Previous. Die Pfeile gehen in beide Richtungen, darum sind auch Last und RemoveLast schnell:
LinkedList<string> route = new LinkedList<string>();
route.AddLast("München");
route.AddLast("Nürnberg");
route.AddLast("Berlin");
LinkedListNode<string> second = route.First.Next;
Console.WriteLine(second.Value);
Console.WriteLine(second.Previous.Value + " <- " + second.Value + " -> " + second.Next.Value);
Console.WriteLine(route.Last.Next == null);
Ausgabe
Nürnberg
München <- Nürnberg -> Berlin
True
  • Der Knoten aus der vorigen 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 NullReferenceException 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 eine Eigenschaft 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: Eine Queue<T> sieht nur ihr erstes Element, also halte den letzten Preis in einem eigenen Feld. Gib die Preise mit F2 aus.

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(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), einer Eigenschaft Count 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 passiert bei Dequeue() auf einer leeren Queue<string>?
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 ·