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.
Sur cette page

Exemple

#
Python
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))
Résultatrésultat enregistré, vous pouvez le vérifier
deque(['Zoé', 'Léa', 'Jean', 'Mia'])
Zoé
Mia
deque(['Léa', 'Jean']) 2

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

#
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

#
Les derniers résultats grâce à maxlen
Python
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))
Résultatrésultat enregistré, vous pouvez le vérifier
[72]
[72, 95]
[72, 95, 64]
[95, 64, 88]
[64, 88, 91]
deque([64, 88, 91], maxlen=3)
81.0
Une file de tâches et rotate()
Python
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)
Résultatrésultat enregistré, vous pouvez le vérifier
Vérification de 1_1
Vérification de 1_2
Vérification de 1_3
deque(['Mia', 'Léa', 'Jean'])
deque(['Jean', 'Mia', 'Léa'])
Le plus court chemin, ou parcours en largeur
Python
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"))
Résultatrésultat enregistré, vous pouvez le vérifier
['Égypte', 'Rome', 'Safari']

Bonnes pratiques

#
  • Lorsque vous retirez souvent des éléments au début d’une liste avec pop(0), remplacez-la par une deque et utilisez popleft().
  • deque ne prend pas en charge les tranches, par exemple file[1:3]. Si vous en avez besoin, transformez la file en liste ou utilisez itertools.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

#

Vous voyez une erreur ou il manque un exemple ? Écrivez-nous.