Ein Deque steht für Double-Ended Queue. Es handelt sich um eine spezielle Art von Datenstruktur, mit der Sie Elemente an beiden Enden effizient hinzufügen und entfernen können.

Im Gegensatz zu normalen Warteschlangen (die normalerweise dem Prinzip „First In First Out“ folgen) unterstützt eine Deque sowohl FIFO- als auch LIFO-Operationen. Dies macht es sehr flexibel und nützlich in realen Anwendungen wie der Aufgabenplanung bei Schiebefensterproblemen und der Echtzeit-Datenverarbeitung.

Beispiel:

from collections import deque # Declaring deque  de = deque(['name''age''DOB']) print(de) 

deque(['name' 'age' 'DOB']) 

Warum brauchen wir Deque?

• Es unterstützt O(1)-Zeit für das Hinzufügen/Entfernen von Elementen an beiden Enden.
• Es ist effizienter als Listen für Front-End-Operationen.
• Es kann sowohl als Warteschlange (FIFO) als auch als Stapel (LIFO) fungieren.
• Ideal für die Planung von Schiebefensterproblemen und die Datenverarbeitung in Echtzeit.
• Es bietet leistungsstarke integrierte Methoden wie appendleft() popleft() Und drehen().

Arten der eingeschränkten Deque-Eingabe

• Eingabebeschränkte Deque :  Die Eingabe ist an einem Ende begrenzt, während das Löschen an beiden Enden zulässig ist.
• Ausgabebeschränkte Deque : Die Ausgabe ist an einem Ende begrenzt, das Einfügen ist jedoch an beiden Enden zulässig.

Operationen auf Deque 

Hier ist eine Tabelle, die integrierte Operationen einer Deque in Python mit Beschreibungen und ihren entsprechenden Zeitkomplexitäten auflistet:

Klasse vs. Objekt Java

Anhängen und Löschen von Elementen aus der Warteschlange

• anhängen(x): Fügt x am rechten Ende der Deque hinzu.
• appendleft(x): Fügt x am linken Ende der Deque hinzu.
• verlängern(iterierbar): Fügt alle Elemente vom Iterable bis zum rechten Ende hinzu.
• extendleft(iterable): Fügt alle Elemente vom iterierbaren Element zum linken Ende hinzu (in umgekehrter Reihenfolge).
• entfernen(Wert): Entfernt das erste Vorkommen des angegebenen Werts aus der Deque. Wenn kein Wert gefunden wird, wird ein ValueError ausgelöst.
• Pop(): Entfernt ein Element vom rechten Ende und gibt es zurück.
• popleft(): Entfernt ein Element vom linken Ende und gibt es zurück.
• klar(): Entfernt alle Elemente aus der Deque.

from collections import deque dq = deque([10 20 30]) # Add elements to the right dq.append(40) # Add elements to the left dq.appendleft(5) # extend(iterable) dq.extend([50 60 70]) print('After extend([50 60 70]):' dq) # extendleft(iterable) dq.extendleft([0 5]) print('After extendleft([0 5]):' dq) # remove method dq.remove(20) print('After remove(20):' dq) # Remove elements from the right dq.pop() # Remove elements from the left dq.popleft() print('After pop and popleft:' dq) # clear() - Removes all elements from the deque dq.clear() # deque: [] print('After clear():' dq) 

Ausgabe:

After extend([50 60 70]): deque([5 10 20 30 40 50 60 70])  
After extendleft([0 5]): deque([5 0 5 10 20 30 40 50 60 70])  
After remove(20): deque([5 0 5 10 30 40 50 60 70])  
After pop and popleft: deque([0 5 10 30 40 50 60])  
After clear(): deque([])

Zugriff auf Element und Länge der Deque

• Indizierung: Greifen Sie mithilfe positiver oder negativer Indizes auf Elemente nach Position zu.
• nur(): Gibt die Anzahl der Elemente in der Deque zurück.

import collections dq = collections.deque([1 2 3 3 4 2 4]) # Accessing elements by index print(dq[0]) print(dq[-1]) # Finding the length of the deque print(len(dq)) 

1 4 7 

Zählen Sie die Rotation und Umkehrung einer Deque

• Anzahl(Wert): Diese Methode zählt die Anzahl der Vorkommen eines bestimmten Elements in der Deque.
• drehen(n): Diese Methode dreht die Deque um n Schritte. Positives n dreht sich nach rechts und negatives n dreht sich nach links.
• umkehren(): Diese Methode kehrt die Reihenfolge der Elemente in der Deque um.

from collections import deque # Create a deque dq = deque([10 20 30 40 50 20 30 20]) # 1. Counting occurrences of a value print(dq.count(20)) # Occurrences of 20 print(dq.count(30)) # Occurrences of 30 # 2. Rotating the deque dq.rotate(2) # Rotate the deque 2 steps to the right print(dq) dq.rotate(-3) # Rotate the deque 3 steps to the left print(dq) # 3. Reversing the deque dq.reverse() # Reverse the deque print(dq) 

3 2 deque([30 20 10 20 30 40 50 20]) deque([20 30 40 50 20 30 20 10]) deque([10 20 30 20 50 40 30 20])