Problème — File implémentée à deux piles

L'idée : une pile entree reçoit les éléments enfilés ; une pile sortie sert à les défiler. Quand sortie est vide, on y transvase tout le contenu de entree, ce qui inverse l'ordre et place le plus ancien au sommet.

class FileDeuxPiles:
    def __init__(self):
        self._entree = []      # pile ou l'on empile les arrivees
        self._sortie = []      # pile d'ou l'on defile

    def est_vide(self):
        return len(self._entree) == 0 and len(self._sortie) == 0

    def enfiler(self, x):
        self._entree.append(x)         # toujours dans la pile d'entree

    def defiler(self):
        if self.est_vide():
            raise IndexError("defiler sur une file vide")
        if len(self._sortie) == 0:
            # transvasement : inverse l'ordre des elements
            while len(self._entree) > 0:
                self._sortie.append(self._entree.pop())
        return self._sortie.pop()      # le plus ancien est au sommet

# Test : FIFO attendu
f = FileDeuxPiles()
f.enfiler(1)
f.enfiler(2)
f.enfiler(3)
print(f.defiler())   # 1
print(f.defiler())   # 2
f.enfiler(4)
print(f.defiler())   # 3
print(f.defiler())   # 4

Analyse du coût : enfiler est toujours en $O(1)$. Une opération defiler peut déclencher un transvasement coûteux en $O(n)$, mais chaque élément n'est transvasé qu'une seule fois durant toute sa vie dans la file. Réparti sur l'ensemble des opérations, le coût amorti de defiler est donc $O(1)$.