Die Bedeutung von Warteschlangen in der Programmierung
Datenstrukturen bilden das Fundament der Programmierung. Sie erlauben es uns, Informationen so zu organisieren, dass wir sie effizient handhaben können. Eine der einfachsten und am weitesten verbreiteten Strukturen ist die Warteschlange.
In diesem Beitrag werden wir die Warteschlange näher untersuchen und ihre Umsetzung in der Programmiersprache Python beleuchten.
Was genau ist eine Warteschlange?
Eine Warteschlange ist eine lineare Datenstruktur, die nach dem Prinzip „First In, First Out“ (FIFO) arbeitet. Das bedeutet, dass das Element, das zuerst hinzugefügt wird, auch zuerst entfernt wird. Im Grunde ist sie das Gegenstück zur Stack-Datenstruktur.
Um das Konzept zu veranschaulichen, stellen wir uns eine echte Warteschlange vor, wie sie beispielsweise an einer Kinokasse anzutreffen ist.
Betrachten wir die Situation: Erst wenn die Person an erster Stelle abgefertigt wurde, kann die zweite Person an den Schalter treten. Das bedeutet, dass die erste Person zuerst an die Reihe kommt und dann die zweite usw. Dies ist das FIFO-Prinzip in Aktion. Solche Warteschlangen begegnen uns häufig im Alltag.
Die Datenstruktur der Warteschlange funktioniert nach dem gleichen Prinzip. Nachdem wir das Wesen und die Funktionsweise der Warteschlange verstehen, wollen wir uns den grundlegenden Operationen zuwenden, die damit ausgeführt werden können.
Operationen mit Warteschlangen
Ähnlich wie beim Stapel (Stack) gibt es zwei Hauptoperationen, die wir in einer Warteschlange durchführen können:
Hinzufügen (Enqueue)
Diese Operation fügt ein neues Datenelement am Ende der Warteschlange hinzu. Dieser Punkt wird oft als „Rückseite“ der Warteschlange bezeichnet.
Entfernen (Dequeue)
Entfernt das Datenelement am Anfang der Warteschlange. Dieser Punkt wird als „Vorderseite“ bezeichnet.
Um die Operationen besser zu verstehen, betrachten wir einige visuelle Darstellungen, denn ein Bild sagt oft mehr als tausend Worte.
Zusätzlich zu den Kernoperationen können wir uns weitere Hilfsfunktionen vorstellen, die uns Informationen über den aktuellen Zustand der Warteschlange liefern. Es gibt hier keine Begrenzung der Anzahl, jedoch wollen wir uns auf die grundlegenden beschränken.
Rückseite (Rear)
Diese Funktion gibt das Element am Ende der Warteschlange zurück.
Vorderseite (Front)
Diese Funktion gibt das erste Element der Warteschlange zurück.
Ist leer (isEmpty)
Diese Funktion gibt einen booleschen Wert (wahr oder falsch) zurück, je nachdem, ob die Warteschlange leer ist oder nicht.
Sind Sie von der Theorie gelangweilt? Zugegeben, Konzepte können manchmal etwas zäh sein.
Ich persönlich schon!
Jedoch führt kein Weg an den Grundlagen vorbei. Wir müssen sie verstehen, bevor wir uns mit der Implementierung beschäftigen können. Aber keine Sorge, jetzt ist es an der Zeit, uns die Hände mit etwas Code schmutzig zu machen.
Ich gehe davon aus, dass Python auf Ihrem Rechner installiert ist. Wenn das nicht der Fall ist, können Sie auch einen Online-Compiler nutzen.
Die Implementierung von Warteschlangen
Die Implementierung einer Warteschlange ist kein Hexenwerk und sollte nicht mehr als 15 Minuten in Anspruch nehmen. Sobald Sie es einmal verstanden haben, werden Sie es im Handumdrehen umsetzen können. Vielleicht sogar in wenigen Minuten nach dieser Anleitung.
Es gibt verschiedene Methoden, um eine Warteschlange in Python zu realisieren. Wir wollen uns verschiedene Ansätze Schritt für Schritt ansehen.
#1. Verwendung von Listen
Die Liste ist ein in Python integrierter Datentyp. Wir nutzen diesen Datentyp, um eine Warteschlange innerhalb einer Klasse umzusetzen. Wir werden den gesamten Prozess Schritt für Schritt ohne die Verwendung von Modulen durchgehen. Legen wir los!
Schritt 1:
Wir beginnen mit der Definition einer Klasse, die wir `Queue` nennen.
class Queue: pass
Schritt 2:
Innerhalb der Klasse brauchen wir eine Variable, um die Daten der Warteschlange zu speichern. Nennen wir diese `elements`. Und es wird natürlich eine Liste sein.
class Queue:
def __init__(self):
self.elements = []
Schritt 3:
Um Daten in die Warteschlange einzufügen, benötigen wir eine Methode innerhalb der Klasse. Diese Methode nennen wir `enqueue`, wie wir bereits im vorherigen Teil des Artikels besprochen haben.
Die Methode nimmt ein Datenelement entgegen und fügt es der Warteschlange (`elements`) hinzu. Wir nutzen die `append`-Methode des Listendatentyps, um Elemente am Ende der Warteschlange anzufügen.
class Queue:
# ...
def enqueue(self, data):
self.elements.append(data)
return data
Schritt 4:
Die Warteschlange benötigt auch eine Möglichkeit, Elemente zu entfernen. Diese Operation nennen wir `dequeue`. Sie haben wahrscheinlich schon vermutet, dass wir die `pop`-Methode des Listendatentyps verwenden werden. Ob Sie es erraten haben oder nicht, herzlichen Glückwunsch!
Die `pop`-Methode löscht standardmäßig das letzte Element einer Liste. Da wir jedoch das erste Element entfernen müssen, müssen wir den Index `0` übergeben.
class Queue:
# ...
def dequeue(self):
return self.elements.pop(0)
Das ist das Grundgerüst für eine Warteschlange. Aber wir brauchen noch Hilfsfunktionen, um zu testen, ob die Operationen korrekt funktionieren. Erweitern wir unsere Klasse um diese Methoden.
Schritt 5:
Die `rear()`-Methode dient dazu, das letzte Element der Warteschlange zurückzugeben. Hier hilft uns die negative Indizierung des Listendatentyps.
class Queue:
# ...
def rear(self):
return self.elements[-1]
Schritt 6:
Die `front()`-Methode gibt das erste Element der Warteschlange zurück. Wir können dies über den Listenindex abrufen.
class Queue:
# ...
def front(self):
return self.elements[0]
Schritt 7:
Mit der `is_empty()`-Methode können wir überprüfen, ob die Warteschlange leer ist. Dazu nutzen wir die Länge der Liste.
class Queue:
# ...
def is_empty(self):
return len(self.elements) == 0
So! Wir haben die grundlegende Implementierung einer Warteschlange abgeschlossen. Jetzt müssen wir ein Objekt erstellen, um die `Queue`-Klasse zu nutzen.
Machen wir das.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Wir haben nun ein `Queue`-Objekt. Testen wir es mit einigen Operationen.
- Überprüfen Sie mit der `is_empty()`-Methode, ob die Warteschlange leer ist. Das Ergebnis sollte `True` sein.
- Fügen Sie die Zahlen 1, 2, 3, 4 und 5 mithilfe der `enqueue()`-Methode zur Warteschlange hinzu.
- Die Methode `is_empty()` sollte nun `False` zurückgeben.
- Geben Sie das erste und das letzte Element der Warteschlange mithilfe der `front()`- und `rear()`-Methode aus.
- Entfernen Sie ein Element mithilfe der `dequeue()`-Methode aus der Warteschlange.
- Überprüfen Sie das erste Element erneut. Es sollte nun das Element 2 sein.
- Entfernen Sie nun alle Elemente aus der Warteschlange.
- Die `is_empty()`-Methode sollte nun `True` zurückgeben.
Das sollte ausreichend sein, um unsere Warteschlangenimplementierung zu testen. Schreiben Sie Code für jeden oben genannten Schritt, um die Warteschlange zu testen.
Haben Sie den Code geschrieben?
Wenn nicht, ist das kein Problem.
Hier ist der vollständige Code zum Überprüfen:
class Queue:
def __init__(self):
self.elements = []
def enqueue(self, data):
self.elements.append(data)
return data
def dequeue(self):
return self.elements.pop(0)
def rear(self):
return self.elements[-1]
def front(self):
return self.elements[0]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
queue = Queue()
## Überprüfen, ob die Warteschlange leer ist -> True
print(queue.is_empty())
## Hinzufügen von Elementen
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
## Überprüfen, ob die Warteschlange leer ist -> False
print(queue.is_empty())
## Ausgabe des ersten und letzten Elements -> 1, 5
print(queue.front(), end=' ')
print(queue.rear())
## Entfernen des ersten Elements -> 1
queue.dequeue()
## Ausgabe des ersten und letzten Elements -> 2 5
print(queue.front(), end=' ')
print(queue.rear())
## Entfernen aller Elemente
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()
## Überprüfen, ob die Warteschlange leer ist -> True
print(queue.is_empty())
Wenn Sie das obige Programm ausführen, sollte die Ausgabe in etwa so aussehen:
True False 1 5 2 5 True
Wir können den Listendatentyp direkt als Warteschlangendatenstruktur verwenden. Die obige Implementierung soll Ihnen jedoch helfen, die zugrunde liegenden Konzepte besser zu verstehen und sie in anderen Programmiersprachen anwenden zu können.
Sie können die oben erstellte `Queue`-Klasse auch in anderen Projekten verwenden, indem Sie einfach das Objekt wie gezeigt instanziieren.
Wir haben die Warteschlange mit dem Listendatentyp von Grund auf selbst implementiert. Gibt es auch bereits vorgefertigte Module für Warteschlangen? Ja! Sehen wir uns diese an.
#2. Deque aus der Collections-Bibliothek
Deque steht für „double-ended queue“ (doppelseitige Warteschlange). Da sie das Hinzufügen und Entfernen von Elementen von beiden Enden unterstützt, können wir sie sowohl als Stack als auch als Warteschlange verwenden. Wir konzentrieren uns hier auf die Nutzung als Warteschlange.
Die Implementierung basiert auf doppelt verketteten Listen. Die Leistung beim Einfügen und Löschen von Elementen ist somit konsistent. Der Zugriff auf Elemente in der Mitte einer solchen verketteten Liste benötigt jedoch O(n) Zeit. Für unsere Warteschlange, wo wir nicht auf mittlere Elemente zugreifen müssen, stellt das kein Problem dar.
Sehen wir uns die Methoden der Deque im Detail an:
- `append(data)` – fügt das Element am Ende der Warteschlange hinzu.
- `popleft()` – entfernt das erste Element der Warteschlange.
Es gibt keine direkten Alternativen für `front`, `rear` oder `is_empty`. Wir können jedoch die gesamte Warteschlange ausgeben. Um zu überprüfen, ob die Warteschlange leer ist, nutzen wir die Funktion `len()`.
Wir verwenden die gleichen Schritte wie bei der vorherigen Warteschlangenimplementierung, um den Code zu testen.
from collections import deque ## Erzeugen eines Deque-Objekts queue = deque() ## Überprüfen, ob die Warteschlange leer ist -> True print(len(queue) == 0) ## Hinzufügen von Elementen queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## Überprüfen, ob die Warteschlange leer ist -> False print(len(queue) == 0) ## Ausgabe der Warteschlange print(queue) ## Entfernen des ersten Elements -> 1 queue.popleft() ## Ausgabe der Warteschlange print(queue) ## Entfernen aller Elemente queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## Überprüfen, ob die Warteschlange leer ist -> True print(len(queue) == 0)
Die Ausgabe sollte in etwa so aussehen:
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Queue-Modul aus der Queue-Bibliothek
Python bietet ein integriertes Modul namens `queue`, das die `Queue`-Klasse zur Verfügung stellt. Die Funktionsweise ähnelt dem, was wir zuvor selbst implementiert haben.
Sehen wir uns die verschiedenen Methoden der `Queue`-Klasse an:
- `put(data)` – fügt ein Element zur Warteschlange hinzu.
- `get()` – entfernt und gibt das erste Element der Warteschlange zurück.
- `empty()` – gibt zurück, ob die Warteschlange leer ist.
- `qsize()` – gibt die Länge der Warteschlange zurück.
Hier ist eine Beispielimplementierung mit diesen Methoden:
from queue import Queue
## Erzeugen eines Queue-Objekts
queue_object = Queue()
## Überprüfen, ob die Warteschlange leer ist -> True
print(queue_object.empty())
## Hinzufügen von Elementen
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## Überprüfen, ob die Warteschlange leer ist -> False
print(queue_object.empty())
## Entfernen der Elemente
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## Ausgeben der Größe der Warteschlange
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## Überprüfen, ob die Warteschlange leer ist -> True
print(queue_object.empty())
Die Ausgabe sollte in etwa so aussehen:
True False 1 2 3 Size 2 4 5 True
Es gibt noch weitere Methoden in der `Queue`-Klasse, die Sie mit der integrierten `dir()`-Funktion erkunden können.
Fazit
Ich hoffe, Sie haben etwas über die Warteschlangendatenstruktur und ihre verschiedenen Implementierungen in Python gelernt. Das war es für die Warteschlange. Sie können diese überall dort einsetzen, wo eine FIFO-Verarbeitung benötigt wird. Denken Sie daran, sie einzusetzen, wenn ein solcher Anwendungsfall auftritt.
Sind Sie daran interessiert, Ihre Python-Kenntnisse zu vertiefen? Dann werfen Sie einen Blick auf diese Lernressourcen: Link zu Lernressourcen.
Viel Spaß beim Programmieren! 🙂 👨💻