Python Language
Module Deque
Recherche…
Syntaxe
- dq = deque () # Crée un deque vide
- dq = deque (iterable) # Crée un deque avec des éléments
- dq.append (object) # Ajoute un objet à droite de la deque
- dq.appendleft (object) # Ajoute un objet à gauche de la deque
- dq.pop () -> objet # Supprime et retourne l'objet le plus à droite
- dq.popleft () -> object # Supprime et renvoie l'objet le plus à gauche
- dq.extend (itérable) # Ajoute quelques éléments à droite du deque
- dq.extendleft (iterable) # Ajoute des éléments à la gauche du deque
Paramètres
| Paramètre | Détails |
|---|---|
iterable | Crée le deque avec les éléments initiaux copiés à partir d'une autre itération. |
maxlen | Limite la taille du déque, en repoussant les anciens éléments à mesure que de nouveaux éléments sont ajoutés. |
Remarques
Cette classe est utile lorsque vous avez besoin d'un objet similaire à une liste qui permet des opérations rapides d'ajout et d'ajout d'un côté ou de l'autre (le nom deque signifie « file d'attente double »).
Les méthodes fournies sont en effet très similaires, sauf que certaines, comme pop , append ou extend peuvent être suffixées par left . La structure de données deque doit être préférée à une liste si l'on doit fréquemment insérer et supprimer des éléments aux deux extrémités car cela permet de le faire à temps constant O (1).
Deque de base en utilisant
Les principales méthodes utiles avec cette classe sont popleft et appendleft
from collections import deque
d = deque([1, 2, 3])
p = d.popleft() # p = 1, d = deque([2, 3])
d.appendleft(5) # d = deque([5, 2, 3])
limiter la taille de deque
Utilisez le paramètre maxlen lors de la création d'un deque pour limiter la taille du deque:
from collections import deque
d = deque(maxlen=3) # only holds 3 items
d.append(1) # deque([1])
d.append(2) # deque([1, 2])
d.append(3) # deque([1, 2, 3])
d.append(4) # deque([2, 3, 4]) (1 is removed because its maxlen is 3)
Méthodes disponibles dans deque
Créer un deque vide:
dl = deque() # deque([]) creating empty deque
Créer deque avec quelques éléments:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Ajouter un élément à deque:
dl.append(5) # deque([1, 2, 3, 4, 5])
Ajout de l'élément côté gauche de deque:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Ajouter une liste d'éléments à deque:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Ajout de la liste des éléments du côté gauche:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
L' .pop() élément .pop() supprime naturellement un élément du côté droit:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
Utiliser l'élément .popleft() pour supprimer un élément du côté gauche:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Supprimer l'élément par sa valeur:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
Inverser l'ordre des éléments dans deque:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])
Largeur Première Recherche
Le Deque est la seule structure de données Python avec des opérations de file d'attente rapides. (Remarque queue.Queue n'est normalement pas approprié, car il est destiné à la communication entre les threads.) Un cas d'utilisation de base d'une file d'attente est la première recherche .
from collections import deque
def bfs(graph, root):
distances = {}
distances[root] = 0
q = deque([root])
while q:
# The oldest seen (but not yet visited) node will be the left most one.
current = q.popleft()
for neighbor in graph[current]:
if neighbor not in distances:
distances[neighbor] = distances[current] + 1
# When we see a new node, we add it to the right side of the queue.
q.append(neighbor)
return distances
Disons que nous avons un graphique simple dirigé:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
Nous pouvons maintenant trouver les distances depuis une position de départ:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}
