Un deque signifie Double-Ended Queue. Il s'agit d'un type spécial de structure de données qui vous permet d'ajouter et de supprimer efficacement des éléments aux deux extrémités.

Contrairement aux files d'attente normales (qui suivent généralement le premier entré, premier sorti), un deque prend en charge les opérations FIFO et LIFO. Cela le rend très flexible et utile dans les applications du monde réel telles que les problèmes de fenêtre glissante de planification de tâches et le traitement de données en temps réel.

Exemple:

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

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

Pourquoi avons-nous besoin de deque

• Il prend en charge le temps O(1) pour ajouter/supprimer des éléments aux deux extrémités.
• C'est plus efficace que les listes pour les opérations frontales.
• Il peut fonctionner à la fois comme une file d'attente (FIFO) et une pile (LIFO).
• Idéal pour planifier les problèmes de fenêtres coulissantes et le traitement des données en temps réel.
• Il propose de puissantes méthodes intégrées telles que appendleft() popgauche() et tourner().

Types d’entrée Deque restreinte

• Deque restreint en entrée  : La saisie est limitée à une extrémité tandis que la suppression est autorisée aux deux extrémités.
• Sortie restreinte Deque : la sortie est limitée à une extrémité mais l'insertion est autorisée aux deux extrémités.

Opérations sur deque 

Voici un tableau répertoriant les opérations intégrées d'un deque en Python avec des descriptions et leurs complexités temporelles correspondantes :

Rudyard Kipling si explication

Ajout et suppression d'éléments retirés de la file d'attente

• ajouter(x): Ajoute x à l'extrémité droite du deque.
• appendleft(x): Ajoute x à l'extrémité gauche du deque.
• étendre (itérable): Ajoute tous les éléments de l'itérable à l'extrémité droite.
• extendleft (itérable): Ajoute tous les éléments de l'itérable à l'extrémité gauche (dans l'ordre inverse).
• supprimer (valeur): Supprime la première occurrence de la valeur spécifiée du deque. Si la valeur n'est pas trouvée, une ValueError est générée.
• populaire(): Supprime et renvoie un élément de l'extrémité droite.
• popgauche() : Supprime et renvoie un élément de l'extrémité gauche.
• clair(): Supprime tous les éléments du 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) 

Sortir:

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

Accès à l'article et à la longueur du deque

• Indexage: Accédez aux éléments par position à l’aide d’indices positifs ou négatifs.
• seulement(): Renvoie le nombre d'éléments dans le deque.

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 

Compter la rotation et l'inversion d'un deque

• compte(valeur): Cette méthode compte le nombre d'occurrences d'un élément spécifique dans le deque.
• faire pivoter(n): Cette méthode fait pivoter le deque de n étapes. Le n positif tourne vers la droite et le n négatif tourne vers la gauche.
• inverse(): Cette méthode inverse l'ordre des éléments dans le deque.

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