La file : enfiler et défiler

Le principe FIFO

Une file (en anglais queue) fonctionne à l'opposé de la pile : le premier élément ajouté est le premier à sortir. On parle de FIFO, pour « First In, First Out » (premier entré, premier sorti). C'est exactement une file d'attente au supermarché : la première personne arrivée est la première servie, quel que soit le monde qui arrive ensuite.

Les deux opérations de base

• enfiler (enqueue) : ajouter un élément à l'arrière de la file ;
• défiler (dequeue) : retirer et renvoyer l'élément à l'avant de la file.

Schéma : évolution d'une file

File vide :                  []

enfiler(A)  ->                [A]
enfiler(B)  ->                [A, B]
enfiler(C)  ->                [A, B, C]         (A est en tête, C vient d'arriver)

defiler() -> A                 [B, C]           (A sort en premier, il était le premier arrivé)
defiler() -> B                 [C]

vue horizontale :
   sortie (defiler)                     entree (enfiler)
        <---   [ A ][ B ][ C ]   <---
             (tête, sort en 1er)     (queue, dernier arrivé)

Pile ou file, ne pas confondre

La différence tient entièrement à l'extrémité où l'on retire l'élément : au même côté que l'ajout pour une pile (LIFO), à l'opposé de l'ajout pour une file (FIFO). Un moyen simple de retenir : la pile s'empile comme une pile d'assiettes, la file se comporte comme une file d'attente humaine.

Piège classique

Une erreur fréquente est d'implémenter une file en pensant « premier arrivé, premier sorti » mais de retirer par erreur le dernier élément ajouté : on obtient alors une pile déguisée, avec un ordre de sortie totalement différent de celui attendu.