Implémenter une structure : l'exemple de la file FIFO

Introduction

Le cours précédent a posé un principe : une interface est un contrat, une implémentation est un code qui le réalise, et un même contrat admet plusieurs implémentations. Ce cours le met en pratique sur un exemple classique de Terminale : la file FIFO.

Deux classes, FileTableau et FileDeuxPiles, exposent ici la même interface (quatre méthodes au comportement strictement identique du point de vue de l'utilisateur), mais leurs performances diffèrent radicalement. C'est l'illustration parfaite de l'item [TA04] : « écrire plusieurs implémentations d'une même structure de données ».

L'interface d'une file FIFO

Une file (en anglais queue) est une structure linéaire au comportement FIFO (First In, First Out). L'analogie est immédiate : la file d'attente à la boulangerie. On entre par la queue, on sort par la tête, on ne double pas.

Son interface comporte typiquement quatre opérations :

Implémentation 1 : avec un tableau (liste Python)

La représentation la plus naturelle utilise une liste Python comme stockage interne. Les éléments sont rangés dans l'ordre d'arrivée ; on enfile à la fin, on défile au début.

class FileTableau:
    """File FIFO implémentée par une liste Python."""

    def __init__(self):
        self._data = []

    def enfiler(self, x):
        self._data.append(x)            # O(1) amorti

    def defiler(self):
        if not self._data:
            raise IndexError("file vide")
        return self._data.pop(0)        # O(n) : décalage de tous les éléments

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

    def taille(self):
        return len(self._data)

Traçons un scénario complet pour vérifier la sémantique FIFO :

f = FileTableau()
f.enfiler(1)
f.enfiler(2)
f.enfiler(3)
print(f.defiler())   # 1 : le premier entré
print(f.defiler())   # 2
print(f.taille())    # 1

Analyse de complexité :

• enfiler repose sur list.append, qui s'exécute en $\mathcal{O}(1)$ amorti.
• defiler repose sur list.pop(0), qui décale tous les éléments restants vers la gauche, d'où un coût en $\mathcal{O}(n)$ où $n$ est la taille courante.

Cette implémentation est simple à lire mais non optimale. Sur une file de un million d'éléments, chaque defiler réalise un million d'écritures mémoire, ce qui est inacceptable en production.

Implémentation 2 : avec deux piles

Une astuce classique : utiliser deux piles pour simuler une file. La pile d'entrée reçoit les enfiler ; la pile de sortie sert aux defiler. Quand la sortie est vide, on transvase tout le contenu de l'entrée dedans, ce qui inverse l'ordre : le premier entré redevient le premier sorti.

class FileDeuxPiles:
    """File FIFO implémentée par deux piles (listes utilisées en LIFO)."""

    def __init__(self):
        self._entree = []        # pile : on append/pop en bout
        self._sortie = []

    def enfiler(self, x):
        self._entree.append(x)                       # O(1)

    def defiler(self):
        if not self._sortie:
            while self._entree:
                self._sortie.append(self._entree.pop())
        if not self._sortie:
            raise IndexError("file vide")
        return self._sortie.pop()                    # O(1) amorti

    def est_vide(self):
        return not self._entree and not self._sortie

    def taille(self):
        return len(self._entree) + len(self._sortie)

Traçons le même scénario qu'avant ; l'observation extérieure est identique :

f = FileDeuxPiles()
f.enfiler(1)
f.enfiler(2)
f.enfiler(3)
print(f.defiler())   # 1
print(f.defiler())   # 2
print(f.taille())    # 1

Pourquoi est-ce plus rapide ?

À première vue, le transvasement coûte cher : il faut bien $k$ opérations pour basculer $k$ éléments. Mais ce qui se passe sur une longue suite d'opérations est tout autre.

C'est la beauté de la complexité amortie : on ne raisonne pas sur le pire cas d'une opération isolée (qui peut être un gros transvasement), mais sur le coût moyen observé sur une longue séquence d'opérations.

La promesse de l'abstraction

Les deux classes FileTableau et FileDeuxPiles exposent exactement la même interface. Un code qui utilise f.enfiler(x) puis f.defiler() fonctionne sans modification, quelle que soit la classe choisie. C'est la promesse de l'abstraction : on peut changer le moteur sans changer la carrosserie.

# Ce code fonctionne identiquement avec FileTableau OU FileDeuxPiles
def traiter_taches(file_de_taches):
    while not file_de_taches.est_vide():
        tache = file_de_taches.defiler()
        # ... traiter la tâche ...

Récapitulatif comparatif

Les deux respectent le contrat ; la deuxième est asymptotiquement meilleure. Le choix d'implémentation dépend du contexte : si la file reste petite et que la simplicité prime, FileTableau suffit ; si la performance compte, FileDeuxPiles (ou mieux, collections.deque, voir ci-dessous).

Pour aller plus loin

Le module standard collections.deque fournit une file double, en $\mathcal{O}(1)$ à chaque bout, implémentée en C. C'est l'outil employé en pratique :

from collections import deque
f = deque()
f.append(1)         # enfiler
f.append(2)
print(f.popleft())  # defiler → 1

Mais savoir réimplémenter une file à partir de structures plus primitives est exigible au baccalauréat : c'est précisément ce que font les deux implémentations ci-dessus.