Stapel und Warteschlangen
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 kostet,
einen Ringpuffer mit Indexrechnung modulo 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 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.
Auf einen leeren Stapel werden , , gelegt. Dann wird einmal das oberste Element genommen, wird gelegt, und danach wird dreimal das oberste genommen. In welcher Reihenfolge kommen die Zahlen heraus?
Stapel (Stack)
Ein Stapel (englisch stack, auch Keller) ist ein abstrakter Datentyp für eine Sammlung von Elementen mit vier Operationen:
- legt oben auf den Stapel.
- entfernt das oberste Element und gibt es zurück.
- gibt das oberste Element zurück, ohne es zu entfernen.
- 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 liefert den Wert , und ein anschließendes liefert und lässt den Stapel so zurück, wie er vor dem war. und auf einem leeren Stapel sind Fehler.
Gegenbeispiel. Eine Sammlung, bei der 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).
Stapel mit Array und mit Liste
Stapel mit Array und mit Liste
Im Array zählt die Elemente. Sie liegen in bis , oben ist .
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 2 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 0 | |
| 7 | 1 | |
| 8 | 2 | |
| 9 | 1 | |
| 10 | 1 |
ist die Kapazität. liefert , prüft .
Ohne Zeile 2 und 3 kostet jede Operation , solange Platz ist. Mit Verdopplung kostet ein einzelnes manchmal , aber wie beim dynamischen Array kosten Operationen zusammen , amortisiert je Operation.
Mit einer einfach verketteten Liste ist das Einfügen vorn und das Entfernen des ersten Knotens. Beides kostet im schlechtesten Fall, dafür braucht jedes Element einen Zeiger.
Warteschlange (Queue)
Eine Warteschlange (englisch queue) ist ein abstrakter Datentyp mit den Operationen (hinten anstellen), (das vorderste Element entfernen und zurückgeben), (das vorderste ansehen) und . 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 zu halten. Dann muss alle übrigen Elemente einen Platz nach vorn schieben und kostet . Das vermeidet der Ringpuffer.
Ringpuffer
Ein Ringpuffer speichert die Warteschlange in einem Array mit Plätzen, bis , und denkt sich das Array zu einem Kreis geschlossen: Hinter Platz kommt Platz . Er merkt sich zwei Zahlen: , den Platz des vordersten Elements, und , die Anzahl der Elemente.
Für ganze Zahlen und ist der Rest bei der Division von durch , eine Zahl von bis . Damit ist der erste freie Platz hinter der Schlange .
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 2 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 0 | |
| 7 | 1 | |
| 8 | 2 | |
| 9 | 1 | |
| 10 | 1 | |
| 11 | 1 | |
| 12 | 1 |
Ein Ringpuffer mit vier Plätzen
Ein Ringpuffer mit vier Plätzen
, zu Beginn und . Ein Strich bedeutet einen freien Platz.
| Schritt | Operation | Platz 0 | Platz 1 | Platz 2 | Platz 3 | head | count | Schlange von vorn |
|---|---|---|---|---|---|---|---|---|
| 0 | Start | – | – | – | – | 0 | 0 | leer |
| 1 | a | a | – | – | – | 0 | 1 | a |
| 2 | b | a | b | – | – | 0 | 2 | a, b |
| 3 | c | a | b | c | – | 0 | 3 | a, b, c |
| 4 | , liefert a | – | b | c | – | 1 | 2 | b, c |
| 5 | , liefert b | – | – | c | – | 2 | 1 | c |
| 6 | d | – | – | c | d | 2 | 2 | c, d |
| 7 | e | e | – | c | d | 2 | 3 | c, d, e |
| 8 | f | e | f | c | d | 2 | 4 | c, d, e, f |
| 9 | , liefert c | e | f | – | d | 3 | 3 | d, e, f |
In Schritt 7 ist der Platz : Die Schlange läuft über das Ende des Arrays hinaus und setzt vorn fort. In Schritt 8 ist , der Puffer ist voll. Ein weiteres bricht in Zeile 3 ab; ein dynamischer Ringpuffer legt stattdessen ein doppelt so großes Array an und kopiert die Elemente ab der Reihe nach hinein.
Ein Ringpuffer hat Plätze, und . Auf welchen Platz schreibt das nächste ?
Der Ringpuffer ist eine Warteschlange
Nach jeder Folge von - und -Aufrufen, von denen keiner einen Fehler meldet, gilt mit und : Die Warteschlange enthält Elemente, und von vorn nach hinten stehen sie auf den Plätzen
.
Jede Operation kostet im schlechtesten Fall .
Induktion über die Anzahl der Operationen. Zu Beginn ist , und die Schlange ist leer.
Gilt die Aussage vor einem mit , dann schreibt Zeile 4 auf , den Platz direkt hinter dem letzten Element. Dieser Platz gehört nicht zu den belegten, denn die Zahlen haben wegen paarweise verschiedene Reste modulo . Mit statt steht das neue Element also hinten, wie FIFO es verlangt.
Gilt die Aussage vor einem mit , dann liefert Zeile 9 das Element auf Platz , das vorderste. Mit und sind die Plätze genau die übrigen, in derselben Reihenfolge.
Jede Operation hat eine feste Zahl von Schritten, unabhängig von und .
Voll und leer sehen gleich aus
Voll und leer sehen gleich aus
Viele Umsetzungen speichern statt einen zweiten Index für den ersten freien Platz und prüfen „leer“ mit . Im Beispiel oben wäre nach Schritt 8 aber , obwohl der Puffer voll ist. Der Code hält den vollen Puffer für leer, und meldet fälschlich eine leere Schlange.
Mit und allein lassen sich die möglichen Füllstände nicht unterscheiden, denn modulo hat nur Werte. Entweder man speichert wie hier, oder man lässt immer einen Platz frei und nennt den Puffer schon bei Elementen voll.
Anwendung: Klammern prüfen
Anwendung: Klammern prüfen
Eine Zeichenkette aus den Klammern heißt korrekt geklammert, wenn sie nach diesen Regeln entsteht: Die leere Kette ist korrekt geklammert. Sind und korrekt geklammert, dann auch , , und (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. ist wahr, wenn die öffnende Klammer zu ist.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 2 | |
| 5 | 3 | |
| 6 | 2 | |
| 7 | 3 | |
| 8 | 1 |
Für : und kommen auf den Stapel. Bei liefert die , die nicht passt, also . 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 . Jedes Zeichen kostet , die Prüfung also für Zeichen. Dass der Algorithmus genau die korrekt geklammerten Ketten annimmt, beweist du in einer Übung.
Anwendung: Postfix-Ausdrücke auswerten
Anwendung: Postfix-Ausdrücke auswerten
In Postfix-Schreibweise steht ein Operator hinter seinen beiden Operanden: wird , und wird . Klammern und Vorrangregeln braucht man nicht mehr. Die Auswertung liest von links: Eine Zahl kommt auf den Stapel. Ein Operator nimmt zuerst , dann und legt zurück, wobei der Operator ist. Am Ende liegt genau eine Zahl auf dem Stapel, das Ergebnis.
| Schritt | Zeichen | Aktion | Stapel danach (unten links) |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | , , lege | ||
| 5 | |||
| 6 | , , lege | ||
| 7 | , , lege | ||
| 8 | |||
| 9 | , , lege |
Das Ergebnis ist , und tatsächlich ist . 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.
Welchen Wert hat der Postfix-Ausdruck ?
Der Aufrufstapel einer Rekursion
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 , das bei den Wert und sonst liefert:
Die rechte Spalte nennt für jeden Rahmen den Wert von .
| Zeitpunkt | Rahmen auf dem Stapel (unten links) |
|---|---|
| beginnt | |
| ruft | |
| ruft | |
| ruft | |
| liefert | |
| liefert | |
| liefert | |
| liefert | leer |
Der zuletzt begonnene Aufruf endet zuerst: LIFO. Die größte Höhe des Stapels ist die Rekursionstiefe, hier 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.
Probier es aus
Deque
Eine Deque (double-ended queue, gesprochen wie „Deck“) erlaubt Einfügen und Entfernen an beiden Enden: , , , . Benutzt man nur und , verhält sie sich wie ein Stapel; mit und wie eine Warteschlange.
Im Ringpuffer kosten alle vier Operationen . setzt , schreibt dorthin und erhöht . Das hält die Zahl vor dem nichtnegativ; in vielen Programmiersprachen ergibt der Rest von durch sonst . liest Platz und verringert . Eine doppelt verkettete Liste mit Wächter leistet dasselbe.
Zusammenfassung
Stapel: , , nach LIFO. Warteschlange: , nach FIFO. Beide sind abstrakte Datentypen.
Ein Stapel im Array arbeitet am Ende (, mit Verdopplung amortisiert ), in der Liste am Kopf ().
Der Ringpuffer hält und und rechnet Plätze modulo . Jede Operation kostet . Mit und 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 .
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
Auf eine leere Warteschlange wirken nacheinander a, b, c, , d, . Was liefert danach ?
Ein Ringpuffer hat Plätze, und . Auf welchem Platz steht das Element, das zuletzt angestellt wurde?
Werte den Postfix-Ausdruck aus. Dabei ist die Division.
Setze eine Warteschlange mit zwei Stapeln und um, auf die du nur mit , und zugreifst. Zeige, dass beliebige Operationen auf der anfangs leeren Warteschlange zusammen Stapeloperationen kosten, also amortisiert je Operation.
Beweise: Liefert den Wert , dann ist korrekt geklammert (im Sinne der Regeln in der Lektion).