Python Deque : Files à Double Extrémité Rapides avec collections.deque

Name

Soren Atelier

Updated on 10/02/2026

Utiliser une liste Python comme file d'attente ou pile semble naturel -- jusqu'à ce que vous commenciez à retirer des éléments du côté gauche. Appeler list.pop(0) est une opération O(n) car chaque élément restant doit se décaler d'une position vers l'avant. Dans une boucle qui traite des millions d'éléments, ce coût caché transforme un pipeline rapide en escargot. Le même problème affecte list.insert(0, x), qui est aussi O(n). Pour toute charge de travail qui touche les deux extrémités d'une séquence, les listes simples deviennent un piège de performance.

collections.deque de Python (file à double extrémité, prononcé "dek") résout ce problème en fournissant des opérations append et pop O(1) aux deux extrémités. Elle est implémentée comme une liste doublement chaînée de blocs de taille fixe, offrant une performance en temps constant à chaque extrémité tout en supportant l'accès indexé. Ce guide couvre tout ce que vous devez savoir sur deque : création, opérations principales, files limitées, sécurité des threads et modèles pratiques.

Créer une Deque

from collections import deque
 
d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])
 
letters = deque("hello")
print(letters)  # deque(['h', 'e', 'l', 'l', 'o'])
 
d = deque()
 
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)
print(d)  # deque([2, 3, 4], maxlen=3)

Opérations Principales

Deque fournit des opérations symétriques pour les deux extrémités de la séquence.

from collections import deque
 
d = deque([2, 3, 4])
 
d.append(5)
d.appendleft(1)
print(d)  # deque([1, 2, 3, 4, 5])
 
right = d.pop()
left = d.popleft()
print(right)  # 5
print(left)   # 1
 
d = deque([3, 4, 5])
d.extend([6, 7, 8])
d.extendleft([2, 1, 0])
print(d)  # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

Notez que extendleft traite les éléments un par un, insérant chacun en position 0. L'ordre résultant est inversé par rapport à l'itérable d'entrée.

Autres Méthodes Utiles

from collections import deque
 
d = deque([1, 2, 3, 2, 4, 2, 5])
 
print(d.count(2))   # 3
print(d.index(3))   # 2
d.remove(2)
d.insert(1, 99)
d.reverse()
d.clear()

Rotation avec rotate()

La méthode rotate() fait tourner la deque de n pas vers la droite. Un n négatif tourne vers la gauche.

from collections import deque
 
d = deque([1, 2, 3, 4, 5])
 
d.rotate(2)
print(d)       # deque([4, 5, 1, 2, 3])
 
d.rotate(-3)
print(d)       # deque([2, 3, 4, 5, 1])

Deques Limitées avec maxlen

Les deques limitées sont l'une des fonctionnalités les plus pratiques. En définissant maxlen, vous créez un tampon de taille fixe qui évacue automatiquement les éléments les plus anciens quand la capacité est atteinte.

Fenêtre Glissante / Moyenne Mobile

from collections import deque
 
def moving_average(data, window_size):
    """Calculate moving average using a bounded deque."""
    window = deque(maxlen=window_size)
    averages = []
    for value in data:
        window.append(value)
        if len(window) == window_size:
            averages.append(sum(window) / window_size)
    return averages
 
prices = [100, 102, 104, 103, 105, 107, 106, 108, 110, 109]
print(moving_average(prices, 3))

Fin d'un Fichier (N Dernières Lignes)

from collections import deque
 
def tail(filename, n=10):
    """Return the last n lines of a file."""
    with open(filename) as f:
        return deque(f, maxlen=n)

Deque comme File d'Attente (FIFO)

from collections import deque
 
queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")
 
print(queue.popleft())    # first
print(queue.popleft())    # second
print(queue.popleft())    # third

C'est là que deque brille vraiment par rapport à une liste. Avec une liste, list.pop(0) est O(n). Avec deque, popleft() est O(1).

Deque comme Pile (LIFO)

from collections import deque
 
stack = deque()
stack.append("first")
stack.append("second")
stack.append("third")
 
print(stack.pop())    # third
print(stack.pop())    # second
print(stack.pop())    # first

Comparaison de Performance : Deque vs Liste

Benchmark

from collections import deque
import time
 
def benchmark_left_operations(n):
    """Compare popleft/appendleft performance."""
    data = list(range(n))
    start = time.perf_counter()
    while data:
        data.pop(0)
    list_time = time.perf_counter() - start
 
    data = deque(range(n))
    start = time.perf_counter()
    while data:
        data.popleft()
    deque_time = time.perf_counter() - start
 
    print(f"n={n:>8,}")
    print(f"  list.pop(0):     {list_time:.4f}s")
    print(f"  deque.popleft(): {deque_time:.4f}s")
    print(f"  Speedup: {list_time / deque_time:.1f}x")
 
benchmark_left_operations(100_000)

Sécurité des Threads

deque de Python fournit des opérations append(), appendleft(), pop() et popleft() thread-safe. Ces méthodes sont atomiques dans CPython car elles s'exécutent dans une seule instruction bytecode, protégées par le GIL.

Pour les systèmes de production nécessitant un comportement bloquant, utilisez queue.Queue à la place.

Modèles Pratiques

Parcours BFS de Graphe

from collections import deque
 
def bfs(graph, start):
    """Breadth-first search using deque as queue."""
    visited = set()
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(
                neighbor for neighbor in graph[node]
                if neighbor not in visited
            )
    return order
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Maximum par Fenêtre Glissante

from collections import deque
 
def sliding_window_max(nums, k):
    """Find maximum in each sliding window of size k."""
    result = []
    window = deque()
    for i, num in enumerate(nums):
        while window and window[0] < i - k + 1:
            window.popleft()
        while window and nums[window[-1]] < num:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result
 
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))
# [3, 3, 5, 5, 6, 7]

Historique d'Annulation

Une deque limitée fait un excellent historique d'annulation qui oublie automatiquement les actions les plus anciennes :

from collections import deque
 
class TextEditor:
    def __init__(self, max_undo=50):
        self.content = ""
        self._undo_stack = deque(maxlen=max_undo)
 
    def type_text(self, text):
        self._undo_stack.append(self.content)
        self.content += text
 
    def delete_last(self, n=1):
        self._undo_stack.append(self.content)
        self.content = self.content[:-n]
 
    def undo(self):
        if self._undo_stack:
            self.content = self._undo_stack.pop()
 
editor = TextEditor(max_undo=10)
editor.type_text("Hello")
editor.type_text(" World")
print(editor.content)   # Hello World
editor.undo()
print(editor.content)   # Hello

Tester les Performances des Structures de Données dans Jupyter

Lors du benchmarking de deques contre des listes ou de l'ajustement de maxlen pour votre charge de travail spécifique, les notebooks interactifs sont inestimables. RunCell (opens in a new tab) fournit un environnement Jupyter alimenté par l'IA où vous pouvez profiler les opérations sur les structures de données, visualiser les différences de performance et obtenir des suggestions intelligentes d'optimisation.

FAQ

Qu'est-ce qu'une deque en Python ?

Une deque (file à double extrémité) est une structure de données du module collections de Python qui supporte les opérations append et pop O(1) aux deux extrémités. Contrairement à une liste, qui prend O(n) pour insérer ou retirer du début, une deque offre une performance en temps constant aux deux extrémités.

Quand utiliser deque au lieu de list ?

Utilisez deque quand vous avez besoin d'insertion ou de suppression rapide aux deux extrémités, comme pour implémenter des files (FIFO), maintenir des fenêtres glissantes ou faire des parcours BFS. Restez avec list quand vous avez besoin d'accès aléatoire rapide par index (O(1) pour liste vs O(n) pour deque).

Python deque est-il thread-safe ?

Oui, les méthodes append(), appendleft(), pop() et popleft() sont thread-safe dans CPython. Ces opérations sont atomiques car elles se complètent dans une seule instruction bytecode, protégées par le GIL. Cependant, les opérations composées ne sont pas atomiques, utilisez donc queue.Queue pour les patterns producteur-consommateur nécessitant une sémantique bloquante.

Que fait maxlen dans deque ?

Le paramètre maxlen crée une deque limitée avec une taille maximale fixe. Quand la deque est pleine et qu'un nouvel élément est ajouté, l'élément à l'extrémité opposée est automatiquement supprimé. C'est utile pour implémenter des fenêtres glissantes, des journaux d'activité récente et des historiques d'annulation.

Comment deque se compare-t-il à queue.Queue ?

collections.deque est conçu pour la vitesse. queue.Queue encapsule une deque en interne mais ajoute des primitives de synchronisation de threads. Utilisez deque pour le code mono-thread. Utilisez queue.Queue quand vous avez besoin d'opérations get() et put() bloquantes dans des scénarios producteur-consommateur multi-threads.

Conclusion

collections.deque de Python est l'une des structures de données les plus utiles mais sous-estimées de la bibliothèque standard. Elle élimine la pénalité O(n) des opérations côté gauche des listes, fournit un tampon limité intégré avec maxlen, offre des opérations atomiques thread-safe et sert de fondation pour les files d'attente, piles, fenêtres glissantes et algorithmes de parcours de graphes.

La décision clé est simple : si votre code touche les deux extrémités d'une séquence, utilisez deque. Si vous avez besoin d'accès aléatoire rapide par index, utilisez list. Pour la plupart des patterns de file d'attente et de pile, deque devrait être votre choix par défaut.