Die Datenstruktur Warteschlange (queue) in Python
In dieser Lektion implementierst du mit collections.deque eine effiziente Warteschlange nach dem Prinzip zuerst hinein, zuerst heraus.
Einführung
Das Problem
Druckaufträge, Support-Tickets und Nachrichten zwischen Programmen müssen in der Reihenfolge ihres Eintreffens bearbeitet werden. Eine Queue hält diese Reihenfolge ein, und das richtige Werkzeug in Python hält sie auch bei Millionen von Elementen schnell.
Stell es dir so vor
Eine Queue ist wie eine Schlange am Ticketschalter. Neue Leute stellen sich hinten an, und wer vorne steht, wird zuerst bedient. Niemand drängelt sich vor, also wird jeder in der Reihenfolge seiner Ankunft bedient.
deque(["first", "second"])🚶🚶 Zwei Leute warten schonqueue.append("third")🚶 Eine neue Person stellt sich hinten anqueue.popleft()🎫 Die Person vorne wird bedientlist(queue)👀 Wer noch wartetEine Queue (Warteschlange) ist eine First-in-first-out-Sammlung (FIFO): Elemente kommen hinten hinzu und werden vorne entfernt.
Das Wichtigste
deque(["first", "second"])erstellt eine Queue, die schon zwei Elemente enthält.queue.append("third")fügt hinten ein Element hinzu.queue.popleft()entfernt das vordere Element und gibt es zurück, hier"first".dequeentfernt vorne schnell; eine Liste müsste jedes restliche Element verschieben.
Wann verwendet man das?
- Aufgaben oder Anfragen in der Reihenfolge ihres Eintreffens verarbeiten.
- Breitensuche in Graphen und Gittern.
- Puffer zwischen Erzeugern und Verbrauchern, etwa für Nachrichten oder Events.
Wann du es nicht brauchst
- Das neueste Element soll zuerst heraus: Nimm einen Stack.
- Elemente haben Prioritäten: Nimm
heapqfür eine Priority Queue. - Mehrere Threads teilen sich die Queue:
queue.Queuekümmert sich um das Locking.
So funktioniert es
Mit enqueue und dequeue siehst du, dass die Elemente in derselben Reihenfolge gehen, in der sie gekommen sind.
Beispielcode
from collections import deque
queue = deque(["first", "second"])
queue.append("third")
print("served:", queue.popleft())
print("waiting:", list(queue))
Ergebnis der Ausführung
served: first
waiting: ['second', 'third']
Erklärung des Codes
Mit deque fügst du rechts mit append() Elemente hinzu und entnimmst sie links mit popleft(), beides in O(1). Bei einer normalen Liste kostet das Entfernen des ersten Elements O(n), weil alle folgenden Elemente nachrücken müssen, deshalb ist deque die richtige Wahl für Warteschlangen.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungen zur Vertiefung
Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Eine Liste und pop(0) verwenden
pop(0) verschiebt jedes restliche Element, was bei langen Queues langsam wird.
queue = ["first", "second"]
queue.pop(0)
queue = deque(["first", "second"])
queue.popleft()
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
- Course Schedule Order Order courses so every prerequisite comes first. Schwierig
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Mittel