Deque (Double Ended Queue) in Python wird mithilfe des Moduls implementiert Sammlungen . Deque wird einer Liste in den Fällen vorgezogen, in denen wir schnellere Anhänge- und Pop-Vorgänge von beiden Enden des Containers benötigen, da deque eine bereitstellt O(1) Zeitkomplexität für Append- und Pop-Operationen im Vergleich zu einer Liste, die O(n)-Zeitkomplexität bereitstellt.
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.
Beispiel: Python-Code zur Demonstration
Python3
from> collections>import> deque> > # Declaring deque> queue>=> deque([>'name'>,>'age'>,>'DOB'>])> > print>(queue)> |
Konvertieren Sie String in Int
>
>Ausgabe
deque(['name', 'age', 'DOB'])>
Operationen auf Deque
Beispiel 1: Elemente effizient anhängen
- append() :- Diese Funktion wird verwendet, um den Wert in ihrem Argument am rechten Ende der Deque einzufügen. appendleft() :- Diese Funktion wird verwendet, um den Wert in ihrem Argument am linken Ende der Deque einzufügen.
Python3
# importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>])> print>(>'deque: '>, de)> # using append() to insert element at right end> # inserts 4 at the end of deque> de.append(>4>)> # printing modified deque> print>(>'
The deque after appending at right is : '>)> print>(de)> # using appendleft() to insert element at left end> # inserts 6 at the beginning of deque> de.appendleft(>6>)> # printing modified deque> print>(>'
The deque after appending at left is : '>)> print>(de)> |
>
>Ausgabe
deque: deque([1, 2, 3]) The deque after appending at right is : deque([1, 2, 3, 4]) The deque after appending at left is : deque([6, 1, 2, 3, 4])>
Siehe Ende für Komplexitätsanalyse.
Beispiel 2: Effizientes Platzieren von Gegenständen
- pop() :- Diese Funktion wird verwendet, um ein Argument vom rechten Ende der Deque zu löschen. popleft() :- Diese Funktion wird verwendet, um ein Argument vom linken Ende der Deque zu löschen.
Python3
# importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>6>,>1>,>2>,>3>,>4>])> print>(>'deque: '>, de)> # using pop() to delete element from right end> # deletes 4 from the right end of deque> de.pop()> # printing modified deque> print>(>'
The deque after deleting from right is : '>)> print>(de)> # using popleft() to delete element from left end> # deletes 6 from the left end of deque> de.popleft()> # printing modified deque> print>(>'
The deque after deleting from left is : '>)> print>(de)> |
>
>Ausgabe
deque: deque([6, 1, 2, 3, 4]) The deque after deleting from right is : deque([6, 1, 2, 3]) The deque after deleting from left is : deque([1, 2, 3])>
Siehe Ende für Komplexitätsanalyse.
Beispiel 3: Zugriff auf Elemente in einer Deque
- index(ele, beg, end) :- Diese Funktion gibt den ersten Index des in den Argumenten genannten Werts zurück und beginnt mit der Suche vom Anfang bis zum Endindex. insert(i, a) :- Diese Funktion fügt den in arguments(a) genannten Wert am in arguments angegebenen Index(i) ein. remove(): – Diese Funktion entfernt das erste Vorkommen des in den Argumenten genannten Werts. count(): – Diese Funktion zählt die Anzahl der in Argumenten genannten Wertvorkommen.
Python3
# Python code to demonstrate working of> # insert(), index(), remove(), count()> # importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>,>3>,>4>,>2>,>4>])> # using index() to print the first occurrence of 4> print> (>'The number 4 first occurs at a position : '>)> print> (de.index(>4>,>2>,>5>))> # using insert() to insert the value 3 at 5th position> de.insert(>4>,>3>)> # printing modified deque> print> (>'The deque after inserting 3 at 5th position is : '>)> print> (de)> # using count() to count the occurrences of 3> print> (>'The count of 3 in deque is : '>)> print> (de.count(>3>))> # using remove() to remove the first occurrence of 3> de.remove(>3>)> # printing modified deque> print> (>'The deque after deleting first occurrence of 3 is : '>)> print> (de)> |
>
>Ausgabe
The number 4 first occurs at a position : 4 The deque after inserting 3 at 5th position is : deque([1, 2, 3, 3, 3, 4, 2, 4]) The count of 3 in deque is : 3 The deque after deleting first occurrence of 3 is : deque([1, 2, 3, 3, 4, 2, 4])>
Siehe Ende für Komplexitätsanalyse.
Beispiel 4: Größe einer Deque
- len(dequeue) :- Gibt die aktuelle Größe der dequeue zurück.
Python3
# Python Program to demonstrate> # how to find size of a Dequeue> from> collections>import> deque> # initializing deque> de>=> deque([>1>,>2>,>3>,>4>,>5>,>6>])> print>(>'Current Deque: '>, de)> # printing current size of deque> print>(f>'Size of Deque: {len(de)}'>)> # using pop() to delete element from right end> # deletes 6 from the right end of deque> de.pop()> # printing modified deque> print>(>'
The deque after deleting from right is: '>, end>=> '')> print>(de)> # printing current size of deque> print>(f>'Size of Deque: {len(de)}'>)> # This code is contributed by Susobhan Akhuli> |
>
>Ausgabe
Current Deque: deque([1, 2, 3, 4, 5, 6]) Size of Deque: 6 The deque after deleting from right is: deque([1, 2, 3, 4, 5]) Size of Deque: 5>
Siehe Ende für Komplexitätsanalyse.
Beispiel 5: Vorder- und Rückseite einer Deque
- Deque[0]: – Wir können über die Indizierung mit de[0] auf das vordere Element der Deque zugreifen. Deque[-1]: – Wir können über die Indizierung mit de[-1] auf das hintere Element der Deque zugreifen.
Python3
# Python Program to demonstrate> # accessing the front and back of a Deque> from> collections>import> deque> # initializing deque> de>=> deque([>1>,>2>,>3>,>4>,>5>,>6>])> print>(>'Current Deque: '>, de)> # Accessing the front element of the deque> print>(>'Front element of the deque:'>, de[>0>])> # Accessing the back element of the deque> print>(>'Back element of the deque:'>, de[>->1>])> # This code is contributed by Susobhan Akhuli> |
>
>Ausgabe
Current Deque: deque([1, 2, 3, 4, 5, 6]) Front element of the deque: 1 Back element of the deque: 6>
Siehe Ende für Komplexitätsanalyse.
Beispiel 6: Verschiedene Operationen auf Deque
- extend(iterable): – Diese Funktion wird verwendet, um mehrere Werte am rechten Ende der Deque hinzuzufügen. Das übergebene Argument ist iterierbar. extensionleft(iterable) :- Diese Funktion wird verwendet, um mehrere Werte am linken Ende der Deque hinzuzufügen. Das übergebene Argument ist iterierbar. Durch Linksanhänge wird die Reihenfolge umgekehrt. reverse() :- Diese Funktion wird verwendet, um die Reihenfolge der Deque-Elemente umzukehren. rotieren(): – Diese Funktion dreht die Deque um die in den Argumenten angegebene Zahl. Wenn die angegebene Zahl negativ ist, erfolgt die Drehung nach links. Ansonsten erfolgt die Drehung nach rechts.
Python3
# Python code to demonstrate working of> # extend(), extendleft(), rotate(), reverse()> # importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>,])> # using extend() to add numbers to right end> # adds 4,5,6 to right end> de.extend([>4>,>5>,>6>])> # printing modified deque> print> (>'The deque after extending deque at end is : '>)> print> (de)> # using extendleft() to add numbers to left end> # adds 7,8,9 to left end> de.extendleft([>7>,>8>,>9>])> # printing modified deque> print> (>'The deque after extending deque at beginning is : '>)> print> (de)> # using rotate() to rotate the deque> # rotates by 3 to left> de.rotate(>->3>)> # printing modified deque> print> (>'The deque after rotating deque is : '>)> print> (de)> # using reverse() to reverse the deque> de.reverse()> # printing modified deque> print> (>'The deque after reversing deque is : '>)> print> (de)> |
>
>Ausgabe
The deque after extending deque at end is : deque([1, 2, 3, 4, 5, 6]) The deque after extending deque at beginning is : deque([9, 8, 7, 1, 2, 3, 4, 5, 6]) The deque after rotating deque is : deque([1, 2, 3, 4, 5, 6, 9, 8, 7]) The deque after reversing deque is : deque([7, 8, 9, 6, 5, 4, 3, 2, 1])>
Siehe Ende für Komplexitätsanalyse.
Komplexitätsanalyse:
| Methoden Zeichenfolge in Java | Zeitkomplexität | Hilfsraum |
|---|---|---|
| append() | O(1) | O(1) |
| appendleft() | O(1) | O(1) |
| Pop() | O(1) | O(1) |
| popleft() | O(1) | O(1) |
| index(ele, beg, end) | AN) | O(1) |
| einfügen(i, a) | AN) | O(1) |
| entfernen() | AN) | O(1) |
| zählen() | AN) | O(1) |
| einfach (aus der Warteschlange entfernen) | O(1) | O(1) |
| Deque[0] | O(1) | O(1) |
| Deque[-1] | O(1) | O(1) |
| erweitern (iterierbar) | PFEIL) | O(1) |
| extensionleft(iterable) | PFEIL) | O(1) |
| umkehren() | AN) | O(1) |
| drehen() | PFEIL) | O(1) So aktualisieren Sie in Java |