Python-Algorithmen

Die Datenstruktur Warteschlange (queue) in Python

In dieser Lektion implementierst du mit collections.deque eine effiziente Warteschlange nach dem Prinzip zuerst hinein, zuerst heraus.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

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.

Von der Ticketschlange zum Code
deque(["first", "second"])🚶🚶 Zwei Leute warten schon
queue.append("third")🚶 Eine neue Person stellt sich hinten an
queue.popleft()🎫 Die Person vorne wird bedient
list(queue)👀 Wer noch wartet
First in, first out: Die Reihenfolge der Ankunft ist die Reihenfolge der Bedienung.
In einem Satz

Eine Queue (Warteschlange) ist eine First-in-first-out-Sammlung (FIFO): Elemente kommen hinten hinzu und werden vorne entfernt.

Das Wichtigste

  1. deque(["first", "second"]) erstellt eine Queue, die schon zwei Elemente enthält.
  2. queue.append("third") fügt hinten ein Element hinzu.
  3. queue.popleft() entfernt das vordere Element und gibt es zurück, hier "first".
  4. deque entfernt 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 heapq für eine Priority Queue.
  • Mehrere Threads teilen sich die Queue: queue.Queue kü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

Code ausführen →
main.py
from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))
Run-Button für dieses Beispiel erstellen

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.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

Eine Liste und pop(0) verwenden

pop(0) verschiebt jedes restliche Element, was bei langen Queues langsam wird.

Problem
queue = ["first", "second"]
queue.pop(0)
Lösung
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.

Alle Challenges