Algorithmes Python

La structure de données file (queue) en Python

Dans cette leçon, vous allez implémenter une file efficace, selon la règle premier entré, premier sorti, avec collections.deque.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

Introduction

Le problème

Les travaux d'impression, les tickets de support et les messages entre programmes doivent être traités dans leur ordre d'arrivée. Une file garde cet ordre, et choisir le bon outil en Python la garde rapide même avec des millions d'éléments.

Imaginez-le ainsi

Une file est comme une file d'attente à un guichet. Les nouveaux arrivants se placent au bout, et la personne de devant est servie en premier. Personne ne double, donc chacun est servi dans l'ordre d'arrivée.

De la file au guichet au code
deque(["first", "second"])🚶🚶 Deux personnes attendent déjà
queue.append("third")🚶 Une nouvelle personne se place au bout
queue.popleft()🎫 La personne de devant est servie
list(queue)👀 Qui attend encore
Premier entré, premier sorti : l'ordre d'arrivée est l'ordre de service.
En une phrase

Une file est une collection FIFO (premier entré, premier sorti) : les éléments sont ajoutés à l'arrière et retirés à l'avant.

Points clés

  1. deque(["first", "second"]) crée une file qui contient déjà deux éléments.
  2. queue.append("third") ajoute un élément à l'arrière.
  3. queue.popleft() retire et renvoie l'élément de devant, ici "first".
  4. deque retire rapidement à l'avant ; une liste devrait décaler chaque élément restant.

Quand l’utiliser ?

  • Traiter des tâches ou des requêtes par ordre d'arrivée.
  • Le parcours en largeur dans les graphes et les grilles.
  • Les tampons entre producteurs et consommateurs, comme des messages ou des événements.

Quand s'en passer

  • L'élément le plus récent doit sortir en premier : utilisez une pile.
  • Les éléments ont des priorités : utilisez heapq pour une file de priorité.
  • Plusieurs threads partagent la file : queue.Queue gère le verrouillage pour vous.

Voir comment ça marche

Faites enqueue et dequeue pour voir que les éléments sortent dans l'ordre où ils sont arrivés.

Code d’exemple

Exécuter le code →
main.py
from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))
Obtenir un bouton Run pour cet exemple

Résultat de l’exécution

served: first
waiting: ['second', 'third']

Explication du code

deque permet d'ajouter des éléments à droite avec append() et de les retirer à gauche avec popleft(), les deux en O(1). Avec une liste ordinaire, supprimer le premier élément coûte O(n), car tous les éléments suivants doivent se décaler, c'est pourquoi deque est le bon choix pour une file.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices d’approfondissement

Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Utiliser une liste et pop(0)

pop(0) décale chaque élément restant, ce qui devient lent pour de longues files.

Problème
queue = ["first", "second"]
queue.pop(0)
Correction
queue = deque(["first", "second"])
queue.popleft()

Leçon terminée ?

Marquez-la comme apprise pour suivre votre progression.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis