Python Language
Deque-Modul
Suche…
Syntax
- dq = deque () # Erzeugt ein leeres Deque
- dq = deque (iterable) # Erzeugt einen Deque mit einigen Elementen
- dq.append (object) # Fügt ein Objekt rechts von der Deque hinzu
- dq.appendleft (object) # Fügt ein Objekt links vom Deque hinzu
- dq.pop () -> object # Entfernt das Objekt ganz rechts und gibt es zurück
- dq.popleft () -> object # Entfernt das linke Objekt und gibt es zurück
- dq.extend (iterable) # Fügt einige Elemente rechts vom Deque hinzu
- dq.extendleft (iterable) # Fügt einige Elemente links vom Deque hinzu
Parameter
| Parameter | Einzelheiten |
|---|---|
iterable | Erzeugt den Deque mit ursprünglichen Elementen, die von einem anderen iterierbaren Element kopiert wurden. |
maxlen | Begrenzt, wie groß der Deque sein kann, wobei alte Elemente als neue ausgegeben werden. |
Bemerkungen
Diese Klasse ist nützlich, wenn Sie ein Objekt benötigen, das einer Liste ähnelt, die schnelle Anhänge- und Popoperationen von beiden Seiten zulässt (der Name deque steht für " double-ended queue ").
Die zur Verfügung gestellten Methoden sind in der Tat sehr ähnlich, mit der Ausnahme, dass einige wie pop , append oder extend mit left . Die deque Datenstruktur sollte einer Liste vorgezogen werden, wenn Elemente an beiden Enden häufig eingefügt und gelöscht werden müssen, da dies zu einer konstanten Zeit O (1) möglich ist.
Basic Deque mit
Die wichtigsten Methoden, die für diese Klasse nützlich sind, sind popleft und appendleft
from collections import deque
d = deque([1, 2, 3])
p = d.popleft() # p = 1, d = deque([2, 3])
d.appendleft(5) # d = deque([5, 2, 3])
Begrenzung der Deque-Größe
Verwenden Sie den Parameter maxlen , während Sie eine Deque erstellen, um die Größe der Deque zu begrenzen:
from collections import deque
d = deque(maxlen=3) # only holds 3 items
d.append(1) # deque([1])
d.append(2) # deque([1, 2])
d.append(3) # deque([1, 2, 3])
d.append(4) # deque([2, 3, 4]) (1 is removed because its maxlen is 3)
Verfügbare Methoden in deque
Leeren deque erstellen:
dl = deque() # deque([]) creating empty deque
Erstellen von Deque mit einigen Elementen:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Element zu deque hinzufügen:
dl.append(5) # deque([1, 2, 3, 4, 5])
Element links von deque hinzufügen:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Liste der Elemente zu deque hinzufügen:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Hinzufügen einer Liste von Elementen von links:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
Mit dem Element .pop() wird ein Element auf der rechten Seite entfernt:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
Verwenden .popleft() Elements .popleft() zum Entfernen eines Elements von der linken Seite:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Element nach seinem Wert entfernen:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
Kehren Sie die Reihenfolge der Elemente in deque um:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])
Breite erste Suche
Der Deque ist die einzige Python-Datenstruktur mit schnellen Warteschlangenoperationen . (Hinweis queue.Queue ist normalerweise nicht geeignet, da sie für die Kommunikation zwischen Threads queue.Queue ist.) Ein grundlegender Anwendungsfall einer Queue ist die erste Suche in der Breite .
from collections import deque
def bfs(graph, root):
distances = {}
distances[root] = 0
q = deque([root])
while q:
# The oldest seen (but not yet visited) node will be the left most one.
current = q.popleft()
for neighbor in graph[current]:
if neighbor not in distances:
distances[neighbor] = distances[current] + 1
# When we see a new node, we add it to the right side of the queue.
q.append(neighbor)
return distances
Angenommen, wir haben eine einfache gerichtete Grafik:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
Wir können nun die Entfernungen von einer Startposition aus finden:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}