.webp)
Eine Warteschlange (engl. Queue) ist eine Datenstruktur, in der Elemente nach dem Warteschlangenprinzip (auch FIFO-Prinzip) eingefügt und gelöscht werden.
Erklärung
Eine Queue heißt auf Deutsch Warteschlange und genau so kannst du dir diese Datenstruktur auch vorstellen:
Hierbei gilt das "First in First Out"-Prinzip: die erste Person, die sich anstellt, wird auch als Erstes bedient.
Operationen am Beispiel
Eine Queue hat drei wichtige Operationen, die auf ihr aufgeführt werden können:
- Enqueue: Einfügen eines neuen Objekts.
- Dequeue: Löschen des ersten Objekts.
- Empty: Überprüfen, ob die Queue leer ist.
Enqueue
Schau dir das am besten am Beispiel einer Warteschlange an.
Die neue Person stellt sich an das Ende der Schlange an.
Dequeue
Die erste Person der Schlange wird als Nächstes bedient.
Empty
Bei der Operation Empty überprüfst du, ob die Schlange leer ist.
Aufbau
Eine Queue kann als doppelt verkettete Liste implementiert werden.
Du benötigst zwei Wächterknoten:
- head: Erster Knoten in der Queue.
- tail: Letzter Knoten.
Operationen an der Datenstruktur
Nun schau dir wieder die drei Operationen an, die du auf eine Queue anwenden kannst:
Enqueue
Um ein neues Element an die Queue zu hängen, fügst du sie vor den Wächterknoten tail ein.
Dafür müssen zuerst die Zeiger von dem neuen Knoten auf den letzten Daten-Knoten und auf tail zeigen.
Dann lässt du die Zeiger von dem letzten Daten-Knoten und tail auf den neuen Knoten zeigen:
Dequeue
Um das erste Element aus der Queue zu löschen, lässt du den Zeiger von head auf den zweiten Knoten zeigen und umgekehrt:
Das erste Element ist nun gelöscht, da keine Knoten aus der Liste auf sie zeigen.
Empty
Mit der Empty-Operation überprüfst du, ob eine Queue leer ist.
Das ist der Fall, wenn head auf tail und tail auf head zeigt:
Nutzungskontext
Queues werden oft als Zwischenspeicher verwendet: Dabei werden Daten von einem Gerät zum anderen "durchgereicht". Der Vorteil dabei ist, dass die beiden Geräte getrennt voneinander einlesen und verarbeiten können.
Ein anderes Wort für Zwischenspeicher ist Buffer (deutsch Puffer). Eine Queue wird gerne als Ringbuffer implementiert. Der sieht ungefähr so aus:
Queues können außerdem für Benutzeroberflächen verwendet werden, um die Eingaben über die Maus und die Tastatur zu speichern.
Beispiele
Equeue
Füge nun nochmal zur Übung die 2 an die Queue an:
2 muss also auf 4 und tail zeigen und danach 4 und tail auf 2:
Dequeue
Nun entferne nochmal zur Übung den ersten Knoten aus der Queue.
head und 7 zeigen nun auf den jeweils Anderen:
Dadurch zeigt kein Knoten mehr auf 12, wodurch sie aus der Liste gelöscht wurde.
Empty
Wenn du überprüfen möchtest, ob die Queue leer ist, dann musst du nur überprüfen, ob head auf tail und tail auf head zeigt. Da das hier nicht der Fall ist, ist sie nicht leer.
.png)
.svg)
