Bei einer Queue (Warteschlange) handelt es sich um eine Datenstruktur die einer Liste ähnlich ist. Allerdings ist die Funktionalität eingeschränkter Natur, denn eine Queue zeichnet sich dadurch aus, dass hier das FIFO-Prinzip (First In, First Out) gilt. Das bedeutet, dass das erste Element, das einer Queue hinzugefügt wird, das erste Element ist, das wieder entfernt wird. Das Hinzufügen von Daten wird als Enqueue, das Entfernen als Dequeue bezeichnet. Das klassische Beispiel zur Queue ist die Druckerwarteschlange, bei der die Druckaufträge in der Reihenfolge ihres Eingangs nach und nach bearbeitet werden. — Nachfolgende Abbildung macht die Funktionsweise einer Queue deutlich:
Liste
Eine Queue kann in Python auf unterschiedliche Art und Weise implementiert werden. Eine Möglichkeit besteht darin, eine andere — in Python zur Verfügung stehende — Datenstruktur zu verwenden: die Liste. Der Code dazu sieht wie folgt aus:
# Neue leere Liste erzeugen
queue = list()
# Elemente zur Queue hinzufügen
queue.append(5)
queue.append(13)
queue.append(22)
queue.append(7)
queue.append(45)
print(queue) # -> [5, 13, 22, 7, 45]
# Ein Element entfernen (gemäß des FIFO-Prinzips)
queue.pop(0)
print(queue) # -> [13, 22, 7, 45]Die erste Zahl, die hinzugefügt wurde, ist die 5. Dem FIFO-Prinzip folgend, ist diese Zahl wieder als erstes zu entfernen, was hier mithilfe der Methode pop() umgesetzt wird. Dabei wird der Index 0 als Parameter angegeben (erstes Element der Liste bzw. der Queue).
Zu diesem Beispiel sei noch folgendes angemerkt: Die gezeigte Implementierung entspricht nicht obiger Abbildung. Denn hier wird ein neues Element mit der Methode append() stets an das Ende der Liste angefügt, und die Elemente werden mit pop(0) vom Anfang der Liste entfernt. Dies ist aber unerheblich, denn entscheidend ist, dass das FIFO-Prinzip gewahrt bleibt, und das ist der Fall. Folgende Abbildung kommt der Implementierung als Liste näher:
Die Verwendung einer Liste stellt eine sehr einfache Implementierung dar, die aber in der Praxis nicht zu empfehlen ist, da sie einen großen Nachteil hat: Durch das Entfernen des Elements an Index 0, müssen alle übrigen Elemente nach links verschoben werden, was zeitaufwendig ist. In der Dokumentation zu Datenstrukturen in Python wird dazu ausgeführt:
However, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).
collections.deque
Aus diesem Grunde stellt die Python-Bibliothek collections.deque bereit. Hierbei wird eine Queue mithilfe einer Linked List realisiert. Oder anders ausgedrückt: Bei collections.deque handelt es sich um eine Implementierung einer Linked List. In Code gegossen, könnte dies wie folgt aussehen:
from collections import deque
queue = deque()
# Elemente zur Queue hinzufügen
queue.append(5)
queue.append(13)
queue.append(22)
queue.append(7)
queue.append(45)
print(queue) # -> [5, 13, 22, 7, 45]
# Ein Element entfernen (gemäß des FIFO-Prinzips)
queue.popleft()
print(queue) # -> [13, 22, 7, 45]Es handelt sich hierbei um die Abwandlung eines Beispiels aus der offiziellen Python-Dokumentation, in der hierzu folgendes ausgeführt wird:
To implement a queue, use
collections.dequewhich was designed to have fast appends and pops from both ends.
Wie auch beim Listen-Beispiel, wird ein Element jeweils am Ende eingefügt, und ein Element am Anfang — mit queue.popleft() — entfernt. Das Element, das als erstes hinzugefügt wurde, wird also als erstes Element wieder entfernt (First In, First Out).
Von diesen beiden Beispielen abgesehen, gibt es noch andere Möglichkeiten der Implementierung einer Queue. Für den Einstieg möchte ich es aber bei diesen beiden Beispielen belassen. Der nächste Artikel zu Datenstrukturen befasst sich dann mit Stacks.
Zuletzt aktualisiert am 17. Februar 2023