collections. deque
Une file à double extrémité : ajout et retrait rapides d’éléments aux deux bouts, avec une limite de longueur facultative.
- Renvoie
- Un objet
deque.
Exemple
#from collections import deque
queue = deque(["Léa", "Jean"])
queue.append("Mia")
queue.appendleft("Zoé")
print(queue)
print(queue.popleft())
print(queue.pop())
print(queue, len(queue))Définition et utilisation
#La classe deque (de « double-ended queue », une file à double extrémité) du module collections fonctionne comme une liste optimisée pour les opérations aux deux bouts. Les méthodes append() et pop() agissent sur l’extrémité droite, et appendleft() et popleft() sur la gauche. Chacune s’exécute en temps constant, quelle que soit la longueur de la file.
Une liste ordinaire possède aussi pop(0) et insert(0, x), mais ces opérations décalent tous les autres éléments, et sont donc lentes sur de grandes listes. C’est pourquoi les files de tâches, le parcours de graphe en largeur (BFS) ou un tampon des derniers événements se construisent sur deque.
Le paramètre maxlen limite la longueur : lorsque la file est pleine, l’ajout d’un élément d’un côté supprime un élément du côté opposé. C’est une méthode toute faite pour garder par exemple les derniers résultats. La méthode rotate(n) décale les éléments en cercle de n positions. L’accès par indice fonctionne, mais au milieu d’une longue file il est plus lent que dans une liste, et les tranches ne sont pas prises en charge.
Syntaxe
#from collections import deque
deque(iterable, maxlen=None)
file.append(x)
file.appendleft(x)
file.pop()
file.popleft()
file.rotate(n)Paramètres
#iterable
collection, facultative
Les éléments initiaux de la file.maxlen
int ou None, None par défaut
La longueur maximale. Une fois dépassée, les éléments de l’extrémité opposée sont supprimés.
Plus d’exemples
#from collections import deque
recent = deque(maxlen=3)
for score in [72, 95, 64, 88, 91]:
recent.append(score)
print(list(recent))
print(recent)
print(sum(recent) / len(recent))from collections import deque
tasks = deque(["1_1", "1_2", "1_3"])
while tasks:
task = tasks.popleft()
print("Vérification de", task)
players = deque(["Léa", "Jean", "Mia"])
players.rotate(1)
print(players)
players.rotate(-2)
print(players)from collections import deque
paths = {
"Égypte": ["Espace", "Rome"],
"Espace": ["Parc jurassique"],
"Rome": ["Safari"],
"Parc jurassique": ["Safari"],
"Safari": [],
}
def shortest(start, goal):
queue = deque([[start]])
seen = {start}
while queue:
route = queue.popleft()
if route[-1] == goal:
return route
for neighbor in paths[route[-1]]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(route + [neighbor])
return None
print(shortest("Égypte", "Safari"))Bonnes pratiques
#- Lorsque vous retirez souvent des éléments au début d’une liste avec
pop(0), remplacez-la par unedequeet utilisezpopleft(). dequene prend pas en charge les tranches, par exemplefile[1:3]. Si vous en avez besoin, transformez la file en liste ou utilisezitertools.islice().- Une file vide est fausse dans les conditions, donc une boucle
while queue:s’exécute tant qu’il reste des éléments.
Entrées associées
#- list.pop()Supprime l’élément à l’indice donné (le dernier par défaut) et le renvoie.
- list.append()Ajoute un seul élément à la fin d’une liste.
- list.insert()Insère un élément à une position choisie dans une liste.
- collections.CounterUn dictionnaire pour compter : pour chaque élément, il garde le nombre de ses occurrences.
- itertoolsDes outils pour travailler avec les itérateurs : chaînage, regroupement, combinaisons et suites infinies.
Vous voyez une erreur ou il manque un exemple ? Écrivez-nous.