Python Queue: So erstellst du eine Warteschlange in Python

Einführung

Daten sind ein wichtiger Bestandteil der Programmierung. Deshalb ist es nötig, die Daten auf geeignete Art und Weise zu verwalten. Dabei werden bestimmte Datenstrukturen verwendet, um den Umgang mit den Daten effizienter zu gestalten. Es gibt zahlreiche Möglichkeiten von Datenstrukturen, die in der Programmierung verwendet werden. Beispiele dafür sind die List, das Stack, die Queue und der Tree.
Eine Python Queue ist eine einfache, aber effiziente Datenstruktur. In Python gibt es einige verschiedene Möglichkeiten, um ein Queue zu implementieren. In diesem Artikel werden wir alles über die Python Queue kennenlernen.

Die Python Queue

Die Queue ist eine lineare Datenstruktur, in der die Daten nach dem FIFO-Prinzip verwaltet werden (aus dem Englischen: First-In-First-Out). Wie die Bezeichnung suggeriert, wird das zuerst eingefügte Element auch wieder als erstes entfernt. Es kann kein anderes Element entfernt werden.

Lasst uns dafür ein Beispiel aus dem Alltag betrachten. Stellen wir uns dafür eine Schlange von Personen vor einem Bankautomaten vor. Die erste Person in der Schlange wird zunächst Geld abheben. Danach wird Sie die Schlange verlassen. Dann wird die zweite Person zum Geldautomaten gehen, Geld abheben und im Anschluss die Schlange verlassen. Diese Prozedur wiederholt sich, bis die Schlange leer ist. Genauso funktioniert eine Queue als Datenstruktur.

Python Queue Operationen und Bedingungen

Bevor wir uns die Implementierung der Queue anschauen, müssen wir die grundlegenden Bedingungen und Operationen der Queue verstehen.

1. Enqueue: Die enqueue-Funktion fügt ein Element am Ende der Queue ein
2. Dequeue: Die Funktion löscht ein Element aus der Queue. Das gelöschte Element ist dabei immer das erste in der Queue
3. Overflow: Die Overflow-Bedingung zeigt an, ob die Queue Elemente hält. Sie wird in der enqueue-Funktion verwendet.
4. Underflow: Die Underflow-Bedingung zeigt an, ob die Queue leer ist. Sie wird in der dequeue-Funktion verwendet.
5. Front: Die Front-Funktion gibt das erste Element in der Queue zurück.
6. Rear: Die Rear-Funktion gibt das letzte Element in der Queue zurück.

Drei Wege, um eine Python Queue zu erstellen

Es gibt drei verschiedene Wege, um eine Queue zu implementieren. Im Folgenden werden wir alle Möglichkeiten einzeln näher begutachten und besprechen.

Die Python Liste

Die Python Liste ist eine integrierte Sammlung und gehört ihrerseits sogar zu den am meisten genutzten Sammlungen in Python. Die Liste bietet zahlreiche integrierte Funktionen, die es einfach machen, Operationen durchzuführen. Die Queue mittels der List zu implementieren, ist der einfachste Weg.

Starten wir mit dem Erstellen einer leeren Queue.

q = []

Grundsätzlich ist „q“ eine List. Wir nutzen sie allerdings als Queue.

Um ein Element hinzuzufügen nutzen wir die append()-Funktion. Damit implementieren wir die Enqueue-Operation, bei der ein Element an das Ende der Queue hinzugefügt wird.

def enqueue(x):
	q.append(x)

q = []
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
enqueue(5)

Die enqueue()-Funktion wird die Enqueue-Operation durchführen. Dabei fügen wir im Code einige Elemente in die Queue ein.

Im Umkehrschluss können wir die pop()-Funktion nutzen. Diese implementiert die Dequeue-Operation.

def enqueue(x):
	q.append(x)

def dequeue():
	q.pop(0)

q = []
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
enqueue(5)
dequeue()
dequeue()

In der dequeue()-Funktion beim Aufruf der pop()-Funktion müssen wir eine 0 übergeben, um das erste Element der List bzw. Queue zu löschen.

Die Dequeue-Operation wird jetzt zweimal ausgeführt. Also sollten aus unserer Queue zwei Elemente wieder gelöscht werden.

Jetzt können wir noch die front()- und rear()-Funktion implementieren um das erste und letzte Element ausgeben zu können.

def enqueue(x):
	q.append(x)

def dequeue():
	q.pop(0)

def front():
	return q[0]

def rear():
	i = len(q) - 1
	return q[i]

q = []
enqueue(1)
enqueue(2)
enqueue(3)
front()
rear()

Jetzt haben wir zwei neue Funktionen. Die front()-Funktion für die Front-Operation und die rear()-Funktion für die Rear-Operation.

In der front()-Funktion wird das erste Element der Queue zurückgegeben. In der rear()-Funktion wiederrum wird die len()-Funktion verwendet um über den Index das letzte Element zu adressieren.

Also erhalten wir bei der front()-Funktion der Wert 1, während wir bei der rear()-Funktion der Wert 3 erhalten.

Verwenden wir im selben Zusammenhang noch einmal die Dequeue-Operation und rufen dann erneut die front()-Funktion auf.

Wie wir sehen, funktioniert unsere Queue einwandfrei.

Das collections.deque Modul

Die zweite Möglichkeit ist mehr oder weniger sehr ähnlich zur ersten Methode. Allerdings wird statt der Python List die deque Klasse aus dem Python Collection-Modul verwendet. Der größte Unterschied ist dabei die Zeitkomplexität.

Die Zeitkomplexität der deque-Klasse in der O-Notation ist O(1). Die Komplexität der List wiederrum ist O(n)., was bedeutet, dass die deque-Klasse Operation innerhalb der Datenstruktur deutlich schneller ausführt als die List. Dies ist besonders bei großen Datenstrukturen wichtig.

Starten wir zunächst mit dem Erstellen der Queue:

from collections import deque
q = deque()

Als erstes müssen wir die deque-Klasse aus dem Collection-Modul importieren. Dann können wir diese nutzen, um unsere Queue zu initialisieren. Als nächstes implementieren wir die Enqueue-Operation, indem wir die append()-Funktion der Klasse nutzen.

Die append()-Funktion der deque-Klasse arbeitet gleich wie die der Python List.

Für die Dequeue-Operation können wir die popleft()-Funktion der deque-Klasse nutzen.

from collections import deque
def enqueue(x):
	q.append(x)

def dequeue():
	q.popleft()

q = deque()
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
enqueue(5)
dequeue()
dequeue()

Auch die popleft()-Funktion funktioniert ähnlich zur pop()-Funktion der Python List. Allerdings müssen wie hier keine = als Parameter übergeben.

Das Python queue.Queue Modul

Diese Herangehensweise ist die gradlinigste Möglichkeit, die Queue in Python zu implementieren. Das queue-Modul ist ein integriertes Modul, das speziell für das Erstellen einer Queue in Python existiert. Es hält mehrere Funktionen, die auf verschiedene Weise nützlich sind.

Starten wir erneut mit dem Erstellen einer leeren Queue mit dem queue-Modul.

from queue import Queue 
q = Queue(maxsize = 5)

Ein Vorteil beim Verwenden dieser Funktion ist die Begrenzung der maximalen Größe der Queue. Dabei übergeben wir der Funktion die maximale Größe, in unserem Fall fünf.

Um Elemente der Queue hinzuzufügen, nutzen wir die put()-Funktion

from queue import Queue 
def enqueue(x):
	q.put(x)

q = Queue(maxsize = 5)
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
enqueue(5)

Auch die put()-Funktion des Moduls arbeitet gleich zu den vorherigen Ansätzen mit der append()-Funktion.

Die Abfrage des Objektes gibt uns ein queue-Objekt zurück.

Wir können außerdem die Größe der Queue abfragen. Dazu nutzen wir die qsize()-Funktion.

from queue import Queue 
def enqueue(x):
	q.put(x)

q = Queue(maxsize = 5)
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
enqueue(5)
q.qsize()

Um die Dequeue-Operation umzusetzen, nutzen wir die get()-Funktion des Moduls.

from queue import Queue 
def enqueue(x):
	q.put(x)

def dequeue():
	q.get()

q = Queue(maxsize = 5)
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
enqueue(5)
q.qsize()
dequeue()
dequeue()
q.qsize()

Ein Python Queue mit individuellen Prioritäten

Eine Queue mit Prioritäten ist eine höhere Variante der normalen Queue. Sie bildet also eine Art Erweiterung der normalen Funktion der Queue. Die Elemente werden dabei beim Entfernen auf Basis ihrer Priorität bearbeitet.

Jedes Element, das in eine Queue mit Prioritäten hinzugefügt wird, erhält eine eigene Nummer. Das Element mit der niedrigsten Nummer, also bildlich mit der niedrigsten Priorität, wird in der Queue als erstes gelöscht. Grundsätzlich wird dabei also das bekannte FIFO-Prinzip übergangen.

Eine Queue mit Priorität kann mittels der PriorityQueue-Klasse aus dem queue-Modul realisiert werden.

from queue import PriorityQueue
q = PriorityQueue()

Jetzt haben wir eine Queue mit Priorität initialisiert.

Um Elemente hinzuzufügen, nutzen wir wie zuvor die put()-Funktion. Allerdings müssen wir bei der PriorityQueue-Klasse einen Unterschied zur Queue-Klasse beachten. Die Elemente müssen mit einer Prioritätsnummer übergeben werden.

from queue import PriorityQueue
def enqueue(p, x):
	q.put(p, x)

q = PriorityQueue()
enqueue(3, 'a')
enqueue(1, 'b')
enqueue(4, 'c')
enqueue(5, 'd')
enqueue(2, 'e')

Die put()-Funktion akzeptiert zwei Parameter. Zum einen die Priorität und zum zweiten das hinzuzufügende Element.

Jetzt wollen wir noch die Dequeue-Operation implementieren. Auch hier können wir wieder die put()-Funktion verwenden.

from queue import PriorityQueue
def enqueue(p, x):
	q.put(p, x)

def dequeue():
	print(q.get())

q = PriorityQueue()

enqueue(3, 'a')
enqueue(1, 'b')
enqueue(4, 'c')
enqueue(5, 'd')
enqueue(2, 'e')
q.qsize()
dequeue()
dequeue()

Betrachten wir die Dequeue-Operation. Das erste Element in der Queue ist das „a“ mit der Priorität 3. In einer normalen Queue sollte das „a“ als erstes entfernt werden, da nach dem FIFO-Prinzip das erste Element als erstes gelöscht werden muss. Dies gilt so allerdings nicht zwingend für die Queue mit individueller Priorität. Im Folgenden Beispiel können wir das schnell erkennen.

Die get()-Funktion gibt die Priorität des gelöschten Elements zurück. Als erstes gibt es 1 zurück, da „b“ gelöscht wurde. Im zweiten Aufruf wird 2 ausgegeben, da „e“ entfernt wurde.

So funktioniert die Queue mit Priorität.

Zusammenfassung

In diesem Artikel haben wir drei Möglichkeiten kennengelernt, wie wir eine Queue in Python umsetzen können. Die einfachste Möglichkeit ist der Weg über die Python List. Die schnellere Variante arbeitet mit der deque-Klasse aus dem collections-Modul oder der Queue-Klasse aus dem queue-Modul. Dabei müssen wir selber entscheiden, welche der Varianten die geeignete für unsere Anwendung ist und wie wir diese implementieren. Die deque- Und Queue-Klasse bieten mehr Funktionen, wohingegen die List ihrerseits deutlich einfacher umzusetzen ist. Außerdem haben wir die Queue mit individuellen Prioritäten kennengelernt.