File d'attente et implémentation en Python

Un cas d'usage très concret : la file d'attente

Une imprimante partagée, un serveur web qui traite des requêtes, un jeu vidéo qui gère les actions des joueurs : dans tous ces cas, on utilise une file pour garantir que les demandes sont traitées dans l'ordre où elles sont arrivées, sans en « doubler » aucune. C'est le principe d'équité du FIFO.

Schéma : file d'attente à une caisse

Arrivees dans l'ordre : client1, client2, client3

file d'attente :
[client1]
[client1, client2]
[client1, client2, client3]

caissier traite client1 -> defiler client1
file restante : [client2, client3]
caissier traite client2 -> defiler client2
file restante : [client3]

Implémentation en Python avec une liste

class File:
    def __init__(self):
        self.elements = []

    def enfiler(self, valeur):
        self.elements.append(valeur)

    def defiler(self):
        if self.est_vide():
            raise IndexError("file vide")
        return self.elements.pop(0)

    def est_vide(self):
        return len(self.elements) == 0

f = File()
f.enfiler("A")
f.enfiler("B")
f.enfiler("C")
print(f.defiler())   # A
print(f.defiler())   # B
print(f.elements)    # ['C']

Piège classique

Avec une liste Python, enfiler (append) est rapide, mais defiler (pop(0)) doit décaler tous les éléments restants d'une case vers l'avant : c'est coûteux dès que la file devient grande, car chaque defiler() coûte alors un temps proportionnel au nombre d'éléments restants. En pratique, on préfère souvent collections.deque, conçue pour retirer efficacement en tête de file en temps constant, mais l'implémentation avec une simple liste reste parfaite pour comprendre le principe du FIFO avant d'optimiser.