Python Deque: Schnelle doppelseitige Warteschlangen mit collections.deque

Name

Soren Atelier

Updated on 10.2.2026

Eine Python-Liste als Warteschlange oder Stack zu verwenden erscheint natürlich -- bis man beginnt, vom linken Ende zu entfernen. Der Aufruf von list.pop(0) ist eine O(n)-Operation, da jedes verbleibende Element eine Position nach vorne verschoben werden muss. In einer Schleife, die Millionen von Elementen verarbeitet, verwandelt diese versteckte Kosten eine schnelle Pipeline in ein Schneckentempo. Das gleiche Problem betrifft list.insert(0, x), das ebenfalls O(n) ist. Für jede Aufgabe, die beide Enden einer Sequenz berührt, werden einfache Listen zur Leistungsfalle.

Pythons collections.deque (doppelseitige Warteschlange, ausgesprochen "Deck") löst dies durch O(1) Append- und Pop-Operationen von beiden Enden. Sie ist als doppelt verkettete Liste fester Blockgrößen implementiert und bietet konstante Zeitperformance an jedem Ende bei gleichzeitiger Unterstützung von indiziertem Zugriff. Dieser Leitfaden behandelt alles, was Sie über deque wissen müssen: Erstellung, Kernoperationen, begrenzte Warteschlangen, Thread-Sicherheit und praktische Muster.

Eine Deque erstellen

from collections import deque
 
# Aus einer Liste
d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])
 
# Aus einem String
letters = deque("hello")
print(letters)  # deque(['h', 'e', 'l', 'l', 'o'])
 
# Leere Deque
d = deque()
 
# Mit maxlen (begrenzte Deque)
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)  # Hinzufügen rechts entfernt linkestes Element
print(d)  # deque([2, 3, 4], maxlen=3)

Kernoperationen

Deque bietet symmetrische Operationen für beide Enden der Sequenz.

from collections import deque
 
d = deque([2, 3, 4])
 
# append und appendleft
d.append(5)        # Am rechten Ende hinzufügen
d.appendleft(1)    # Am linken Ende hinzufügen
print(d)  # deque([1, 2, 3, 4, 5])
 
# pop und popleft
right = d.pop()       # Vom rechten Ende entfernen
left = d.popleft()    # Vom linken Ende entfernen
print(right)  # 5
print(left)   # 1
 
# extend und extendleft
d = deque([3, 4, 5])
d.extend([6, 7, 8])        # Mehrere Elemente rechts hinzufügen
d.extendleft([2, 1, 0])    # Links hinzufügen (beachten: umgekehrte Reihenfolge)
print(d)  # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

Beachten Sie, dass extendleft Elemente einzeln verarbeitet und jedes an Position 0 einfügt. Die resultierende Reihenfolge ist im Vergleich zum Eingabe-Iterable umgekehrt.

Weitere nützliche Methoden

from collections import deque
 
d = deque([1, 2, 3, 2, 4, 2, 5])
 
print(d.count(2))   # 3
print(d.index(3))   # 2
d.remove(2)          # Erstes Vorkommen entfernen
d.insert(1, 99)      # An Position einfügen
d.reverse()          # An Ort und Stelle umkehren
d.clear()            # Alle Elemente löschen

Rotation mit rotate()

Die Methode rotate() rotiert die Deque um n Schritte nach rechts. Negatives n rotiert nach links.

from collections import deque
 
d = deque([1, 2, 3, 4, 5])
 
d.rotate(2)    # 2 Schritte nach rechts rotieren
print(d)       # deque([4, 5, 1, 2, 3])
 
d.rotate(-3)   # 3 Schritte nach links rotieren
print(d)       # deque([2, 3, 4, 5, 1])

Begrenzte Deques mit maxlen

Begrenzte Deques sind eine der praktischsten Funktionen. Durch Setzen von maxlen erstellen Sie einen Puffer fester Größe, der automatisch die ältesten Elemente entfernt, wenn die Kapazität erreicht ist.

Gleitendes Fenster / Gleitender Durchschnitt

from collections import deque
 
def moving_average(data, window_size):
    """Calculate moving average using a bounded deque."""
    window = deque(maxlen=window_size)
    averages = []
    for value in data:
        window.append(value)
        if len(window) == window_size:
            averages.append(sum(window) / window_size)
    return averages
 
prices = [100, 102, 104, 103, 105, 107, 106, 108, 110, 109]
print(moving_average(prices, 3))
# [102.0, 103.0, 104.0, 105.0, 106.0, 107.0, 108.0, 109.0]

Ende einer Datei (Letzte N Zeilen)

from collections import deque
 
def tail(filename, n=10):
    """Return the last n lines of a file."""
    with open(filename) as f:
        return deque(f, maxlen=n)

Dies ist bemerkenswert effizient. Die begrenzte Deque liest die gesamte Datei, behält aber nur die letzten n Zeilen im Speicher.

Deque als Warteschlange (FIFO)

Verwenden Sie append() zum Einreihen und popleft() zum Ausreihen:

from collections import deque
 
queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")
 
print(queue.popleft())    # first
print(queue.popleft())    # second
print(queue.popleft())    # third

Hier zeigt deque seine wahre Stärke gegenüber einer Liste. Mit einer Liste ist list.pop(0) O(n). Mit deque ist popleft() O(1).

Deque als Stack (LIFO)

Verwenden Sie append() zum Hinzufügen und pop() zum Entnehmen vom gleichen Ende:

from collections import deque
 
stack = deque()
stack.append("first")
stack.append("second")
stack.append("third")
 
print(stack.pop())    # third
print(stack.pop())    # second
print(stack.pop())    # first

Leistungsvergleich: Deque vs Liste

Das Fazit: Verwenden Sie deque, wenn Sie schnelle Operationen an beiden Enden benötigen. Verwenden Sie list, wenn Sie schnellen Zufallszugriff per Index benötigen.

Benchmark

from collections import deque
import time
 
def benchmark_left_operations(n):
    """Compare popleft/appendleft performance."""
    # List: pop from position 0
    data = list(range(n))
    start = time.perf_counter()
    while data:
        data.pop(0)
    list_time = time.perf_counter() - start
 
    # Deque: popleft
    data = deque(range(n))
    start = time.perf_counter()
    while data:
        data.popleft()
    deque_time = time.perf_counter() - start
 
    print(f"n={n:>8,}")
    print(f"  list.pop(0):     {list_time:.4f}s")
    print(f"  deque.popleft(): {deque_time:.4f}s")
    print(f"  Speedup: {list_time / deque_time:.1f}x")
 
benchmark_left_operations(100_000)

Thread-Sicherheit

Pythons deque bietet thread-sichere append(), appendleft(), pop() und popleft() Operationen. Diese Methoden sind in CPython atomar, da sie innerhalb einer einzigen Bytecode-Anweisung ausgeführt werden, geschützt durch den GIL.

Für Produktionssysteme, die blockierendes Verhalten benötigen (Warten auf Elemente), verwenden Sie stattdessen queue.Queue, das intern deque umhüllt und geeignete Sperren und Bedingungsvariablen hinzufügt.

Praktische Muster

BFS-Graphtraversierung

from collections import deque
 
def bfs(graph, start):
    """Breadth-first search using deque as queue."""
    visited = set()
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(
                neighbor for neighbor in graph[node]
                if neighbor not in visited
            )
    return order
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Maximum im gleitenden Fenster

from collections import deque
 
def sliding_window_max(nums, k):
    """Find maximum in each sliding window of size k."""
    result = []
    window = deque()  # Stores indices of useful elements
    for i, num in enumerate(nums):
        while window and window[0] < i - k + 1:
            window.popleft()
        while window and nums[window[-1]] < num:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result
 
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))
# [3, 3, 5, 5, 6, 7]

Rückgängig-Historie

Eine begrenzte Deque eignet sich hervorragend als Rückgängig-Historie, die automatisch die ältesten Aktionen vergisst:

from collections import deque
 
class TextEditor:
    def __init__(self, max_undo=50):
        self.content = ""
        self._undo_stack = deque(maxlen=max_undo)
 
    def type_text(self, text):
        self._undo_stack.append(self.content)
        self.content += text
 
    def delete_last(self, n=1):
        self._undo_stack.append(self.content)
        self.content = self.content[:-n]
 
    def undo(self):
        if self._undo_stack:
            self.content = self._undo_stack.pop()
 
editor = TextEditor(max_undo=10)
editor.type_text("Hello")
editor.type_text(" World")
print(editor.content)   # Hello World
editor.undo()
print(editor.content)   # Hello

Datenstruktur-Performance in Jupyter testen

Beim Benchmarking von Deques gegenüber Listen oder beim Abstimmen von maxlen für Ihre spezifische Arbeitslast sind interaktive Notebooks unschätzbar wertvoll. RunCell (opens in a new tab) bietet eine KI-gestützte Jupyter-Umgebung, in der Sie Datenstruktur-Operationen profilieren, Leistungsunterschiede visualisieren und intelligente Optimierungsvorschläge erhalten können.

FAQ

Was ist eine Deque in Python?

Eine Deque (doppelseitige Warteschlange) ist eine Datenstruktur aus Pythons collections-Modul, die O(1) Append- und Pop-Operationen von beiden Enden unterstützt. Anders als eine Liste, die O(n) Zeit für das Einfügen oder Entfernen am Anfang benötigt, bietet eine Deque konstante Zeitperformance für Operationen an beiden Enden.

Wann sollte ich deque statt list verwenden?

Verwenden Sie deque, wenn Sie schnelles Einfügen oder Entfernen an beiden Enden der Sequenz benötigen, z.B. bei der Implementierung von Warteschlangen (FIFO), der Verwaltung gleitender Fenster oder der BFS-Traversierung. Bleiben Sie bei list, wenn Sie schnellen Zufallszugriff per Index benötigen (O(1) für Liste vs O(n) für Deque).

Ist Python deque thread-sicher?

Ja, die Methoden append(), appendleft(), pop() und popleft() sind in CPython thread-sicher. Diese Operationen sind atomar, da sie innerhalb einer einzigen Bytecode-Anweisung abgeschlossen werden, geschützt durch den GIL. Zusammengesetzte Operationen sind jedoch nicht atomar, verwenden Sie also queue.Queue für Producer-Consumer-Muster, die blockierende Semantik benötigen.

Was macht maxlen bei deque?

Der maxlen-Parameter erstellt eine begrenzte Deque mit einer festen maximalen Größe. Wenn die Deque voll ist und ein neues Element hinzugefügt wird, wird das Element am gegenüberliegenden Ende automatisch verworfen. Dies ist nützlich für die Implementierung von gleitenden Fenstern, Aktivitätsprotokollen und Rückgängig-Historien.

Wie vergleicht sich deque mit queue.Queue?

collections.deque ist auf Geschwindigkeit ausgelegt. queue.Queue umhüllt intern eine Deque, fügt aber Thread-Synchronisations-Primitive wie Sperren und Bedingungsvariablen hinzu. Verwenden Sie deque für einthread-Code. Verwenden Sie queue.Queue, wenn Sie blockierende get()- und put()-Operationen in mehrtthread-Producer-Consumer-Szenarien benötigen.

Fazit

Pythons collections.deque ist eine der nützlichsten, aber unterschätztesten Datenstrukturen in der Standardbibliothek. Sie beseitigt die O(n)-Strafe der linksseitigen Listenoperationen, bietet eingebaute begrenzte Pufferung mit maxlen, ermöglicht thread-sichere atomare Operationen und dient als Grundlage für Warteschlangen, Stacks, gleitende Fenster und Graphtraversierungsalgorithmen.

Die Entscheidung ist unkompliziert: Wenn Ihr Code beide Enden einer Sequenz berührt, verwenden Sie deque. Wenn Sie schnellen Zufallszugriff per Index benötigen, verwenden Sie list. Für die meisten Warteschlangen- und Stack-Muster sollte deque Ihre Standardwahl sein.