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).
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres