Warteschlangenimplementierung in Python

Eine Warteschlange speichert Elemente in der Reihenfolge First In, First Out (FIFO): Jedes neue Element kommt hinten hinzu, und das vorderste Element wird als Nächstes entfernt. In Python lässt sich dieses Verhalten auf verschiedene Arten abbilden. Dieser Leitfaden implementiert eine Warteschlange mit einer Liste und einer verketteten Liste und zeigt anschließend die Option aus der Standardbibliothek collections.deque.

Verhalten und grundlegende Operationen einer Warteschlange

Vorne steht das Element, das als Nächstes entfernt wird; hinten werden neue Elemente angefügt. Enthält eine Warteschlange beispielsweise 1, 2, 3, steht 1 vorne und 3 hinten. Wird 4 eingereiht, ergibt sich 1, 2, 3, 4; ein Entfernen gibt 1 zurück und lässt 2, 3, 4 übrig.

Die folgende kurze, ausführbare Sequenz fügt Elemente hinten an und entfernt sie vorne. Das bereitgestellte Paket enthält keine Laufzeitbeobachtung für dieses Beispiel; daher wird keine Ausgabe behauptet.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

queue = []
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
removed = queue.pop(0)
print(removed)
print(queue)

Eine praktische Warteschlangenschnittstelle bietet vier Operationen: Einreihen fügt ein Element hinzu, Entfernen nimmt das vorderste Element heraus und gibt es zurück, eine Leerheitsprüfung meldet, ob noch Elemente vorhanden sind, und die Längenabfrage gibt ihre Anzahl an. Die folgenden Implementierungen geben beim Entfernen aus einer leeren Warteschlange (False, None) und bei Erfolg (True, item) zurück. Das Erfolgskennzeichen unterscheidet ein tatsächlich gespeichertes None von einer leeren Warteschlange.

Eine Warteschlange mit einer Python-Liste implementieren

Eine Liste eignet sich als kompaktes Lehrbeispiel. Fügen Sie Elemente mit append() am Ende an und entfernen Sie das erste Element mit pop(0). Der Code bleibt dadurch einfach, aber beim Entfernen vorne werden die übrigen Elemente verschoben. Deshalb benötigt das Entfernen mit wachsender Warteschlange lineare Zeit. Das Beispiel unterstützt beliebige Python-Objekte, einschließlich None.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

class ListQueue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.items:
            return False, None
        return True, self.items.pop(0)

    def is_empty(self):
        return len(self.items) == 0

    def __len__(self):
        return len(self.items)


queue = ListQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

Eine Liste mit Kopfindex kann das Verschieben bei jeder Entfernung vermeiden, behält aber entfernte Einträge, bis die Liste verdichtet wird. Dafür ist zusätzliche Buchführung nötig, um logische Warteschlangenpositionen auf Listenindizes abzubilden und den Speicher sicher zurückzusetzen oder zu verdichten. Für den allgemeinen Einsatz von FIFO ist collections.deque meist die klarere Wahl. Die Zeichenketten first und second in der unveränderten Beispielausgabe bleiben auf Englisch.

Eine Warteschlange mit einer verketteten Liste implementieren

Bei einer einfach verketteten Warteschlange speichert jeder Knoten ein Element; seine next-Referenz weist in Richtung des hinteren Endes. Speichern Sie Referenzen auf beide Enden: Beim Einreihen wird ein neuer Knoten an rear angehängt, beim Entfernen rückt front weiter. Wird der letzte Knoten entfernt, muss auch rear auf None gesetzt werden. Andernfalls könnte das nächste Einreihen versuchen, über einen veralteten Knoten anzufügen. Einreihen und Entfernen benötigen konstante Zeit. Die Längenabfrage benötigt in diesem Beispiel lineare Zeit, weil dafür die Knoten gezählt werden.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        node = Node(item)
        if self.rear is None:
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node

    def dequeue(self):
        if self.front is None:
            return False, None
        item = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return True, item

    def is_empty(self):
        return self.front is None

    def __len__(self):
        count = 0
        current = self.front
        while current is not None:
            count += 1
            current = current.next
        return count


queue = LinkedQueue()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

Die Invariante lautet: Genau dann, wenn die Warteschlange leer ist, sind beide Referenzen None. Bei einer nicht leeren Warteschlange verweist front auf das nächste zu entfernende Element und rear.next ist None. Wird diese Invariante eingehalten, funktionieren sowohl Warteschlangen mit nur einem Element als auch die erneute Verwendung nach dem Leeren.

collections.deque als Warteschlange verwenden

Für gewöhnliche FIFO-Aufgaben ist Pythons collections.deque die praktische Standardwahl. Fügen Sie Elemente rechts mit append() an und entfernen Sie sie links mit popleft(). Beide Operationen an den Enden sind auf Effizienz ausgelegt. Mit len() und einer Wahrheitswertprüfung bleibt die übrige Schnittstelle knapp. Wird popleft() für eine leere Deque aufgerufen, entsteht ein IndexError. Dieser Wrapper prüft deshalb vorher, ob die Deque leer ist, und verwendet dasselbe Ergebnisformat mit Erfolgskennzeichen wie die anderen Beispiele. Die Zeichenketten first und second in der unveränderten Beispielausgabe bleiben auf Englisch.

from collections import deque


class DequeQueue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.items:
            return False, None
        return True, self.items.popleft()

    def is_empty(self):
        return not self.items

    def __len__(self):
        return len(self.items)


queue = DequeQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

deque ist eine Klasse aus dem Modul collections. Entscheidend ist hier ihre öffentliche Schnittstelle; verlassen Sie sich nicht auf Annahmen über ihre interne Darstellung. Wenn Sie eine begrenzte Kapazität oder die Koordination zwischen Erzeuger- und Verbraucherthreads benötigen, ziehen Sie stattdessen die dafür vorgesehenen Warteschlangenklassen aus Pythons Modul queue in Betracht.

Die Implementierungen vergleichen

Die Laufzeitangaben für die verkettete Liste setzen voraus, dass die Warteschlange sowohl front als auch rear speichert. Ihre Länge zu bestimmen, durchläuft dennoch alle Knoten, weil kein Zähler geführt wird. Ein eigener Zähler könnte die Längenabfrage auf konstante Zeit verkürzen, würde aber eine zusätzliche Invariante erfordern, die bei jeder Operation aktualisiert werden muss. Für die meisten Programme ist collections.deque die passende Wahl. Verwenden Sie eine Liste, wenn die Warteschlange sehr klein ist oder Elemente nicht wiederholt vorne entfernt werden. Eine verkettete Liste eignet sich, wenn Sie die Datenstruktur lernen oder gezielt ihr Verhalten auf Knotenebene untersuchen möchten.