Lektion 2.2

Stapel und Warteschlangen

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • Stapel und Warteschlange als abstrakte Datentypen beschreiben und auseinanderhalten,

  • beide mit einem Array und mit einer Liste so umsetzen, dass jede Operation O(1)O(1) kostet,

  • einen Ringpuffer mit Indexrechnung modulo NN verwalten,

  • mit einem Stapel Klammern prüfen und Postfix-Ausdrücke auswerten,

  • den Aufrufstapel einer Rekursion und die Warteschlange der Breitensuche erklären.

Vorausgesetzt: Arrays und verkettete Listen, Amortisierte Analyse, Rekursion und Rekurrenzgleichungen

Ein Texteditor merkt sich deine Änderungen. Drückst du „Rückgängig“, verschwindet die letzte Änderung zuerst, dann die vorletzte. Ein Drucker im Büro macht es umgekehrt: Der Auftrag, der zuerst kam, wird zuerst gedruckt.

Beide brauchen nur zwei Operationen: etwas hineinlegen und das nächste herausholen. Der Unterschied liegt allein darin, welches das nächste ist.

Eine dritte Frage: Ist ( [ ) ]\texttt{( [ ) ]} korrekt geklammert? Jede Klammer hat ein Gegenstück, trotzdem stimmt etwas nicht. Wie prüft ein Programm das in einem einzigen Durchlauf? Die Antwort ist die erste Struktur dieser Lektion.

Vermute zuerst

Auf einen leeren Stapel werden 11, 22, 33 gelegt. Dann wird einmal das oberste Element genommen, 44 wird gelegt, und danach wird dreimal das oberste genommen. In welcher Reihenfolge kommen die Zahlen heraus?

Definition

Stapel (Stack)

Ein Stapel (englisch stack, auch Keller) ist ein abstrakter Datentyp für eine Sammlung von Elementen mit vier Operationen:

  • push(S, x)\texttt{push(S, x)} legt xx oben auf den Stapel.
  • pop(S)\texttt{pop(S)} entfernt das oberste Element und gibt es zurück.
  • top(S)\texttt{top(S)} gibt das oberste Element zurück, ohne es zu entfernen.
  • isEmpty(S)\texttt{isEmpty(S)} sagt, ob der Stapel leer ist.

„Oben“ ist das Element, das als letztes hineingelegt wurde und noch drin ist. Man nennt das LIFO (last in, first out). Genauer: Nach push(S, x)\texttt{push(S, x)} liefert top(S)\texttt{top(S)} den Wert xx, und ein anschließendes pop(S)\texttt{pop(S)} liefert xx und lässt den Stapel so zurück, wie er vor dem push\texttt{push} war. pop\texttt{pop} und top\texttt{top} auf einem leeren Stapel sind Fehler.

Gegenbeispiel. Eine Sammlung, bei der pop\texttt{pop} stets das kleinste Element liefert, ist kein Stapel, auch mit denselben Operationsnamen: Das Verhalten hängt von den Werten ab, nicht von der Reihenfolge des Hineinlegens. Das ist eine Prioritätswarteschlange (eigene Lektion).

Beispiel

Stapel mit Array und mit Liste

Im Array S.A\texttt{S.A} zählt S.t\texttt{S.t} die Elemente. Sie liegen in S.A[0]\texttt{S.A[0]} bis S.A[t-1]\texttt{S.A[t-1]}, oben ist S.A[t-1]\texttt{S.A[t-1]}.

ZeileEinrückungAnweisung
10function push(S, x)\texttt{function push(S, x)}
21if S.t == S.cap\texttt{if S.t == S.cap}
32verdopple S.A\texttt{verdopple S.A}
41S.A[S.t] = x\texttt{S.A[S.t] = x}
51S.t = S.t + 1\texttt{S.t = S.t + 1}
60function pop(S)\texttt{function pop(S)}
71if S.t == 0\texttt{if S.t == 0}
82error "Stapel leer"\texttt{error "Stapel leer"}
91S.t = S.t - 1\texttt{S.t = S.t - 1}
101return S.A[S.t]\texttt{return S.A[S.t]}

S.cap\texttt{S.cap} ist die Kapazität. top\texttt{top} liefert S.A[S.t-1]\texttt{S.A[S.t-1]}, isEmpty\texttt{isEmpty} prüft S.t == 0\texttt{S.t == 0}.

Ohne Zeile 2 und 3 kostet jede Operation O(1)O(1), solange Platz ist. Mit Verdopplung kostet ein einzelnes push\texttt{push} manchmal Θ(n)\Theta(n), aber wie beim dynamischen Array kosten mm Operationen zusammen O(m)O(m), amortisiert O(1)O(1) je Operation.

Mit einer einfach verketteten Liste ist push\texttt{push} das Einfügen vorn und pop\texttt{pop} das Entfernen des ersten Knotens. Beides kostet O(1)O(1) im schlechtesten Fall, dafür braucht jedes Element einen Zeiger.

Definition

Warteschlange (Queue)

Eine Warteschlange (englisch queue) ist ein abstrakter Datentyp mit den Operationen enqueue(Q, x)\texttt{enqueue(Q, x)} (hinten anstellen), dequeue(Q)\texttt{dequeue(Q)} (das vorderste Element entfernen und zurückgeben), front(Q)\texttt{front(Q)} (das vorderste ansehen) und isEmpty(Q)\texttt{isEmpty(Q)}. Vorne steht das Element, das am längsten drin ist: FIFO (first in, first out).

Mit einem Array liegt es nahe, das vorderste Element in A[0]\texttt{A[0]} zu halten. Dann muss dequeue\texttt{dequeue} alle übrigen Elemente einen Platz nach vorn schieben und kostet Θ(n)\Theta(n). Das vermeidet der Ringpuffer.

Definition

Ringpuffer

Ein Ringpuffer speichert die Warteschlange in einem Array Q.A\texttt{Q.A} mit NN Plätzen, Q.A[0]\texttt{Q.A[0]} bis Q.A[N-1]\texttt{Q.A[N-1]}, und denkt sich das Array zu einem Kreis geschlossen: Hinter Platz N−1N-1 kommt Platz 00. Er merkt sich zwei Zahlen: Q.head\texttt{Q.head}, den Platz des vordersten Elements, und Q.count\texttt{Q.count}, die Anzahl der Elemente.

Für ganze Zahlen a≥0a \ge 0 und N≥1N \ge 1 ist a mod Na \bmod N der Rest bei der Division von aa durch NN, eine Zahl von 00 bis N−1N-1. Damit ist der erste freie Platz hinter der Schlange (head+count) mod N(\texttt{head} + \texttt{count}) \bmod N.

ZeileEinrückungAnweisung
10function enqueue(Q, x)\texttt{function enqueue(Q, x)}
21if Q.count == N\texttt{if Q.count == N}
32error "Puffer voll"\texttt{error "Puffer voll"}
41Q.A[(Q.head + Q.count) mod N] = x\texttt{Q.A[(Q.head + Q.count) mod N] = x}
51Q.count = Q.count + 1\texttt{Q.count = Q.count + 1}
60function dequeue(Q)\texttt{function dequeue(Q)}
71if Q.count == 0\texttt{if Q.count == 0}
82error "Schlange leer"\texttt{error "Schlange leer"}
91x = Q.A[Q.head]\texttt{x = Q.A[Q.head]}
101Q.head = (Q.head + 1) mod N\texttt{Q.head = (Q.head + 1) mod N}
111Q.count = Q.count - 1\texttt{Q.count = Q.count - 1}
121return x\texttt{return x}
Beispiel

Ein Ringpuffer mit vier Plätzen

N=4N = 4, zu Beginn head=0\texttt{head} = 0 und count=0\texttt{count} = 0. Ein Strich bedeutet einen freien Platz.

SchrittOperationPlatz 0Platz 1Platz 2Platz 3headcountSchlange von vorn
0Start––––00leer
1enqueue\texttt{enqueue} aa–––01a
2enqueue\texttt{enqueue} bab––02a, b
3enqueue\texttt{enqueue} cabc–03a, b, c
4dequeue\texttt{dequeue}, liefert a–bc–12b, c
5dequeue\texttt{dequeue}, liefert b––c–21c
6enqueue\texttt{enqueue} d––cd22c, d
7enqueue\texttt{enqueue} ee–cd23c, d, e
8enqueue\texttt{enqueue} fefcd24c, d, e, f
9dequeue\texttt{dequeue}, liefert cef–d33d, e, f

In Schritt 7 ist der Platz (2+2) mod 4=0(2 + 2) \bmod 4 = 0: Die Schlange läuft über das Ende des Arrays hinaus und setzt vorn fort. In Schritt 8 ist (2+3) mod 4=1(2 + 3) \bmod 4 = 1, der Puffer ist voll. Ein weiteres enqueue\texttt{enqueue} bricht in Zeile 3 ab; ein dynamischer Ringpuffer legt stattdessen ein doppelt so großes Array an und kopiert die Elemente ab head\texttt{head} der Reihe nach hinein.

Kurz geprüft

Ein Ringpuffer hat N=8N = 8 Plätze, head=6\texttt{head} = 6 und count=5\texttt{count} = 5. Auf welchen Platz schreibt das nächste enqueue\texttt{enqueue}?

Satz

Der Ringpuffer ist eine Warteschlange

Nach jeder Folge von enqueue\texttt{enqueue}- und dequeue\texttt{dequeue}-Aufrufen, von denen keiner einen Fehler meldet, gilt mit h=headh = \texttt{head} und c=countc = \texttt{count}: Die Warteschlange enthält cc Elemente, und von vorn nach hinten stehen sie auf den Plätzen
h mod N, (h+1) mod N, …, (h+c−1) mod Nh \bmod N, \ (h+1) \bmod N, \ \dots, \ (h+c-1) \bmod N.
Jede Operation kostet im schlechtesten Fall O(1)O(1).

Häufige Fehler

Voll und leer sehen gleich aus

Viele Umsetzungen speichern statt count\texttt{count} einen zweiten Index tail\texttt{tail} für den ersten freien Platz und prüfen „leer“ mit head == tail\texttt{head == tail}. Im Beispiel oben wäre nach Schritt 8 aber tail=(2+4) mod 4=2=head\texttt{tail} = (2+4) \bmod 4 = 2 = \texttt{head}, obwohl der Puffer voll ist. Der Code hält den vollen Puffer für leer, und dequeue\texttt{dequeue} meldet fälschlich eine leere Schlange.

Richtig ist

Mit head\texttt{head} und tail\texttt{tail} allein lassen sich die N+1N+1 möglichen Füllstände 0,1,…,N0, 1, \dots, N nicht unterscheiden, denn tail−head\texttt{tail} - \texttt{head} modulo NN hat nur NN Werte. Entweder man speichert count\texttt{count} wie hier, oder man lässt immer einen Platz frei und nennt den Puffer schon bei N−1N-1 Elementen voll.

Beispiel

Anwendung: Klammern prüfen

Eine Zeichenkette aus den Klammern ( ) [ ] { }\texttt{( ) [ ] \{ \}} heißt korrekt geklammert, wenn sie nach diesen Regeln entsteht: Die leere Kette ist korrekt geklammert. Sind uu und vv korrekt geklammert, dann auch (u)\texttt{(}u\texttt{)}, [u]\texttt{[}u\texttt{]}, {u}\texttt{\{}u\texttt{\}} und uvuv (die beiden hintereinander).

Der Algorithmus legt jede öffnende Klammer auf einen Stapel. Eine schließende Klammer muss zur zuletzt geöffneten, noch offenen passen, und genau die liegt oben. match(a, c)\texttt{match(a, c)} ist wahr, wenn aa die öffnende Klammer zu cc ist.

ZeileEinrückungAnweisung
10function balanced(w)\texttt{function balanced(w)}
21S = leerer Stapel\texttt{S = leerer Stapel}
31for each c in w\texttt{for each c in w}
42if c is opening\texttt{if c is opening}
53push(S, c)\texttt{push(S, c)}
62else if isEmpty(S) or not match(pop(S), c)\texttt{else if isEmpty(S) or not match(pop(S), c)}
73return false\texttt{return false}
81return isEmpty(S)\texttt{return isEmpty(S)}

Für ( [ ) ]\texttt{( [ ) ]}: (\texttt{(} und [\texttt{[} kommen auf den Stapel. Bei )\texttt{)} liefert pop\texttt{pop} die [\texttt{[}, die nicht passt, also false\texttt{false}. Das ist genau der Fehler: Die runde Klammer wird geschlossen, während die eckige noch offen ist.

Der Stapel enthält stets die noch offenen Klammern, die zuletzt geöffnete oben. Am Ende muss er leer sein, sonst bleibt etwas offen, wie bei ( (\texttt{( (}. Jedes Zeichen kostet O(1)O(1), die Prüfung also O(n)O(n) für nn Zeichen. Dass der Algorithmus genau die korrekt geklammerten Ketten annimmt, beweist du in einer Übung.

Beispiel

Anwendung: Postfix-Ausdrücke auswerten

In Postfix-Schreibweise steht ein Operator hinter seinen beiden Operanden: 3+43 + 4 wird 3 4 +\texttt{3 4 +}, und 5+(1+2)⋅4−35 + (1 + 2) \cdot 4 - 3 wird 5 1 2 + 4 * + 3 -\texttt{5 1 2 + 4 * + 3 -}. Klammern und Vorrangregeln braucht man nicht mehr. Die Auswertung liest von links: Eine Zahl kommt auf den Stapel. Ein Operator nimmt zuerst b=popb = \texttt{pop}, dann a=popa = \texttt{pop} und legt a∘ba \circ b zurück, wobei ∘\circ der Operator ist. Am Ende liegt genau eine Zahl auf dem Stapel, das Ergebnis.

SchrittZeichenAktionStapel danach (unten links)
155push\texttt{push}55
211push\texttt{push}5,15, 1
322push\texttt{push}5,1,25, 1, 2
4++b=2b = 2, a=1a = 1, lege 1+21 + 25,35, 3
544push\texttt{push}5,3,45, 3, 4
6⋅\cdotb=4b = 4, a=3a = 3, lege 3⋅43 \cdot 45,125, 12
7++b=12b = 12, a=5a = 5, lege 5+125 + 121717
833push\texttt{push}17,317, 3
9−-b=3b = 3, a=17a = 17, lege 17−317 - 31414

Das Ergebnis ist 1414, und tatsächlich ist 5+3⋅4−3=145 + 3 \cdot 4 - 3 = 14. Bei −- und :: kommt es auf die Reihenfolge an: Das zuerst entnommene Element ist der rechte Operand. Manche Taschenrechner und viele Interpreter für Programmiersprachen arbeiten genau so.

Kurz geprüft

Welchen Wert hat der Postfix-Ausdruck 4 2 3 * - 5 +\texttt{4 2 3 * - 5 +}?

Beispiel

Der Aufrufstapel einer Rekursion

Auch der Rechner selbst benutzt einen Stapel. Jeder Funktionsaufruf legt einen Rahmen auf den Aufrufstapel: die Parameter, die lokalen Variablen und die Stelle, an der es nach dem Aufruf weitergeht. Endet die Funktion, wird ihr Rahmen entfernt, und der Aufrufer macht weiter. Für fak(n)\texttt{fak(n)}, das bei n=0n = 0 den Wert 11 und sonst n⋅fak(n-1)n \cdot \texttt{fak(n-1)} liefert:

Die rechte Spalte nennt für jeden Rahmen den Wert von nn.

ZeitpunktRahmen auf dem Stapel (unten links)
fak(3)\texttt{fak(3)} beginnt33
ruft fak(2)\texttt{fak(2)}3,23, 2
ruft fak(1)\texttt{fak(1)}3,2,13, 2, 1
ruft fak(0)\texttt{fak(0)}3,2,1,03, 2, 1, 0
fak(0)\texttt{fak(0)} liefert 113,2,13, 2, 1
fak(1)\texttt{fak(1)} liefert 1⋅1=11 \cdot 1 = 13,23, 2
fak(2)\texttt{fak(2)} liefert 2⋅1=22 \cdot 1 = 233
fak(3)\texttt{fak(3)} liefert 3⋅2=63 \cdot 2 = 6leer

Der zuletzt begonnene Aufruf endet zuerst: LIFO. Die größte Höhe des Stapels ist die Rekursionstiefe, hier n+1n + 1 Rahmen. Eine Rekursion braucht daher Speicher proportional zu ihrer Tiefe, auch ohne eigene Datenstrukturen. Ist der Aufrufstapel voll, bricht das Programm mit einem Stapelüberlauf (stack overflow) ab.

Ausblick: Breitensuche mit einer Warteschlange

Breitensuche · Stadtplan

Acht Kreuzungen, die Gewichte sind Fahrzeiten in Minuten. Der schnellste Weg von A nach H ist nicht der, der auf der Karte am geradesten aussieht.

Ungerichteter Graph · 8 Knoten · 12 Kanten

Ad = 0StartBCDEFGHZiel
Abgeschlossen
0
Kanten geprüft
0
Entdeckt
1
  • in der Warteschlange
  • in Arbeit
  • fertig
  • Kante, über die entdeckt wurde
  • Weg zum Ziel
Schritt 1 von 42
Tempo
← → Schritt, Leertaste Abspielen
Start

Start bei A

Die Breitensuche erkundet den Graphen in Wellen: erst alle Nachbarn von A, dann deren Nachbarn und so weiter. d[v] zählt, wie viele Kanten ein Knoten v vom Start entfernt ist, vor[v] merkt sich den Knoten, von dem aus v entdeckt wurde. Zu Beginn kennt die Suche nur A mit d[A] = 0, und A steht allein in der Warteschlange. Die Nachbarn eines Knotens kommen in alphabetischer Reihenfolge an die Reihe.

Warteschlange Q

Vorne wird entnommen, hinten angefügt.

Werte der Knoten

KnotenZustanddvor
Awartet0–
Bunbekannt∞–
Cunbekannt∞–
Dunbekannt∞–
Eunbekannt∞–
Funbekannt∞–
Gunbekannt∞–
Hunbekannt∞–

d: Abstand in Kanten · vor: Vorgänger

Pseudocoden = 8, m = 12
  1. d[v] ← ∞, vor[v] ← – für alle v; d[s] ← 0; Q ← [s]
  2. solange Q nicht leer ist:
  3. u ← vorderster Knoten aus Q (entfernen)
  4. für jeden Nachbarn v von u:
  5. wenn d[v] = ∞ (v noch unentdeckt):
  6. d[v] ← d[u] + 1, vor[v] ← u, v hinten an Q
  7. u ist abgeschlossen

Ein Graph besteht aus Knoten (hier Kreuzungen A bis H) und Kanten (Straßen zwischen ihnen). Die Breitensuche besucht die Knoten nach ihrem Abstand vom Start A, gezählt in Kanten, und hält entdeckte, noch nicht bearbeitete Knoten in der Warteschlange Q. Graphen haben ein eigenes Kapitel.

Probier es aus

Definition

Deque

Eine Deque (double-ended queue, gesprochen wie „Deck“) erlaubt Einfügen und Entfernen an beiden Enden: pushFront\texttt{pushFront}, pushBack\texttt{pushBack}, popFront\texttt{popFront}, popBack\texttt{popBack}. Benutzt man nur pushBack\texttt{pushBack} und popBack\texttt{popBack}, verhält sie sich wie ein Stapel; mit pushBack\texttt{pushBack} und popFront\texttt{popFront} wie eine Warteschlange.

Im Ringpuffer kosten alle vier Operationen O(1)O(1). pushFront\texttt{pushFront} setzt head = (head - 1 + N) mod N\texttt{head = (head - 1 + N) mod N}, schreibt dorthin und erhöht count\texttt{count}. Das +N+N hält die Zahl vor dem  mod \bmod nichtnegativ; in vielen Programmiersprachen ergibt der Rest von −1-1 durch NN sonst −1-1. popBack\texttt{popBack} liest Platz (head+count−1) mod N(\texttt{head} + \texttt{count} - 1) \bmod N und verringert count\texttt{count}. Eine doppelt verkettete Liste mit Wächter leistet dasselbe.

Zusammenfassung

  • Stapel: push\texttt{push}, pop\texttt{pop}, top\texttt{top} nach LIFO. Warteschlange: enqueue\texttt{enqueue}, dequeue\texttt{dequeue} nach FIFO. Beide sind abstrakte Datentypen.

  • Ein Stapel im Array arbeitet am Ende (O(1)O(1), mit Verdopplung amortisiert O(1)O(1)), in der Liste am Kopf (O(1)O(1)).

  • Der Ringpuffer hält head\texttt{head} und count\texttt{count} und rechnet Plätze modulo NN. Jede Operation kostet O(1)O(1). Mit head\texttt{head} und tail\texttt{tail} allein sind voll und leer nicht zu unterscheiden.

  • Klammerprüfung: Öffnende Klammern auf den Stapel, jede schließende muss zur obersten passen, am Ende muss der Stapel leer sein. Laufzeit O(n)O(n).

  • Postfix-Auswertung: Zahlen auf den Stapel, ein Operator verknüpft die beiden obersten. Das zuerst entnommene Element ist der rechte Operand.

  • Jede Rekursion läuft auf dem Aufrufstapel; ihr Speicherbedarf wächst mit der Rekursionstiefe.

  • Die Breitensuche bearbeitet Knoten in der Reihenfolge ihrer Entdeckung, also mit einer Warteschlange. Eine Deque vereint Stapel und Warteschlange.

Übungen

Aufgabe 1Multiple Choice

Auf eine leere Warteschlange wirken nacheinander enqueue\texttt{enqueue} a, enqueue\texttt{enqueue} b, enqueue\texttt{enqueue} c, dequeue\texttt{dequeue}, enqueue\texttt{enqueue} d, dequeue\texttt{dequeue}. Was liefert danach front\texttt{front}?

Aufgabe 2Numerisch

Ein Ringpuffer hat N=10N = 10 Plätze, head=7\texttt{head} = 7 und count=6\texttt{count} = 6. Auf welchem Platz steht das Element, das zuletzt angestellt wurde?

Aufgabe 3Numerisch

Werte den Postfix-Ausdruck 9 3 / 4 2 - *\texttt{9 3 / 4 2 - *} aus. Dabei ist /\texttt{/} die Division.

Aufgabe 4Freitext

Setze eine Warteschlange mit zwei Stapeln IN\texttt{IN} und OUT\texttt{OUT} um, auf die du nur mit push\texttt{push}, pop\texttt{pop} und isEmpty\texttt{isEmpty} zugreifst. Zeige, dass mm beliebige Operationen auf der anfangs leeren Warteschlange zusammen O(m)O(m) Stapeloperationen kosten, also amortisiert O(1)O(1) je Operation.

Aufgabe 5Freitext

Beweise: Liefert balanced(w)\texttt{balanced(w)} den Wert true\texttt{true}, dann ist ww korrekt geklammert (im Sinne der Regeln in der Lektion).