Warteschlange (Queue): FIFO einfach erklärt
Du lernst, wie eine Warteschlange Einträge ordnet, wie du sie bedienst und wie du sie im Speicher umsetzen kannst.
Kurz gesagt
Eine Warteschlange, englisch Queue, entnimmt den zuerst eingefügten noch vorhandenen Eintrag zuerst. Das heißt FIFO, kurz für First in, first out: zuerst hinein, zuerst heraus.
Eine Queue ist eine Datenstruktur, also eine festgelegte Art, Daten zu ordnen und zu verwalten. Einen einzelnen gespeicherten Eintrag nennen wir Element. Du untersuchst die Reihenfolge, die Arbeitsschritte und verschiedene Umsetzungen einer Queue. Alle Beispiele und Aufgabenfälle auf dieser Seite sind erfunden.
Deine Lernziele
Eine Queue arbeitet nach FIFO: First in, first out bedeutet „zuerst hinein, zuerst heraus“. Neue Elemente kommen hinten hinzu. Entnommen wird vorn das Element, das von den noch vorhandenen Elementen zuerst eingefügt wurde. Bereits entnommene Elemente gehören nicht mehr zur Queue.
Ein Stack ist ein Stapel von Elementen. Er arbeitet nach LIFO: Last in, first out bedeutet „zuletzt hinein, zuerst heraus“. Beim Stack wird das zuletzt eingefügte noch vorhandene Element zuerst entnommen. Queue und Stack unterscheiden sich damit in ihrer Entnahmereihenfolge.
FIFO
Von den noch vorhandenen Elementen wird das zuerst eingefügte Element zuerst entnommen.
Beispiel: Queue und Stack mit erfundenen Einträgen
- 1In eine leere Queue und einen leeren Stack kommen nacheinander „Wolke“, „Blitz“ und „Regen“. Vorher wird nichts entnommen.
- 2Die Queue entnimmt zuerst „Wolke“, weil dieser Eintrag zuerst eingefügt wurde.
- 3Der Stack entnimmt zuerst „Regen“, weil dieser Eintrag zuletzt eingefügt wurde.
Teste dich
Eine Operation ist ein festgelegter Arbeitsschritt. Wir verwenden ein vereinfachtes Modell, also eine Darstellung mit festen Regeln, und keinen ausführbaren Programmcode. In enqueue(X) steht X für den einzufügenden Eintrag. Die leeren Klammern bei dequeue(), front() und empty() bedeuten, dass kein Eintrag mitgegeben wird.
In unserem Modell liefert dequeue() den entnommenen Eintrag zurück. front() liefert den vorderen Eintrag, ohne ihn zu entfernen. empty() liefert einen Wahrheitswert, also eine Antwort „wahr“ oder „falsch“: true steht für „wahr“, false für „falsch“. front() und empty() verändern die Queue nicht.
Bei einer leeren Queue kann dequeue() nichts entnehmen. Auch front() hat dann kein vorderes Element zum Anzeigen. Eine feste Kapazität ist die festgelegte Höchstzahl gleichzeitig gespeicherter Einträge. Ist eine Queue mit fester Kapazität voll, kann enqueue() keinen weiteren Eintrag einfügen. Wie eine konkrete Umsetzung diese Fälle meldet, legt sie selbst fest.
| Operation | Wirkung in unserem Modell |
|---|---|
| enqueue(X) | Fügt X hinten ein, wenn ein Platz verfügbar ist. |
| dequeue() | Entfernt und liefert das vordere Element, sofern die Queue nicht leer ist. |
| front() | Liefert das vordere Element, ohne es zu entfernen, sofern es eines gibt. |
| empty() | Liefert true bei leerer Queue, sonst false; verändert die Queue nicht. |
Merke: front() betrachtet, dequeue() entnimmt. empty() prüft, ob die Queue leer ist. Eine Abfrage mit front() oder empty() verschiebt und entfernt keine Elemente.
Teste dich
Wir schreiben den Inhalt einer Queue in eckige Klammern. Die Elemente stehen darin von vorn nach hinten; Kommas trennen sie. [16, 4] bedeutet also: 16 steht vorn und 4 dahinter. [] steht für eine leere Queue.
Notiere nach jedem Schritt den vollständigen Inhalt. Bei enqueue(X) ergänzt du X rechts, also hinten. Bei dequeue() streichst du das linke, also vordere Element. front() liest das linke Element, ohne es zu streichen. empty() prüft, ob die Klammern leer sind. Beide Abfragen lassen den Inhalt unverändert.
Für unsere Schrittfolgen ist genügend Platz vorhanden, sofern keine feste Kapazität genannt wird. dequeue() und front() verwenden wir in diesen Folgen bei nicht leeren Queues.
Beispiel: Eine erfundene Zahlenfolge verfolgen
- 1Start: []
- 2enqueue(16) ergibt [16].
- 3enqueue(4) ergibt [16, 4].
- 4enqueue(29) ergibt [16, 4, 29].
- 5dequeue() liefert 16. Übrig bleibt [4, 29].
- 6dequeue() liefert 4. Übrig bleibt [29].
- 7enqueue(11) ergibt [29, 11].
- 8front() liefert 29. Die Queue bleibt [29, 11].
Teste dich
Ein Array besitzt eine beim Anlegen festgelegte Anzahl nummerierter Speicherplätze. Auch unbelegte Plätze gehören zum Array und benötigen Speicher. Wir betrachten zunächst eine einfache Array-Queue, die ihre Einträge ab Platz 0 zusammenhält. Nach einer Entnahme verschiebt sie die übrigen Einträge nach links. Je mehr Einträge übrig sind, desto mehr muss sie verschieben.
Ein Ringpuffer ist eine kreisförmige Organisation eines Arrays, keine davon unabhängige Speicherstruktur. Nach dem letzten Arrayplatz folgt wieder Platz 0. Angaben über den Anfang und das Ende halten die Queue-Reihenfolge fest. Frei gewordene Plätze können erneut genutzt werden; die verbleibenden Einträge werden dabei nicht verschoben. Ein voller Ringpuffer mit fester Kapazität kann keinen weiteren Eintrag aufnehmen. Unsere Queue überschreibt dabei keine vorhandenen Einträge. Weder Umlaufen noch Verschieben schafft zusätzliche Arrayplätze.
Eine verkettete Liste besteht aus Knoten. Jeder Knoten speichert einen Eintrag und einen Verweis auf den nächsten Knoten. Ein Verweis hält fest, welcher Knoten folgt. Unsere Listen-Queue besitzt außerdem Verweise auf den ersten und letzten Knoten. So kann sie hinten einen Knoten anhängen und vorn einen entfernen, ohne die übrige Liste zu durchlaufen. Sie braucht keine vorab unbesetzten Arrayplätze. Dafür benötigt jeder Knoten zusätzlichen Speicher, etwa für seinen Verweis. Eine Liste braucht deshalb nicht grundsätzlich weniger Speicher als eine Array-Queue.
Beim Ringpuffer ohne Vergrößern werden je Einfügen oder Entnehmen einzelne Plätze und Positionsangaben bearbeitet. Bei der beschriebenen Liste werden einzelne Knoten und Verweise bearbeitet. Die Zahl dieser Verwaltungsschritte wächst nicht mit der Zahl der gespeicherten Einträge. Soll ein Array mehr Plätze erhalten, wird ein größeres Array angelegt und die vorhandenen Einträge werden dorthin kopiert. Das bisherige Array vergrößert sich nicht selbst. Beim Kopieren müssen alle vorhandenen Einträge übertragen werden.
| Umsetzung | Speicherung | Entnahme vorn |
|---|---|---|
| Array mit Verschieben | Feste Plätze; Einträge stehen zusammen ab Platz 0. | Die übrigen Einträge rücken nach links. |
| Ringpuffer im Array | Feste Plätze; Anfang und Ende wandern im Kreis. | Der Anfang rückt weiter; die übrigen Einträge bleiben auf ihren Plätzen. |
| Liste mit Anfangs- und Endverweis | Verbundene Knoten mit zusätzlichem Speicher für Verweise. | Der vordere Knoten wird entfernt; Anfangs- und Endverweis werden passend angepasst. |
Beispiel: Ein erfundener Ringpuffer mit vier Plätzen
- 1Die Plätze heißen 0, 1, 2 und 3. Nach Platz 3 folgt wieder Platz 0.
- 2Anfang: Platz 1 enthält 60, Platz 2 enthält 70 und Platz 3 enthält 80. Platz 0 ist frei. Vorn steht 60.
- 3enqueue(90) nutzt Platz 0. Die Reihenfolge von vorn nach hinten lautet [60, 70, 80, 90].
- 4dequeue() liefert 60 und gibt Platz 1 frei. Vorn steht jetzt 70 auf Platz 2.
- 5enqueue(25) nutzt Platz 1. Die Reihenfolge lautet [70, 80, 90, 25].
Teste dich
Alles auf einen Blick
Warteschlange (Datenstruktur)
Eine Queue entnimmt nach FIFO das zuerst eingefügte noch vorhandene Element; ein Stack nach LIFO das zuletzt eingefügte.
enqueue fügt hinten ein, wenn Platz vorhanden ist. dequeue entfernt bei einer nicht leeren Queue das vordere Element.
front betrachtet bei einer nicht leeren Queue das vordere Element. empty prüft auf Leerheit. Beide verändern die Queue nicht.
In der beschriebenen Verschiebevariante rücken übrige Einträge nach einer Entnahme nach links. Für mehr Plätze braucht es ein größeres Array und das Kopieren der Einträge.
Ein Array wird im Kreis genutzt. Das vermeidet das Verschieben übriger Einträge, schafft aber keine zusätzlichen Plätze.
Mit Verweisen auf Anfang und Ende kann die Queue hinten Knoten anhängen und vorn entfernen, ohne die übrige Liste zu durchlaufen. Knoten brauchen zusätzlichen Speicher.
Erfundene Aufträge: Was steht am Ende vorn?
- 1Aufgabe: Starte mit einer leeren Queue. Führe enqueue(„Druck“), enqueue(„Kopie“), front(), dequeue(), enqueue(„Scan“) und dequeue() aus. Gesucht ist das vordere Element danach.
- 2enqueue(„Druck“) ergibt [„Druck“].
- 3enqueue(„Kopie“) ergibt [„Druck“, „Kopie“].
- 4front() liefert „Druck“. Die Queue bleibt [„Druck“, „Kopie“].
- 5dequeue() liefert „Druck“. Übrig bleibt [„Kopie“].
- 6enqueue(„Scan“) ergibt [„Kopie“, „Scan“].
- 7dequeue() liefert „Kopie“. Übrig bleibt [„Scan“].
- 8Ergebnis: „Scan“ steht vorn, weil die beiden vorher eingefügten Einträge entnommen wurden.
Fehler finden
Fehler in Zeile 3Die Anzahl wurde fälschlich verringert. front() entfernt keinen Eintrag. Richtig: Nach front() enthält die Queue zwei Einträge.
Lückentext
Eine Queue erhält nacheinander „Korn“, „Salz“ und „Mehl“. Es wurde noch nichts entnommen. Als Nächstes kommt heraus. Eine andere Queue enthält vorn „Pinsel“ und dahinter „Lineal“. Nach front() enthält sie . Ein Ringpuffer nutzt die Plätze 0 bis 5. Auf Platz 5 folgt bei der Suche nach dem nächsten Platz die Nummer .