Une file avec deux piles

/* Une file realisee par deux piles.
   INVARIANT : la file, de la tete vers la queue, est
   « sortie de son sommet vers son fond », puis « entree de son fond
   vers son sommet ». */
typedef struct { pile* entree; pile* sortie; } file2p;

void enfiler(file2p* f, int x) { pile_empiler(f->entree, x); }

int defiler(file2p* f) {
    if (pile_est_vide(f->sortie)) {              /* transfert : on RENVERSE */
        while (!pile_est_vide(f->entree)) {
            pile_empiler(f->sortie, pile_depiler(f->entree));
        }
    }
    assert(!pile_est_vide(f->sortie));           /* precondition : file non vide */
    return pile_depiler(f->sortie);
}

Vérifié : après avoir enfilé $1$ à $5$, défilé trois fois, enfilé $6$ à $8$ puis défilé cinq fois, on obtient $1,2,3,4,5,6,7,8$ — l'ordre fifo.

Pourquoi cela marche. Dépiler la pile d'entrée rend ses éléments dans l'ordre inverse de leur arrivée ; les empiler sur la pile de sortie les remet donc dans l'ordre d'arrivée, et le sommet de la pile de sortie est le plus ancien. Deux renversements valent une identité, et c'est toute l'astuce.

Le coût. Un defiler isolé peut coûter $\Theta (n)$ : celui qui déclenche le transfert. Mais comptons le total. Chaque élément est déplacé au plus une fois de l'entrée vers la sortie — une fois transféré, il ne revient jamais. Sur une suite de $n$ enfilages et $n$ défilages, le nombre total de transferts est donc au plus $n$, et le coût total est $O(n)$ : le coût amorti est $O(1)$.

Mesuré, en comptant les transferts :

8 enfilages entrelaces de 8 defilages          :      8 transferts
100 000 enfilages puis 100 000 defilages       : 100 000 transferts
100 000 couples (enfiler, defiler) alternes    : 100 000 transferts

Dans les trois régimes, un transfert par élément : la borne est atteinte et jamais dépassée.

Le rapprochement à faire, et c'est pour cela que l'exercice figure ici : le raisonnement est exactement celui du tableau dynamique du chapitre chap:langage-c. Une opération chère, mais chaque unité de travail imputable à un élément distinct et payée une seule fois. C'est la forme la plus simple d'analyse amortie, et elle ne demande aucun outil : seulement de compter le travail total au lieu du travail d'un appel.

À quoi cela sert vraiment : à réaliser une file dans un langage ou une bibliothèque qui n'offre que des piles — et, plus utilement, à réaliser une file persistante en OCaml, où les deux piles sont deux listes immuables et où l'on obtient une file dont toutes les versions coexistent.