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 pour ces opérations.