Mit Google fortfahren
Warteschlange (Queue): FIFO einfach erklärt
Eine Warteschlange, auf Englisch Queue, speichert Elemente in ihrer Ankunftsreihenfolge: Was zuerst hineinkommt, kommt zuerst wieder heraus. Dieses Prinzip heißt FIFO (First In – First Out).
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Warum eine Queue nach FIFO arbeitet
Stell dir eine Warteschlange an einer Kasse vor. Eine Person stellt sich hinten an. Bedient wird die Person, die vorne schon am längsten wartet. Genau diese Ordnung bildet eine Queue ab.
FIFO
First In – First Out bedeutet: Von allen noch gespeicherten Elementen wird das zuerst eingefügte Element auch zuerst entfernt.
Eine Queue hat deshalb zwei verschiedene Enden:
- vorne (front): Hier liegt das älteste vorhandene Element und wird entnommen.
- hinten (rear oder tail): Hier werden neue Elemente angefügt.
Du fügst nacheinander A, B und C ein. Die Queue sieht dann von vorne nach hinten so aus:
vorne → A | B | C ← hinten
A kam zuerst an. Deshalb wird A auch zuerst entfernt.
Eine Queue sortiert ihre Elemente nicht neu. Sie bewahrt die Einreihungsfolge.
Was die vier Grundoperationen tun
Die Queue wird durch ihre erlaubten Operationen beschrieben. Wie sie intern gespeichert ist, spielt für diese Bedeutung zunächst keine Rolle.
Grundoperationen
enqueue(x)fügt das Elementxhinten an.dequeue()gibt das Element vorne zurück und entfernt es.front()liest das Element vorne, entfernt es aber nicht.empty()prüft, ob kein Element gespeichert ist.
Die Namen können in Programmiersprachen abweichen. Eine Bibliothek kann etwa push statt enqueue und pop statt dequeue verwenden. Entscheidend ist die Wirkung der Operation.
Ausgangszustand: vorne → Herz Dame | Karo König | Kreuz Ass ← hinten
front()liefertHerz Dame. Die Queue bleibt unverändert.dequeue()liefert und entferntHerz Dame.- Danach liegt
Karo Königvorne.
Der Unterschied ist wichtig: front() schaut nur nach, dequeue() schaut nach und entfernt.
Was passiert bei einer leeren Queue?
Vor front() oder dequeue() solltest du mit empty() prüfen, ob ein Element vorhanden ist. Auf einer leeren Queue gibt es kein vorderstes Element. Wie ein Programm diesen Fall meldet, muss die konkrete Implementierung festlegen.
Der Versuch, aus einer leeren Queue zu entnehmen, wird Underflow genannt. Eine robuste Implementierung behandelt diesen Randfall ausdrücklich, statt so zu tun, als gäbe es ein Element.
Wie du Befehlsfolgen sicher simulierst
Notiere nach jeder Operation den vollständigen Zustand von vorne nach hinten. So überspringst du keinen Schritt und verwechselst die beiden Enden nicht.
Die Queue ist anfangs leer. Werte die Folge aus:
enqueue(7)→vorne → 7 ← hintenenqueue(12)→vorne → 7 | 12 ← hintenenqueue(4)→vorne → 7 | 12 | 4 ← hintendequeue()liefert7→vorne → 12 | 4 ← hintenfront()liefert12→ die Queue bleibtvorne → 12 | 4 ← hintenenqueue(2)→vorne → 12 | 4 | 2 ← hintendequeue()liefert12→vorne → 4 | 2 ← hinten
Die ausgegebenen Werte sind zuerst 7, dann 12. Am Ende enthält die Queue von vorne nach hinten 4 | 2.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Bei enqueue kommt ein neues Element am hinzu. dequeue entfernt das vorhandene Element am Anfang. front liest dieses Element, es zu entfernen.
Wie eine Queue intern gespeichert werden kann
Eine Queue ist ein abstrakter Datentyp: Ihre Operationen und deren Wirkung sind festgelegt, nicht aber eine einzige Speicherform. Deshalb können verschiedene Implementierungen nach außen dasselbe Queue-Verhalten zeigen.
| Implementierung | Grundidee | Wichtige Besonderheit |
|---|---|---|
| Array | Elemente liegen in Feldern eines Arrays. | Bei fester Größe ist die Kapazität begrenzt. |
| Ringpuffer | Ein- und Ausgabezeiger laufen zyklisch durch ein Array. | Freie Plätze am Anfang werden nach dem Umlauf wieder genutzt. |
| Einfach verkettete Liste | Jeder Knoten verweist auf seinen Nachfolger; Zeiger markieren Anfang und Ende. | Neue Knoten können am Ende angehängt und alte am Anfang entfernt werden. |
| Doppelt verkettete Liste mit Wächtern | Knoten verweisen in beide Richtungen; Wächter begrenzen Anfang und Ende. | Beim Ändern müssen die Verweise der beteiligten Nachbarn passend gesetzt werden. |
Verkettete Queue
Bei einer einfach verketteten Queue zeigt head auf den vordersten und tail auf den hintersten Knoten.
enqueue(x): Der bisher letzte Knoten verweist auf den neuen Knoten; anschließend wirdtailauf ihn gesetzt.dequeue():headwird auf den Nachfolger des bisherigen ersten Knotens gesetzt; der entfernte Speicher wird freigegeben.- Beim ersten Element zeigen
headundtailauf denselben Knoten. - Wird dieses einzige Element entfernt, muss die Queue danach wieder eindeutig leer sein; beide Zeiger werden entsprechend zurückgesetzt.
Die Implementierung darf verschieden sein. Nach außen muss trotzdem gelten: hinten einfügen, vorne entnehmen, FIFO-Reihenfolge bewahren.
Was leer und voll bei Implementierungen bedeutet
Leer und voll sind nicht dasselbe Problem:
- Leer: Es ist kein Element zum Lesen oder Entfernen vorhanden. Das kann bei jeder Queue auftreten.
- Voll: Es gibt in einer kapazitätsbegrenzten Implementierung keinen freien Speicherplatz für ein weiteres Element.
Overflow
Overflow bedeutet hier: Ein Element soll eingefügt werden, obwohl die feste Kapazität bereits ausgeschöpft ist.
Ein Ringpuffer braucht für diesen Fall eine festgelegte Strategie. Die Implementierung kann den Überlauf melden, zusätzlichen Speicher bereitstellen oder – wenn der Anwendungsfall das ausdrücklich erlaubt – das älteste Element überschreiben. Beim Überschreiben gehen alte Daten verloren.
Eine verkettete Queue hat dagegen nicht dieselbe feste Arraygrenze. Auch sie ist in einem realen Rechner nicht grenzenlos: Neue Knoten benötigen verfügbaren Speicher. Das ist jedoch ein anderer Grenzfall als ein Ringpuffer mit vorab festgelegter Kapazität.
Ein Ringpuffer fasst drei Elemente und enthält A | B | C. Nun soll D eingefügt werden.
- Bei der Strategie Überlauf melden bleibt
A | B | Cerhalten, und das Einfügen scheitert kontrolliert. - Bei der Strategie ältestes Element überschreiben geht
Averloren; die logische FIFO-Reihenfolge der verbleibenden Elemente ist danachB | C | D.
Welche Reaktion richtig ist, hängt vom festgelegten Anwendungsfall ab. Sie darf nicht zufällig entstehen.
Queue oder Stack – welche Reihenfolge brauchst du?
Eine Queue wird leicht mit einem Stack verwechselt. Beim Stack wird das zuletzt abgelegte Element zuerst entnommen: LIFO (Last In – First Out).
| Frage | Queue | Stack |
|---|---|---|
| Welche Reihenfolge gilt? | FIFO | LIFO |
| Wo wird eingefügt? | hinten | am selben zugänglichen Ende |
| Was wird als Nächstes entnommen? | das älteste vorhandene Element | das zuletzt abgelegte Element |
Du speicherst nacheinander 1, 2, 3.
- Queue: Die erste Entnahme liefert
1. - Stack: Die erste Entnahme liefert
3.
Die Eingabefolge ist gleich, aber die Entnahmeregel ist verschieden.
Queues passen beispielsweise zu Druckaufträgen oder gepufferten Eingaben, wenn die Ankunftsreihenfolge erhalten bleiben soll. Sie entkoppeln das Einstellen eines Auftrags von seiner späteren Verarbeitung.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Warteschlange (Queue)
- FIFO: ältestes vorhandenes Element zuerst
- Operationen: enqueue, dequeue, front, empty
- Randfälle: leer, ein Element, volle feste Kapazität
- Implementierungen: Array, Ringpuffer, verkettete Liste
- Abgrenzung: Queue FIFO, Stack LIFO
- Anwendungen: Aufträge und Eingaben puffern