Warteschlangen und collections.deque
Fügen Sie an beiden Enden schnell Elemente ein und entfernen Sie sie
Warteschlangen und collections.deque ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
First In, First Out
Eine Queue verarbeitet Elemente in der Reihenfolge ihres Eintreffens, wie eine Warteschlange im Geschäft. Das zuerst eingefügte Element wird zuerst entfernt.
Warum keine Liste verwenden
Eine Liste kann am Anfang Elemente entfernen, aber pop(0) benötigt O(n), weil alle anderen Elemente nach links verschoben werden. Für große Eingaben ist das zu langsam.
q = []
q.pop(0) # O(n), avoid thiscollections.deque kennenlernen
Die deque aus collections ist eine doppelseitige Queue, die an beiden Enden in O(1) Zeit Elemente einfügt und entfernt. Sie ist die erste Wahl bei Programmierwettbewerben.
from collections import deque
q = deque()Hinten einreihen
Fügen Sie neue Elemente mit append am rechten Ende ein, genau wie bei einer Liste. Das ist das Ende der Queue.
q.append(1)
q.append(2)Vorne entfernen
Entfernen Sie das älteste Element mit popleft von der linken Seite. Das läuft in konstanter Zeit und liefert echtes FIFO-Verhalten.
first = q.popleft() # returns 1Beide Enden sind offen
Eine deque unterstützt außerdem appendleft und das Entfernen mit pop von rechts. Diese Flexibilität ermöglicht es, dieselbe Struktur als Stack oder Queue zu verwenden.
q.appendleft(0)
last = q.pop()Vor dem Entfernen prüfen
Das Entfernen aus einer leeren deque löst einen Fehler aus. Prüfen Sie daher in Schleifen mit while q, ob Elemente vorhanden sind, damit Ihr Durchlauf sicher bleibt.
while q:
x = q.popleft()Queues treiben BFS an
Die häufigste Verwendung bei Programmierwettbewerben ist BFS. Sie fügen einen Startknoten ein, entfernen dann immer das vorderste Element und fügen dessen Nachbarn hinzu.
Ein kleines BFS-Grundgerüst
Diese Schleife besucht Knoten schichtweise. Jeder Nachbar wird angehängt und später in der Reihenfolge seines Eintreffens verarbeitet.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Die Größe der deque begrenzen
Mit maxlen wird beim Erreichen der maximalen Größe das älteste Element aus einer deque entfernt. Das ist ideal für gleitende Fenster und die Verfolgung der jüngsten Historie.
window = deque(maxlen=3)Eine Struktur, viele Rollen
Denken Sie daran, dass deque an beiden Enden schnell ist. Verwenden Sie sie daher für eine Queue, einen Stack oder einen gleitenden Puffer.
Kurzprüfung
Sie benötigen schnelles Entfernen am Anfang einer Queue. Welche Wahl ist richtig?
Zusammenfassung: Deque ist die schnelle Queue
Sie haben collections.deque kennengelernt: append und popleft für O(1)-FIFO, Zugriff an beiden Enden und maxlen für Fenster. Sie bildet das Rückgrat von BFS. 🎯
Häufig gestellte Fragen
Ist die Lektion „Warteschlangen und collections.deque“ kostenlos?
Ja — der vollständige Text von „Warteschlangen und collections.deque“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Warteschlangen und collections.deque“?
Fügen Sie an beiden Enden schnell Elemente ein und entfernen Sie sie Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Warteschlangen und collections.deque“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Stapel zum Abgleichen von Klammern
- Monotoner Stapel: nächstgrößeres Element
- Warteschlangen und collections.deque
- Maximum im Sliding Window mit Deque