Files
Une file retire les éléments dans leur ordre d’insertion : premier entré, premier sorti. L’enfilage se fait à l’arrière ; le défilage et la consultation à l’avant.
from collections import deque
queue: deque[str] = deque()
queue.append("first")
queue.append("second")
front = queue[0]
removed = queue.popleft()
deque fournit des opérations efficaces aux extrémités. En Python, list.pop(0) décale les références restantes et coûte ; ce n’est donc pas l’opération de file à privilégier.
Implémentations
- Extrémités chaînées : maintenir les nœuds avant et arrière ; enfiler et défiler sont en lorsque les invariants sont corrects.
- Tampon circulaire : stocker les éléments dans un tableau fixe avec des indices de tête et de taille/queue pris modulo la capacité ; les opérations bornées sont en sans décalage.
- Deque redimensionnable : employer des blocs ou un stockage circulaire pour grandir tout en conservant un accès efficace aux extrémités.
Invariants et politique
Une file chaînée vide n’a normalement ni avant ni arrière. Un tampon circulaire doit distinguer l’état vide de l’état plein au moyen d’une taille, d’un emplacement réservé ou d’un invariant équivalent.
Le comportement en cas de sous-dépassement ou de capacité pleine appartient à l’interface : lever une erreur, bloquer, supprimer, écraser ou appliquer une contre-pression. Dans les systèmes concurrents et asynchrones, ces choix comptent davantage que la simple règle FIFO.
Usages et limites
Les files servent au parcours en largeur, aux boucles d’événements, à la mise en mémoire tampon et à l’ordonnancement du travail. Une file de priorité est différente : le retrait suit la priorité plutôt que l’ordre d’arrivée. Les files de messages sûres entre threads ou processus exigent aussi une synchronisation et des garanties de livraison qui dépassent ce type abstrait en mémoire.
Suivre le bouclage d’un tampon circulaire
Pour une capacité positive C, conserver head (indice du prochain retrait) et size, avec 0 <= size <= C. La position logique i occupe (head + i) % C. Pour enfiler lorsque le tampon n’est pas plein, écrire à (head + size) % C, puis incrémenter size. Pour défiler lorsqu’il n’est pas vide, lire et vider l’emplacement head, avancer à (head + 1) % C, puis décrémenter size. Vider l’emplacement libère la référence du conteneur à l’objet retiré.
Avec une capacité de 3, enfiler A, B, C aux emplacements 0, 1, 2. Retirer A donne head = 1, size = 2. Enfiler D à (1 + 2) % 3 = 0. Les emplacements physiques contiennent D, B, C, mais l’ordre logique est B, C, D. La taille distingue le vide du plein même quand la tête et le prochain indice d’insertion coïncident. C’est le mécanisme d’indexation des files sur tableau ; un redimensionnement ajoute des copies et modifie la garantie par opération.
Capacité en Python
Dans l’exemple initial, front et removed valent "first" et l’élément restant est "second". Sur une file vide, queue[0] et queue.popleft() lèvent IndexError. La documentation de deque précise une autre politique pour les ajouts bornés :
recent = deque(["A", "B"], maxlen=2)
recent.append("C")
assert list(recent) == ["B", "C"]
A est volontairement abandonné : utile pour un historique récent, mais pas pour une file de travail qui doit conserver chaque tâche. Une deque seule ne rend pas non plus atomique une séquence « vérifier si vide, puis retirer ». Les producteurs et consommateurs bloquants nécessitent une interface de file conçue pour cette coordination.