Implémentation des files par deux listes

La méthode précédente ne permet que de créer des files ayant une taille maximum.

Si on veut que la file d’attente puisse s’allonger indéfiniment, il faut utiliser des listes.

Mais utiliser une seule liste pour représenter une file d’attente serait une très mauvaise idée !

En fait, on va utiliser deux listes, une « liste arrière » et une « liste avant » :

  • Au début, les deux listes sont vides, et chaque nouvel arrivant s’ajoute à la liste arrière.
  • L’élément qui quitte la file sera la tête de la liste avant. Si celle-ci est vide, on l’alimente en y re(n)versant la liste arrière (de telle sorte que le plus ancien dans la liste arrière devienne l’élément de tête, donc celui qui sort, dans la liste avant).
  • On le voit, les retournements de listes sont assez exceptionnels (ils ne se produisent que lorsque la liste avant s’épuise, et à supposer que la liste arrière contienne à ce moment précis {n} éléments, le retournement de cette liste fait que les {n} sorties suivantes se font en temps constant).
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :