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.
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.
deque(["first", "second"])🚶🚶 Deux personnes attendent déjàqueue.append("third")🚶 Une nouvelle personne se place au boutqueue.popleft()🎫 La personne de devant est servielist(queue)👀 Qui attend encoreUne 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
deque(["first", "second"])crée une file qui contient déjà deux éléments.queue.append("third")ajoute un élément à l'arrière.queue.popleft()retire et renvoie l'élément de devant, ici"first".dequeretire 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
heapqpour une file de priorité. - Plusieurs threads partagent la file :
queue.Queuegè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
from collections import deque
queue = deque(["first", "second"])
queue.append("third")
print("served:", queue.popleft())
print("waiting:", list(queue))
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.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
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.
queue = ["first", "second"]
queue.pop(0)
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.
- Course Schedule Order Order courses so every prerequisite comes first. Difficile
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Moyen