Implémentations

L'implémentation la plus simple utilise une liste simplement chaînée. Nous allons nous servir de la technique présentée dans la section 23.3.1 pour simplifier le code. Le voici :

file.lisp

Mais comme pour la pile, cette implémentation n'est pas très économique pour des files de taille importante. Chaque élément nécessite une cellule de liste avec un surcoût d'au moins deux pointeurs. De plus, le ramasse-miettes doit parcourir chaque cellule, et (selon la technique utilisée) éventuellement la déplacer.

Une meilleure implémentation utilise un vecteur avec trou (voir section 23.3.4). Selon les conventions utilisées, l'insertion peut se faire au début du trou et les suppressions à la fin. Le seul inconvénient possible de ce type d'implémentation est qu'elle est moins adaptée au temps-réel, car certaines opérations provoquent le redimensionnement du vecteur, ce qui prend un temps linéaire au lieu de constant. La complexité moyenne est par contre toujours $O(1)$ pour ces opérations.