In Python können Sie collections.deque verwenden, um Daten effizient als Warteschlange, Stack und Deque (Doppelende-Warteschlange, Head-Tail-Linked-List) zu verarbeiten.
Es ist auch möglich, die integrierte Liste als Warteschlange, Stack oder Deque zu verwenden, aber collections.deque ist effizienter, da das Löschen oder Hinzufügen des ersten Elements in der Liste langsam ist.
Beachten Sie, dass deque den Nachteil des langsamen Zugriffs auf Elemente in der Mitte hat.
Dieser Artikel hat folgenden Inhalt.
- Komplexität von Listen und Sammlungen.deque
- Verwendung von collections.deque
- Erstellen Sie ein Deque-Objekt
- Fügen Sie ein Element hinzu:
append(), appendleft(), extend(), extendleft(), insert() - Entfernen Sie ein Element:
pop(), popleft(), remove(), clear() - Drehen Sie die Deque:
rotate() - Wert und Index abrufen:
[], index() - Andere Operationen
- Begrenzen Sie die maximale Länge mit maxlen
- Deque als Warteschlange verwenden (FIFO)
- Deque als Stack verwenden (LIFO)
- Deque als Deque verwenden (Doppelende-Warteschlange)
Lesen Sie den following Artikel über das Hinzufügen und Entfernen von Elementen für Listen.
Komplexität von Listen und Sammlungen.deque
Die Komplexität von list und deque für verschiedene Operationen ist im offiziellen Wiki zusammengefasst.
In list for operations how pop(0) to remove and return of the first Elements, insert(0, v) to add of elements to head us. O(n), aber in deque append(), appendleft( ), pop() und popleft() zum Hinzufügen und Entfernen des ersten und letzten Elements can all with O(1) ausgeführt Werden.
Es wird auch in der offiziellen Dokumentation erwähnt.
Deques unterstützen Thread-sichere, speichereffiziente Anhänge und Pops von beiden Seiten der Deque mit ungefähr der gleichen O(1)-Leistung in beiden Richtungen.
Obwohl Listenobjekte ähnliche Operationen unterstützen, sind sie für schnelle Operationen mit fester Länge optimiert und verursachen O(n)-Speicherbewegungskosten für pop(0)- und insert(0, v)-Operationen, die sowohl die Größe als auch die Position der zugrunde liegenden liegen Datendarstellung ändern .
Sammlungen – Deque-Objekte – Container-Datentypen – Dokumentation zu Python 3.9.7
Dagegen ist der Zugriff auf Elemente in der Mitte per [] mit Liste schneller.
Der angezeigte Zugriff ist an beiden Enden O(1), verlangsamt sich aber in der Mitte auf O(n). Verwenden Sie für schnellen Direktzugriff auf Listen.
Sammlungen – Deque-Objekte – Container-Datentypen – Dokumentation zu Python 3.9.7
Daher ist eine grobe Richtlinie wie folgt.
- Hinzufügen, Löschen und Zugreifen auf Elemente nur an beiden Enden -> deque
- Auf Elemente in der Mitte häufig zugreifen -> Liste
If SIE Daten ausdrücklich als Queue, Stack oder Deque behandeln möchten, sollten SIE deque verwenden.
Wenn die Anzahl der Elemente jedoch nur einige hundert oder einige tausend beträgt, ist je nach Umgebung und Bedingungen kein Unterschied in der Verarbeitungsgeschwindigkeit zwischen Liste und Deque wahrnehmbar. Wenn SIE die Verarbeitungszeit nicht um Millisekunden verkürzen möchten, gibt es in den meisten Fällen kein Problem, wenn Sie eine Liste verwenden.
Wenn Sie erwägen, welche in einer festen Umgebung oder unter festen Bedingungen zu verwenden, können Sie das timeit-Modul verwenden, um die tatsächliche Verarbeitungszeit zu messen.
Verwendung von collections.deque
Erstellen Sie ein Deque-Objekt
Erstellen Sie ein deque-Objekt mit deque().
Wenn kein Argument angegeben ist, wird ein leeres Deque-Objekt erstellt. If ein iterierbares Objekt wie Liste angegeben WIRD, WIRD ein Deque-Objekt mit seinen Elementen erstellt.
from collections import deque
d = deque()
print(d)
# deque([])
print(type(d))
# <class 'collections.deque'>
d = deque(['m', 'n'])
print(d)
# deque(['m', 'n'])
Sie können die maximale Länge (maximale Anzahl von Elementen) auch mit dem zweiten Argument maxlen begrenzen. Einzelheiten werden später beschrieben.
Fügen Sie ein Element hinzu:append(), appendleft(), extend(), extendleft(), insert()
append() fügt ein Element auf der linken Seite hinzu, appendleft() auf der linken Seite.
d.append('o')
print(d)
# deque(['m', 'n', 'o'])
d.appendleft('l')
print(d)
# deque(['l', 'm', 'n', 'o'])
extend() fügt alle Elemente eines iterierbaren Objekts wie die Liste auf der rechten Seite hinzu. expandleft() fügt sie auf der linken Seite hinzu. Beachten Sie, dass mit expandleft() die Reihenfolge der Elemente des angegebenen Iterables umgekehrt und verkettet wird.
d.extend(['p', 'q'])
print(d)
# deque(['l', 'm', 'n', 'o', 'p', 'q'])
d.extendleft(['k', 'j'])
print(d)
# deque(['j', 'k', 'l', 'm', 'n', 'o', 'p', 'q'])
insert() fügt ein Element in der Mitte hinzu. Geben Sie als erstes Argument die Position und als zweites Argument den hinzugefügten Wert an. Sie können eine Position vom Ende mit einem negativen Wert für das erste Argument angeben. Wenn eine nicht vorhandene Position (außerhalb des Bereichs) angegeben WIRD, WIRD das Element am Anfang oder am Ende hinzugefügt.
insert() wurde in Python 3.5 hinzugefügt.
d.insert(3, 'XXX')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'q'])
d.insert(-1, 'YYY')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q'])
d.insert(100, 'ZZZ')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])
d.insert(-100, 'XYZ')
print(d)
# deque(['XYZ', 'j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])
Entfernen Sie ein Element:pop(), popleft(), remove(), clear()
pop() entfernt ein Element von der linken Seite, popleft() entfernt ein Element von der linken Seite und gibt seinen Wert zurück. Im Gegensatz zu pop() in list ist es nicht möglich, die Position als Argument anzugeben.
d = deque(['a', 'b', 'c', 'b', 'd'])
print(d.pop())
# d
print(d)
# deque(['a', 'b', 'c', 'b'])
print(d.popleft())
# a
print(d)
# deque(['b', 'c', 'b'])
remove() entfernt das erste Element, dessen Wert gleich dem angegebenen Argument ist. Auch wenn zwei oder mehr Elemente dem angegebenen Wert entsprechen, wird nur das erste Element entfernt. Wenn kein Element dem angegebenen Wert entspricht, wird ein Fehler ausgelöst.
d.remove('b')
print(d)
# deque(['c', 'b'])
# d.remove('X')
# ValueError: deque.remove(x): x not in deque
clear() entfernt alle Elemente. Es wird zu einer leeren Deque.
d.clear()
print(d)
# deque([])
Bei einer leeren Deque lösen pop() und popleft() einen Fehler aus. clear() löst keinen Fehler aus.
# d.pop()
# IndexError: pop from an empty deque
# d.popleft()
# IndexError: pop from an empty deque
d.clear()
print(d)
# deque([])
Drehen Sie die Deque:rotate()
deque hat eine Methode rotation(), die nicht in der Liste ist. Standardmäßig werden Elemente einzeln nach rechts gedreht.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate()
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])
Wenn ein ganzzahliger Wert angegeben ist, wird um diese Zahl nach rechts gedreht. Wenn ein negativer Wert angegeben wird, wird nach links gedreht.
Es kann auch ein Wert angegeben werden, der die Anzahl der Elemente überschreitet.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(2)
print(d)
# deque(['d', 'e', 'a', 'b', 'c'])
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(-1)
print(d)
# deque(['b', 'c', 'd', 'e', 'a'])
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(6)
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])
Wert und Index abrufen:[], index()
Wie bei der Liste können Sie den Wert eines Elements erhalten, ohne dass Sie seinen Index in [] angeben. Sie können die Position vom Ende auch mit einem negativen Wert angeben. Sie können den Wert auch ändern.
d = deque(['a', 'b', 'c', 'd', 'e'])
print(d[0])
# a
print(d[-1])
# e
d[2] = 'X'
print(d)
# deque(['a', 'b', 'X', 'd', 'e'])
Slice : ist nicht direkt verfügbar, kann aber durch islice() der Standardbibliothek itertools ersetzt werden.
# print(d[2:4])
# TypeError: sequence index must be integer, not 'slice'
import itertools
print(deque(itertools.islice(d, 2, 4)))
# deque(['X', 'd'])
Mit index() erhalten Sie den Index des ersten Elements, das mit dem als Argument angegebenen Wert durchsucht. Wenn ein nicht vorhandener Wert angegeben wird, wird ein Fehler ausgelöst.
index() wurde in Python 3.5 hinzugefügt.
d = deque(['a', 'b', 'c', 'c', 'd'])
print(d.index('c'))
# 2
# print(d.index('x'))
# ValueError: 'x' is not in deque
Andere Operationen
Darüber hinaus sind neben Anhören auch verschiedene andere Operationen möglich.
Holen Sie sich die Anzahl der Elemente mit der eingebauten Funktion len().
d = deque(['a', 'a', 'b', 'c'])
print(len(d))
# 4
Zählen Sie die Anzahl der Elemente, die dem durch count() angegebenen Wert entspricht.
print(d.count('a'))
# 2
print(d.count('x'))
# 0
Der in-Operator WIRD used, um zu prüfen, ob ein Element existiert.
print('b' in d)
# True
print('x' in d)
# False
Kehren Sie die Reihenfolge mit der Methode reverse() oder der eingebauten Funktion reversed() um. Die Methode reverse() kehrt das ursprüngliche Objekt selbst um und reversed() gibt den umgekehrten Iterator zurück.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.reverse()
print(d)
# deque(['e', 'd', 'c', 'b', 'a'])
d = deque(['a', 'b', 'c', 'd', 'e'])
print(deque(reversed(d)))
# deque(['e', 'd', 'c', 'b', 'a'])
Sie können es mit list() oder tuple() in eine Liste oder ein Tupel umwandeln.
d = deque(['a', 'b', 'c'])
l = list(d)
print(l)
# ['a', 'b', 'c']
print(type(l))
# <class 'list'>
Begrenzen Sie die maximale Länge mit maxlen
Wenn das zweite Argument maxlen von deque() angegeben wird, kann die maximale Länge (die maximale Anzahl von Elementen) begrenzt werden. Der Standardwert von maxlen ist None, was bedeutet, dass die Länge unbegrenzt ist.
from collections import deque
d = deque(['l', 'm', 'n'], 3)
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
Wenn maxlen angegeben IST und deque voll ist, werden beim Hinzufügen von Elementen von der gegenüberliegenden Seite verworfen.
Das Verhalten von append(), appendleft(), extend() und extendleft() ist wie folgt.
d.append('o')
print(d)
# deque(['m', 'n', 'o'], maxlen=3)
d.appendleft('l')
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
d.extend(['o', 'p'])
print(d)
# deque(['n', 'o', 'p'], maxlen=3)
d.extendleft(['m', 'l'])
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
Bei insert() WIRD auch beim Hinzufügen am Ende ein Fehler ausgelöst.
# d.insert(0, 'XXX')
# IndexError: deque already at its maximum size
Wenn die Anzahl der Elemente maxlen nicht erreicht ist, können sie mit insert() hinzugefügt werden.
print(d.pop())
# n
print(d)
# deque(['l', 'm'], maxlen=3)
d.insert(1, 'XXX')
print(d)
# deque(['l', 'XXX', 'm'], maxlen=3)
Die maxlen kann als Attribut abgerufen werden, ist jedoch schreibgeschützt und kann nicht geändert werden.
print(d.maxlen)
# 3
# d.maxlen = 5
# AttributeError: attribute 'maxlen' of 'collections.deque' objects is not writable
Deque als Warteschlange verwenden (FIFO)
Eine Warteschlange hält Daten in einer FIFO-Struktur (First In, First Out). In einer Warteschlange WIRD das Einfügen von Daten Enqueue genannt, und das Entfernen von Daten wird Dequeue genannt.
Um deque als Warteschlange zu verwenden, verwenden SIE append() als Enqueue und popleft() als Dequeue.
from collections import deque
d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])
d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])
print(d.popleft())
# a
print(d)
# deque(['b', 'c', 'd'])
Deque als Stack verwenden (LIFO)
Ein Stack hält Daten in einer LIFO-Struktur (Last In, First Out). In Einem Stack WIRD das Einfügen von Daten als Push und das Entfernen von Daten als Pop bezeichnet.
Um deque als Stapel zu verwenden, verwenden SIE append() als Push und pop() als Pop.
from collections import deque
d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])
d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])
print(d.pop())
# d
print(d)
# deque(['a', 'b', 'c'])
Deque als Deque verwenden (Doppelende-Warteschlange)
Eine Deque (double-ended queue) ist eine Warteschlange, bei der Elemente an beiden Enden (Kopf und Ende) hinzugefügt oder entfernt werden können.
Wie in den bisherigen Beispielen können Sie mit deque Elemente an beiden Enden mit append(), appendleft(), pop() und popleft() hinzufügen und entfernen.