Deque en Python - Tutoriel avec exemples

Si vous êtes un développeur Python, vous avez probablement entendu parler d'une deque, ou "file d'attente à double extrémité". C'est un outil puissant qui peut augmenter l'efficacité de votre application et accélérer ses performances.

Un deque est un type de données de conteneur spécialisé qui offre des opérations d'ajout et de pop plus rapides à partir des deux extrémités du conteneur. Cela en fait un outil précieux pour implémenter des files d'attente et des piles, qui sont des types de données courants de type liste en informatique.

C'est une structure de données de bas niveau et hautement optimisée qui est très utile pour une variété d'applications. En tant que programmeur Python, un deque est un outil que vous voudrez avoir dans votre arsenal.

Continuez à lire pour en savoir plus sur Deques et comment vous pouvez les implémenter dans votre code Python !

Table des matières

• Qu'est-ce qu'un Deque ?
  • Caractéristiques d'un Python Deque
  • Applications de A Deque
• Comment créer et initialiser un Deque
  • Utilisation de la fonction deque()
  • Initialiser un Deque avec des éléments
• Comment effectuer des opérations Deque courantes
  • Ajouter des éléments à un Deque
  • Ajout de plusieurs éléments de données à un Deque
  • Supprimer des éléments d'un Deque
  • Suppression de tous les éléments d'un Deque
  • Accéder aux éléments d'un Deque
  • Modification des éléments d'un Deque
• Comment travailler avec un Deque en tant que file d'attente
  • Utilisation des méthodes append() et popleft()
  • Vérifier si une file d'attente Deque est vide
• Travailler avec Deque comme une pile
  • Utilisation des méthodes append() et pop()
  • Recherche d'un objet Deque vide
• Qu'est-ce qu'un Deque restreint ?
  • • Entrée restreinte Deque
    • Sortie restreinte Deque
• Enveloppons ça

Qu'est-ce qu'un Deque ?

Si vous débutez en Python ou en programmation informatique en général, vous vous demandez peut-être ce qu'est un deque. Deque signifie « file d'attente à double extrémité », et c'est une structure de données qui vous permet d'ajouter et de supprimer des éléments des deux extrémités de la file d'attente.

C'est similaire à une file d'attente normale, mais avec la flexibilité supplémentaire de pouvoir ajouter et supprimer des éléments à la fois au début et à la fin de la file d'attente. Ceci est possible car le deque de Python est implémenté sous la forme d'une liste doublement liée.

En Python, deques est implémenté à l'aide du module collections, qui fournit une classe deque. Cette classe fournit un certain nombre de méthodes pour ajouter et supprimer des éléments de la deque.

Il fournit également des fonctions pour d'autres opérations utiles telles que la rotation du deque ou son effacement complet.

Caractéristiques d'un Python Deque

Contrairement à une liste régulière, qui a une complexité temporelle O (n) pour les opérations d'ajout et de pop, un deque fournit une complexité temporelle O (1). Cela le rend beaucoup plus rapide et économe en mémoire pour ces opérations de lecture et d'écriture.

Voici quelques autres fonctionnalités de Python deque que vous devriez connaître :

• C'est une structure de données mutable.

• Il peut stocker plusieurs types de données, par exemple des entiers, des tuples, des tableaux, etc.

• Il prend en charge l'indexation, mais pas les opérations de découpage.

• Il ne prend pas en charge le tri sur place

• Il prend en charge les fonctions et opérations itérables intégrées courantes telles que in , sorted() , len() , reverse() , etc.

Applications de A Deque

Les deques sont utiles pour diverses raisons. Par exemple, ils peuvent être utilisés pour implémenter une file d'attente ou une pile, qui sont toutes deux des structures de données courantes en informatique.

Ils peuvent également être utilisés pour traiter efficacement les données en temps réel, comme dans les applications de streaming ou dans les systèmes qui nécessitent un accès rapide aux données.

En plus d'être utilisé pour les files d'attente et les piles, deques peut également être utilisé pour implémenter des algorithmes de recherche en largeur d'abord. Ils sont également utiles pour maintenir une fenêtre glissante d'éléments dans une plus grande séquence.

Comment créer et initialiser un Deque

Vous pouvez créer un deque en utilisant une fonction intégrée du module collections. Examinons de près comment vous pouvez créer et remplir cette structure de données.

Utilisation de la fonction deque()

Pour créer un deque en Python, vous pouvez utiliser la fonction intégrée deque() du module collections. Cette fonction renvoie un nouvel objet deque vide que vous pouvez utiliser pour implémenter une file d'attente double.

Voici un exemple de création d'un objet deque vide :

from collections import deque 

my_deque = deque() 

Vous pouvez également créer un deque avec des éléments initiaux en passant un itérable (liste, tuple, etc.) à la fonction deque() . Le deque sera initialisé avec les éléments de l'itérable, de gauche à droite.

Voici un exemple:

from collections import deque

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

Initialiser un Deque avec des éléments

Vous pouvez également initialiser un deque vide avec des éléments en utilisant diverses méthodes. Une façon de faire est d'utiliser les méthodes append() et appendleft() pour ajouter des éléments au deque à partir des côtés droit et gauche, respectivement.

Voici un exemple:

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)

Après avoir exécuté ce code, le deque contiendra les éléments [3, 1, 2].

Une autre façon d'initialiser un deque avec des éléments est de passer une liste d'éléments à la fonction deque() .

Voici un exemple:

from collections import deque

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

L'exécution de ce code créera un objet deque contenant les éléments [1, 2, 3] .

Dans l'ensemble, la création et l'initialisation d'un deque en Python sont simples et peuvent être effectuées à l'aide de la fonction intégrée deque() . Vous pouvez également le faire en ajoutant des éléments à un deque vide à l'aide des méthodes append() et appendleft() .

Comment effectuer des opérations Deque courantes

Il existe de nombreuses opérations que vous pouvez effectuer sur les objets deque en Python. Voyons quelques-uns des plus populaires.

Ajouter des éléments à un Deque

Vous pouvez ajouter des éléments à un deque Python en utilisant les méthodes append() et appendleft() . La méthode append() ajoute un élément à l'extrémité droite du deque tandis que la méthode appendleft() ajoute un élément à l'extrémité gauche du deque.

Voici un exemple :

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])

Ajout de plusieurs éléments de données à un Deque

Si vous ne voulez pas ajouter des éléments de données à un deque un par un, vous pouvez accélérer le processus avec les fonctions extend() ou extendleft() . Ces fonctions acceptent un itérable et ajoutent le contenu de l'itérable à la fin ou à l'extrémité gauche du deque respectivement.

Voici un exemple :

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)

Dans le code ci-dessus, la fonction extend() ajoute les multiples valeurs du cont tuple à la fin de deque. Ensuite, la fonction extendleft() ajoute les multiples éléments de données dans la liste complète à l'extrémité gauche du deque.

Supprimer des éléments d'un Deque

Vous pouvez supprimer des éléments d'un deque Python en utilisant les méthodes pop() et popleft() . La méthode pop() supprime et renvoie l'élément le plus à droite du deque tandis que la méthode popleft() supprime et renvoie l'élément le plus à gauche du deque.

Voici un exemple :

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])

Vous pouvez également supprimer une valeur spécifique d'un deque en utilisant la fonction remove() . La fonction supprime la première occurrence de la valeur spécifiée de la deque.

Voici un exemple :

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])

Si l'élément n'est pas trouvé, Python renverra une ValueError .

Suppression de tous les éléments d'un Deque

Pour supprimer tous les éléments d'un Deque et le remettre dans un état vide, nous pouvons utiliser la fonction clear() . Voici comment cela fonctionne:

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

Pour utiliser un deque comme file d'attente, vous pouvez utiliser la méthode append() pour ajouter des éléments à l'extrémité droite du deque. De plus, vous pouvez utiliser la méthode popleft() pour supprimer des éléments de l'extrémité gauche de la deque.

C'est un moyen très efficace d'implémenter une file d'attente en Python. Voici un exemple:

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]) 

Comme vous pouvez le voir, la méthode append() ajoute des éléments à l'extrémité droite du deque, et la méthode popleft() supprime les éléments de l'extrémité gauche du deque.

C'est exactement ce dont nous avons besoin dans une implémentation de file d'attente.

Vérifier si une file d'attente Deque est vide

Pour vérifier si un deque est vide, vous pouvez utiliser l' opérateur not . Voici un exemple:

from collections import deque 

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

Cela affichera " La file d'attente est vide " car le deque est vide. Si vous ajoutez des éléments au deque, il ne sera plus vide.

En conclusion, utiliser un deque comme file d'attente en Python est très efficace et facile à mettre en œuvre.

Travailler avec Deque comme une pile

Tout comme les files d'attente, les piles sont un autre exemple de types de données abstraits que vous pouvez utiliser pour organiser les données. Contrairement aux files d'attente, les piles fonctionnent selon le mode dernier entré, premier sorti (LIFO).

Cela signifie que le dernier élément dans le deque sera le premier élément sorti. Voici comment vous pouvez implémenter cela en utilisant la structure de données sous-jacente.

Utilisation des méthodes append() et pop()

Lorsque vous utilisez Deque en tant que pile, vous pouvez ajouter des éléments au sommet de la pile à l'aide de la méthode append() . Cette méthode ajoute l'élément à l'extrémité droite du deque.

De même, vous pouvez supprimer des éléments du haut de la pile à l'aide de la méthode pop() . Cette méthode supprime et renvoie l'élément le plus à droite du deque.

Par exemple, disons que vous avez un deque appelé " my_stack " et que vous voulez ajouter un élément au sommet de la pile. Vous pouvez utiliser le code suivant :

 my_stack.append(5) 

Cela ajoutera l'élément 5 au sommet de la pile.

Si vous souhaitez supprimer l'élément supérieur de la pile, vous pouvez utiliser la méthode pop() : `

bal = my_stack.pop() 

print(bal)
# Output: 5

Cela supprimera et renverra l'élément le plus à droite du deque, qui dans ce cas est 5.

Recherche d'un objet Deque vide

Vous pouvez vérifier si une pile deque est vide en utilisant l'opérateur booléen « not ». Si le deque est vide, « not my_deque » renverra True . Sinon, il retournera False .

Par exemple, supposons que vous ayez une pile deque appelée « my_deque » et que vous vouliez vérifier si elle est vide. Vous pouvez utiliser le code suivant :

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

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

Cela affichera « Le deque est vide » si le deque est vide. S'il n'est pas vide, la sortie sera « Le deque n'est pas vide ».

Lorsque vous travaillez avec Deque en tant que pile, il est important de savoir si la pile est vide ou non. Si vous essayez d'extraire un élément d'une pile vide, vous obtiendrez une IndexError .

Qu'est-ce qu'un Deque restreint ?

Un deque restreint est une file d'attente à double extrémité avec certaines restrictions placées sur les opérations d'ajout et de pop de données à chaque extrémité du deque. Il existe deux principaux types de deques restreintes; Entrée restreinte deque et sortie restreinte deques

Regardons-les :

Entrée restreinte Deque

Un deque à entrée restreinte vous permet de faire apparaître ou de supprimer des éléments de données des deux extrémités du deque. Cependant, vous ne pouvez insérer des éléments de données qu'à partir d'une extrémité du deque.

Ceci est très utile dans les applications avec des contraintes de mémoire. Vous pouvez l'utiliser pour ajouter des éléments de données dans l'ordre chronologique tout en conservant la possibilité de supprimer des données à n'importe quelle fin de la deque.

Sortie restreinte Deque

Un deque à sortie restreinte vous permet d'insérer des données des deux extrémités du deque. Cependant, vous ne pouvez supprimer des éléments qu'à une extrémité de la deque appelée le front-end.

Un deque à sortie restreinte est très utile dans les cas où vous devez implémenter une structure de données FIFO, mais souhaitez toujours que la fonctionnalité ajoute des données des deux extrémités.

Enveloppons ça

À présent, vous devriez avoir une bonne compréhension du module deque en Python et de la manière dont il peut être utilisé pour implémenter des files d'attente et des piles efficaces.

Deques est une structure de données polyvalente qui offre de nombreux avantages par rapport aux listes traditionnelles. Ces avantages sont évidents lorsqu'il s'agit d'opérations d'ajout et de pop économes en mémoire.

Ils constituent également un excellent choix lorsque vous devez implémenter une pile ou une file d'attente à double extrémité. Certains des principaux avantages de l'utilisation de deques incluent :

• Opérations d'ajout et de pop O(1) efficaces aux deux extrémités de la deque

• Accès rapide O(1) aux premier et dernier éléments de la deque

• Prise en charge intégrée des opérations atomiques thread-safe

• Méthodes flexibles pour insérer, retirer et faire pivoter des éléments dans le deque

Dans l'ensemble, le module deque est un outil puissant qui peut vous aider à écrire du code Python plus efficace et maintenable. Que vous travailliez sur un petit script ou sur un projet à grande échelle, les deques valent vraiment la peine d'être considérées comme une alternative aux listes traditionnelles ou à d'autres structures de données !

Prêt à en savoir plus sur Python, consultez notre liste de lecture ci-dessous