Warteschlangenimplementierung und Deque
Erstellen Sie eine Warteschlange mit Pythons deque, implementieren Sie eine zirkuläre Warteschlange und lösen Sie das Maximum eines Sliding Windows mit einer monotonen Deque.
Warteschlangenimplementierung und Deque ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die Queue-Datenstruktur
Eine Queue ist eine Datenstruktur nach dem Prinzip „first in, first out“ (FIFO). Das zuerst eingereihte Element wird als Erstes entfernt – wie in einer Warteschlange an der Kasse. Die grundlegenden Operationen sind enqueue (am Ende hinzufügen) und dequeue (am Anfang entfernen). Beide müssen O(1) benötigen, damit die Queue effizient ist.
Eine Python-Liste als Queue zu verwenden, ist verlockend, aber falsch: list.pop(0) benötigt O(n), weil alle Elemente verschoben werden. Das richtige Werkzeug ist collections.deque, das O(1) für appendleft, append, popleft und pop bietet.
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Queue-Klasse mit deque
Kapseln Sie deque in eine Queue-Klasse mit benannten Operationen, wie es Interviewer erwarten. Intern ruft enqueue append auf und dequeue ruft popleft auf. Die Operation peek liest queue[0], ohne das Element zu entfernen.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2BFS mit einer Queue
Die klassische Anwendung einer Queue ist die Breitensuche (Breadth-First Search, BFS). Fügen Sie die Wurzel zur Queue hinzu. Solange die Queue nicht leer ist, entfernen Sie einen Knoten, verarbeiten ihn und fügen seine noch nicht besuchten Nachbarn hinzu. Da die Knoten ebenenweise verarbeitet werden, findet BFS in einem ungewichteten Graphen auf natürliche Weise den kürzesten Pfad. Die Queue enthält immer Knoten aus höchstens zwei benachbarten Ebenen.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Zirkuläre Queue (LeetCode 622)
LeetCode 622 'Design Circular Queue': Implementieren Sie eine Queue mit fester Kapazität, die zyklisch wieder zum Anfang springt. Verwenden Sie ein Array der Größe k und zwei Zeiger: head und tail. Fügen Sie am tail ein, entfernen Sie am head und berechnen Sie Positionen modulo k. Eine Variable count unterscheidet zwischen voll und leer (andernfalls gilt für beide Fälle head == tail modulo k).
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueMaximum im gleitenden Fenster mit monotoner Deque
LeetCode 239 'Sliding Window Maximum': Finden Sie für jedes Fenster der Größe k das größte Element. Der Brute-Force-Ansatz benötigt O(n*k). Der O(n)-Ansatz verwendet eine monoton fallende Deque, die Indizes speichert. Für jedes neue Element: Entfernen Sie am Anfang Indizes, die außerhalb des Fensters liegen, und am Ende Indizes mit kleineren Werten (sie können in keinem zukünftigen Fenster mehr das Maximum sein). Am Anfang steht immer das Maximum.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Warum eine Deque statt nur einer Liste für eine Queue?
Python's list.pop(0) entfernt das erste Element in O(n), weil jedes verbleibende Element um eine Position nach links verschoben werden muss. Bei n Einfügungen und n Löschungen ergibt sich dadurch insgesamt O(n²). collections.deque ist eine doppelt verkettete Liste aus Blöcken fester Größe. popleft benötigt O(1), weil dabei nur ein Zeiger angepasst wird. Bei einer BFS auf einem Graphen mit 10^5 Knoten ist der Unterschied zwischen O(n) und O(n²) der Unterschied zwischen 100 ms und 100 Sekunden.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')Level-Order-Traversierung eines Binärbaums (LeetCode 102)
LeetCode 102 'Binary Tree Level Order Traversal': Geben Sie alle Knotenwerte ebenenweise zurück. Verwenden Sie eine Queue. Erfassen Sie zu Beginn jeder Ebene die Größe der Queue (sie gibt an, wie viele Knoten sich auf dieser Ebene befinden). Entfernen Sie genau diese Anzahl an Knoten, sammeln Sie ihre Werte und fügen Sie ihre Kinder zur Queue hinzu. Wiederholen Sie dies, bis die Queue leer ist.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]Prioritätswarteschlange mit heapq
Das Python-Modul heapq stellt einen Min-Heap (eine Prioritätswarteschlange) bereit: Das kleinste Element wird immer zuerst aus der Warteschlange entfernt. heapq.heappush(h, item) fügt ein Element in O(log n) hinzu, und heapq.heappop(h) entfernt das Minimum in O(log n). Für Aufgaben wie den Dijkstra-Algorithmus und Top-k-Probleme ersetzt heapq die einfache Warteschlange.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Tapetenmuster: Warteschlange für Word Ladder
LeetCode 127 „Word Ladder“: Finden Sie die minimale Anzahl einzelner Zeichenersetzungen, um ein Wort in ein anderes umzuwandeln, wobei nur Wörter aus dem Wörterbuch verwendet werden. Modellieren Sie das Problem als Graphen, in dem Kanten Wörter verbinden, die sich in genau einem Zeichen unterscheiden. BFS auf diesem Graphen findet den kürzesten Pfad (die minimale Anzahl an Schritten) in O(n * L²), wobei n die Größe des Wörterbuchs und L die Wortlänge ist.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5deque als doppelseitige Warteschlange
collections.deque ist eine doppelseitige Warteschlange (Deque): Sie können an beiden Enden effizient Elemente hinzufügen und entfernen. Methoden: appendleft und popleft für den Anfang; append und pop für das Ende. Dadurch kann deque sowohl als FIFO-Warteschlange (appendright + popleft) als auch als LIFO-Stack (append + pop) dienen. Das Maximum eines gleitenden Fensters verwendet beide Enden: Entfernen Sie alte Indizes von links und kleinere Werte von rechts.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Zusammenfassung: Warteschlange vs. Deque vs. Heap
Wählen Sie das richtige Werkzeug für das Problem. Verwenden Sie eine einfache Warteschlange (deque) für FIFO-Verarbeitung und BFS. Verwenden Sie eine monotone Deque, wenn Sie das Maximum oder Minimum eines gleitenden Fensters benötigen — sie bewahrt eine sortierte Invariante, indem sie dominierte Elemente entfernt. Verwenden Sie eine Prioritätswarteschlange (heapq), wenn Sie unabhängig von der Reihenfolge das globale Minimum oder Maximum benötigen, etwa beim Dijkstra-Algorithmus oder bei Top-k-Problemen. Zu wissen, welches Werkzeug Sie wann einsetzen und warum, ist eine wichtige Fähigkeit, die in Interviews geprüft wird.
Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: collections.deque bietet O(1)-Operationen zum Einfügen und Entfernen und ist damit die richtige Implementierung einer Warteschlange in Python, BFS verwendet eine Warteschlange, um Knoten Ebene für Ebene zu verarbeiten und kürzeste Pfade in ungewichteten Graphen zu finden und eine monoton absteigende Deque löst das Maximum eines gleitenden Fensters in O(n), indem sie dominierte Indizes entfernt. Als Nächstes sehen wir uns das Muster des monotonen Stacks im Detail an.
Häufig gestellte Fragen
Ist die Lektion „Warteschlangenimplementierung und Deque“ kostenlos?
Ja — der vollständige Text von „Warteschlangenimplementierung und 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 DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Warteschlangenimplementierung und Deque“?
Erstellen Sie eine Warteschlange mit Pythons deque, implementieren Sie eine zirkuläre Warteschlange und lösen Sie das Maximum eines Sliding Windows mit einer monotonen Deque. Du übst DSA Interview Prep 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 DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep 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 2 von 4.
Wie lange dauert die Lektion „Warteschlangenimplementierung und 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 DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-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
- Stapelimplementierung und Anwendungen
- Warteschlangenimplementierung und Deque
- Muster des monotonen Stapels
- Gegenseitige Simulation von Stapel und Warteschlange