Deque in Python – Tutorial mit Beispielen

Wenn Sie ein Python-Entwickler sind, haben Sie wahrscheinlich schon von einer Deque oder „doppelten Warteschlange“ gehört. Es handelt sich um ein leistungsstarkes Tool, das die Effizienz Ihrer Anwendung steigern und ihre Leistung beschleunigen kann.

Eine Deque ist ein spezieller Container-Datentyp, der schnellere Anhänge- und Popup-Vorgänge von beiden Enden des Containers aus ermöglicht. Dies macht es zu einem wertvollen Werkzeug für die Implementierung von Warteschlangen und Stapeln, bei denen es sich in der Datenverarbeitung um gängige listenartige Datentypen handelt.

Es handelt sich um eine hochoptimierte Datenstruktur auf niedriger Ebene, die für eine Vielzahl von Anwendungen sehr nützlich ist. Als Python-Programmierer ist eine Deque ein Werkzeug, das Sie in Ihrem Arsenal haben möchten.

Lesen Sie weiter, um mehr über Deques zu erfahren und wie Sie sie in Ihren Python-Code implementieren können !

Inhaltsverzeichnis

• Was ist ein Deque?
  • Merkmale einer Python-Deque
  • Anwendungen von A Deque
• So erstellen und initialisieren Sie eine Deque
  • Verwenden der Funktion deque()
  • Initialisieren einer Deque mit Elementen
• So führen Sie allgemeine Deque-Operationen durch
  • Elemente zu einer Deque hinzufügen
  • Hinzufügen mehrerer Datenelemente zu einer Deque
  • Elemente aus einer Deque entfernen
  • Entfernen aller Elemente aus einer Deque
  • Zugriff auf Elemente einer Deque
  • Elemente einer Deque ändern
• So arbeiten Sie mit einer Deque als Warteschlange
  • Verwendung der Methoden append() und popleft()
  • Überprüfen, ob eine Deque-Warteschlange leer ist
• Arbeiten mit Deque als Stack
  • Verwendung der Methoden append() und pop()
  • Auf ein leeres Deque-Objekt prüfen
• Was ist eine eingeschränkte Deque?
  • • Eingabebeschränkte Deque
    • Ausgabebeschränkte Deque
• Lassen Sie uns das abschließen

Was ist ein Deque?

Wenn Sie mit Python oder der Computerprogrammierung im Allgemeinen noch nicht vertraut sind, fragen Sie sich vielleicht, was eine Deque ist. Deque steht für „ Double-Ended Queue “ und ist eine Datenstruktur, die es Ihnen ermöglicht, Elemente an beiden Enden der Warteschlange hinzuzufügen und zu entfernen.

Es ähnelt einer normalen Warteschlange, bietet jedoch die zusätzliche Flexibilität, Elemente sowohl vorne als auch hinten in der Warteschlange hinzufügen und entfernen zu können. Dies ist möglich, weil Pythons Deque als doppelt verknüpfte Liste implementiert ist.

In Python werden Deques mithilfe des Collections-Moduls implementiert, das eine Deque-Klasse bereitstellt. Diese Klasse bietet eine Reihe von Methoden zum Hinzufügen und Entfernen von Elementen zur Deque.

Es bietet auch Funktionen für andere nützliche Vorgänge, wie z. B. das Drehen der Deque oder das vollständige Löschen der Deque.

Merkmale einer Python-Deque

Im Gegensatz zu einer regulären Liste, die eine O(n)-Zeitkomplexität für Anhänge- und Popup-Operationen aufweist, bietet eine Deque eine O(1)-Zeitkomplexität. Dies macht es bei diesen Lese- und Schreibvorgängen deutlich schneller und speichereffizienter.

Hier sind einige weitere Python-Deque-Funktionen, die Sie kennen sollten:

• Es handelt sich um eine veränderliche Datenstruktur.

• Es kann mehrere Datentypen speichern, z. B. Ganzzahlen, Tupel, Arrays usw.

• Es unterstützt Indizierungs-, aber keine Slicing-Vorgänge.

• Die In-Place-Sortierung wird nicht unterstützt

• Es unterstützt gängige integrierte iterierbare Funktionen und Operationen wie in , sorted() , len() , reverse() usw.

Anwendungen von A Deque

Deques sind aus verschiedenen Gründen nützlich. Sie können beispielsweise zur Implementierung einer Warteschlange oder eines Stapels verwendet werden, beides gängige Datenstrukturen in der Informatik.

Sie können auch zur effizienten Verarbeitung von Daten in Echtzeit eingesetzt werden, beispielsweise in Streaming-Anwendungen oder in Systemen, die einen schnellen Zugriff auf Daten erfordern.

Neben der Verwendung für Warteschlangen und Stapel können Deques auch zur Implementierung von Breitensuchalgorithmen verwendet werden. Sie sind auch nützlich, um ein Schiebefenster mit Elementen in einer größeren Reihenfolge beizubehalten.

So erstellen und initialisieren Sie eine Deque

Sie können eine Deque mit einer integrierten Funktion aus dem Collections-Modul erstellen. Schauen wir uns einmal genauer an, wie Sie diese Datenstruktur erstellen und füllen können.

Verwenden der Funktion deque()

Um eine Deque in Python zu erstellen, können Sie die integrierte Funktion deque() aus dem Collections-Modul verwenden. Diese Funktion gibt ein neues leeres Deque-Objekt zurück, mit dem Sie eine doppelendige Warteschlange implementieren können.

Hier ist ein Beispiel für die Erstellung eines leeren Deque-Objekts:

from collections import deque 

my_deque = deque() 

Sie können auch eine Deque mit Anfangselementen erstellen, indem Sie eine Iterable (Liste, Tupel usw.) an die Funktion deque() übergeben. Die Deque wird mit den Elementen in der Iterable von links nach rechts initialisiert.

Hier ist ein Beispiel:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

Initialisieren einer Deque mit Elementen

Sie können eine leere Deque auch mit verschiedenen Methoden mit Elementen initialisieren. Eine Möglichkeit, dies zu tun, besteht darin, die Methoden append() und appendleft() zu verwenden , um Elemente von der rechten bzw. linken Seite zur Deque hinzuzufügen.

Hier ist ein Beispiel:

from collections import deque

#Initialize the empty deque
my_deque = deque()
print(my_deque)

#Add Values to the deque
my_deque.append(1) 
my_deque.append(2) 
my_deque.appendleft(3) 

print(my_deque)

Nach der Ausführung dieses Codes enthält die Deque die Elemente [3, 1, 2].

Eine andere Möglichkeit, eine Deque mit Elementen zu initialisieren, besteht darin, eine Liste von Elementen an die Funktion deque() zu übergeben .

Hier ist ein Beispiel:

from collections import deque

my_deque = deque([1, 2, 3]) 

Wenn Sie diesen Code ausführen, wird ein Deque-Objekt erstellt, das die Elemente [1, 2, 3] enthält .

Insgesamt ist das Erstellen und Initialisieren einer Deque in Python unkompliziert und kann mit der integrierten Funktion deque() durchgeführt werden . Sie können dies auch tun, indem Sie mit den Methoden append() und appendleft() Elemente zu einer leeren Deque hinzufügen .

So führen Sie allgemeine Deque-Operationen durch

Es gibt viele Operationen, die Sie in Python für Deque-Objekte ausführen können. Schauen wir uns einige der beliebtesten an.

Elemente zu einer Deque hinzufügen

Mit den Methoden append() und appendleft() können Sie Elemente zu einer Python- Deque hinzufügen . Die Methode append() fügt ein Element am rechten Ende der Doppelschlange hinzu, während die Methode appendleft() ein Element am linken Ende der Doppelschlange hinzufügt.

Hier ist ein Beispiel:

import collections 

# Create an empty deque 
my_deque = collections.deque() 

# Add elements to the deque 
my_deque.append(1) 
my_deque.appendleft(2) 
my_deque.append(3) 

print(my_deque) 

# Output: 
deque([2, 1, 3])

Adding Multiple Data Elements to A Deque

If you don’t want to add data elements to a deque one by one, you can speed up the process with the extend() or extendleft() functions. These functions take in an iterable and append the iterable’s content to the end or left end of the deque respectively.

Here’s an example:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

#Creating a tuple and list
cont = (11, 12, 13, 14)
full = [10,20,30]

#Extending the deque from the right
my_deque.extend(cont)
print(my_deque)

#Extending the deque from the left
my_deque.extendleft(full)
print(my_deque)

In the code above the extend() function appends the multiple values in the cont tuple to the end of the deque. Next, the extendleft() function appends the multiple data elements in the full list to the left end of the deque.

Removing Elements from a Deque

You can remove elements from a Python deque using the pop() and popleft() methods. The pop() method removes and returns the rightmost element of the deque while the popleft() method removes and returns the leftmost element of the deque.

Here’s an example:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

#Remove elements from the deque 
my_deque.pop() 
my_deque.popleft() 

print(my_deque) 

# Output: deque([2, 3, 4])

You can also remove a specific value from a deque using the remove() function. The function removes the first occurrence of the specified value from the deque.

Here’s an example:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 1, 4, 5]) 

#Remove elements from the deque 
my_deque.remove(1)

print(my_deque) 

# Output: deque([2, 1, 4, 5])

If the element is not found, Python will return a ValueError.

Removing All Elements From a Deque

To remove all the elements from a Deque and return it to an empty state, we can use the clear() function. Here’s how it works:

from collections import deque 

#Create a deque with some elements 
my_deque = deque([1, 2, 1, 4, 5]) 

#Remove all elements from the deque 
my_deque.clear()

print(my_deque) 

# Output: 
deque([])

Accessing Elements of a Deque

You can access elements of a Python deque using the indexing operator []. You can also use a negative value in the indexing operator to access the deque elements from the right.

The indexing starts from 0 for the leftmost element and -1 for the rightmost element. Here’s an example:

import collections 

# Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

# Access elements of the deque 
print(my_deque[0]) 
# Output: 1 

print(my_deque[-1]) 
# Output: 5 

Modifying Elements of a Deque

You can modify elements of a Python deque using the indexing operator “[]” and the assignment operator “=“. Here’s an example:

from collections import deque

# Create a deque with some elements 
my_deque = deque([1, 2, 3, 4, 5]) 
print(my_deque)

# Modify elements of the deque 
my_deque[0] = 10 
my_deque[-1] = 50 

print(my_deque) 

In the above code, the indexing operator changes the first and last elements of the deque to 10 and 50 respectively.

These are the basic operations you can perform on a deque object in Python. With these operations, you can efficiently implement various data structures such as queues, stacks, and more.

How to Work with a Deque as a Queue

You can use a deque in Python to implement a queue data structure. A queue is an abstract data type that operates on a first in first out (FIFO) basis.

What this means is that you can append new items from one end of the queue and push out old items from the other end.

A good way to explain this is a line at a store. Typically, the first person to arrive will be at the head of the line and will be attended to first.

New arrivals will have to head to the back of the line and wait their turn. So, the first in will be the first answered, while the last in will be the last attended to.

Here’s how you can use a deque to implement queues.

Using append() and popleft() Methods

Um eine Deque als Warteschlange zu verwenden, können Sie mit der Methode append() Elemente am rechten Ende der Deque hinzufügen. Darüber hinaus können Sie die Methode popleft() verwenden , um Elemente vom linken Ende der Deque zu entfernen.

Dies ist eine sehr effiziente Möglichkeit, eine Warteschlange in Python zu implementieren. Hier ist ein Beispiel:

from collections import deque 

queue = deque() 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print(queue) 
# Output: deque([1, 2, 3]) 

x = queue.popleft() 
print(x) 
# Output: 1 

print(queue) 
# Output: deque([2, 3]) 

Wie Sie sehen können, fügt die Methode append() Elemente am rechten Ende der Doppelschlange hinzu und die Methode popleft() entfernt Elemente vom linken Ende der Doppelschlange.

Das ist genau das, was wir in einer Warteschlangenimplementierung brauchen.

Überprüfen, ob eine Deque-Warteschlange leer ist

Um zu überprüfen, ob eine Deque leer ist, können Sie den Not- Operator verwenden. Hier ist ein Beispiel:

from collections import deque 

queue = deque() 
if not queue: 
   print("Queue is empty") 
else: 
   print("Queue is not empty") 

Dadurch wird „ Warteschlange ist leer “ ausgegeben, da die Doppelschlange leer ist. Wenn Sie Elemente zur Deque hinzufügen, ist diese nicht mehr leer.

Zusammenfassend lässt sich sagen, dass die Verwendung einer Deque als Warteschlange in Python sehr effizient und einfach zu implementieren ist.

Arbeiten mit Deque als Stack

Ebenso wie Warteschlangen sind Stapel ein weiteres Beispiel für abstrakte Datentypen, die Sie zum Organisieren von Daten verwenden können. Im Gegensatz zu Warteschlangen arbeiten Stapel nach dem LIFO-Prinzip (Last In First Out).

Dies bedeutet, dass das letzte Element in der Deque das erste Element ist, das es verlässt. So können Sie dies mithilfe der zugrunde liegenden Datenstruktur implementieren.

Verwendung der Methoden append() und pop()

Wenn Sie Deque als Stapel verwenden, können Sie mit der Methode append() Elemente oben im Stapel hinzufügen . Diese Methode fügt das Element am rechten Ende der Deque hinzu.

Ebenso können Sie mit der Methode pop() Elemente vom oberen Rand des Stapels entfernen . Diese Methode entfernt das Element ganz rechts aus der Deque und gibt es zurück.

Nehmen wir zum Beispiel an, Sie haben eine Deque mit dem Namen „ my_stack “ und möchten oben im Stapel ein Element hinzufügen. Sie können den folgenden Code verwenden:

 my_stack.append(5) 

Dadurch wird das Element 5 oben im Stapel hinzugefügt.

Wenn Sie das oberste Element vom Stapel entfernen möchten, können Sie die Methode pop() verwenden: `

bal = my_stack.pop() 

print(bal)
# Output: 5

Dadurch wird das ganz rechte Element der Deque entfernt und zurückgegeben, in diesem Fall 5.

Auf ein leeres Deque-Objekt prüfen

Sie können überprüfen, ob ein Deque-Stack leer ist, indem Sie den booleschen Operator „ not “ verwenden. Wenn die Deque leer ist, gibt „ not my_deque “ True zurück . Andernfalls wird False zurückgegeben .

Nehmen wir zum Beispiel an, Sie haben einen Deque-Stack mit dem Namen „ my_deque “ und möchten prüfen, ob er leer ist. Sie können den folgenden Code verwenden:

if not my_deque: 
   print("The deque is empty") 

else: 
   print("The deque is not empty") 

Dies wird „ Die Deque ist leer “ ausgeben, wenn die Deque leer ist. Wenn es nicht leer ist, lautet die Ausgabe „ Die Deque ist nicht leer “.

Wenn Sie mit Deque als Stapel arbeiten, ist es wichtig, den Überblick darüber zu behalten, ob der Stapel leer ist oder nicht. Wenn Sie versuchen, ein Element aus einem leeren Stapel zu entfernen, erhalten Sie einen IndexError .

Was ist eine eingeschränkte Deque?

Eine eingeschränkte Deque ist eine doppelendige Warteschlange mit einigen Einschränkungen für Datenanhänge- und Popup-Vorgänge an beiden Enden der Deque. Es gibt zwei Haupttypen von eingeschränkten Deques; Eingabebeschränkte Deques und ausgabebeschränkte Deques

Schauen wir sie uns an:

Eingabebeschränkte Deque

Mit einer eingabebeschränkten Deque können Sie Datenelemente an beiden Enden der Deque entfernen oder entfernen. Sie können Datenelemente jedoch nur von einem Ende der Doppelschlange einfügen.

Dies ist sehr nützlich bei Anwendungen mit Speicherbeschränkungen. Sie können damit Datenelemente in chronologischer Reihenfolge hinzufügen und gleichzeitig die Möglichkeit behalten, Daten von jedem Ende der Warteschlange zu verwerfen.

Ausgabebeschränkte Deque

Mit einer ausgabebeschränkten Deque können Sie Daten von beiden Enden der Deque einfügen. Sie können Elemente jedoch nur von einem Ende der Deque, dem sogenannten Frontend, löschen.

Eine ausgabebeschränkte Deque ist in Fällen sehr nützlich, in denen Sie eine FIFO-Datenstruktur implementieren müssen, aber dennoch die Funktionalität zum Anhängen von Daten von beiden Enden wünschen.

Lassen Sie uns das abschließen

Inzwischen sollten Sie ein gutes Verständnis des Deque-Moduls in Python haben und wissen, wie es zur Implementierung effizienter Warteschlangen und Stapel verwendet werden kann.

Deques sind eine vielseitige Datenstruktur, die viele Vorteile gegenüber herkömmlichen Listen bietet. Diese Vorteile werden deutlich, wenn es um speichereffiziente Anhänge- und Pop-Vorgänge geht.

Sie sind auch eine gute Wahl, wenn Sie einen Stack oder eine doppelendige Warteschlange implementieren müssen. Zu den wichtigsten Vorteilen der Verwendung von Deques gehören:

• Effiziente O(1)-Anhänge- und Popup-Operationen von beiden Enden der Deque

• Schneller O(1)-Zugriff auf das erste und letzte Element der Deque

• Integrierte Unterstützung für threadsichere, atomare Operationen

• Flexible Methoden zum Einfügen, Entfernen und Drehen von Elementen in die Deque

Insgesamt ist das Deque-Modul ein leistungsstarkes Tool, mit dem Sie effizienteren und wartbareren Python-Code schreiben können. Unabhängig davon, ob Sie an einem kleinen Skript oder einem Großprojekt arbeiten, sind Deques als Alternative zu herkömmlichen Listen oder anderen Datenstrukturen auf jeden Fall eine Überlegung wert!

Wenn Sie mehr über Python erfahren möchten, schauen Sie sich unsere Playlist unten an