On veut écrire une classe pour gérer une file à l'aide d'une liste chainée circulaire. On dispose d'une classe Maillon permettant la création d'un maillon de la chaine, celui-ci étant constitué d'une donnée valeur et d'une référence au maillon suivant de la chaine:
Une liste chainée est une succession de maillons. On accède à la liste par le premier maillon. Chaque maillon permet d'accéder au maillon suivant.
L'accès direct au premier maillon permet de supprimer ce premier maillon ou d'ajouter un nouveau maillon qui devient le nouveau premier maillon, de manière efficace. Ceci est parfait pour implémenter une pile pour laquelle la suppresion et l'ajout d'un élément s'effectuent du même côté.
Pour implémenter une file, il est nécessaire de pouvoir accéder de manière efficace au premier maillon et au dernier maillon. Une solution est donc d'avoir deux accès à la liste.
Une autre solution est d'utiliser une liste chainée circulaire obtenue à partie d'une liste chainee en ajoutant un lien entre le dernier maillon et le premier maillon.
Le premier maillon de la liste auquel on accède est celui représentant le dernier élément entré dans la file. Ce maillon permet d'accéder directement au maillon contenant le premier élément entré dans la file.
Par exemple, on suppose avoir enfilé dans l'ordre les éléments 1, 2, 3. On accède à la liste par le maillon contenant l'élément 3, qui permet d'accéder directement au maillon contenant l'élément 1:
Pour enfiler un élément, si la file est vide il suffit de créer un maillon contenant l'élément et un lien vers lui-même.
Sinon, on crée un nouveau maillon avec un lien vers le maillon contenant le premier élément enfilé. Par exemple, pour enfiler l'élément 4 dans la file représentée précedemment, on crée un maillon contenant l'élement 4 avec un lien vers le maillon contenant l'élément 1:
On modifie le lien du maillon par lequel on accède à la liste, celui contenant l'élément 3:
On modifie le lien permettant d'accéder à un maillon de la liste afin d'accéder directement au maillon contenant le dernier élément enfilé.
On obtient bien la liste souhaitée.
On suppose avoir enfilé dans l'ordre les éléments 1, 2, 3, 4 comme dans la file précédente.
Pour défiler un élément, on récupère l'élément stocké dans le premier maillon entré dans la file (1), qui est le maillon suivant celui par lequel on accède à la liste. On modifie ensuite le lien qui ne pointe plus vers le maillon à retirer mais pointe vers le maillon suivant.
Compléter la classe File et vérifier votre travail sur les exemples. On vous donne la méthode __init__ qui initialise une file, la méthode __repr__ qui permet un affichage des éléments de la file, la méthode est_vide qui renvoie True si la file est vide et False sinon.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)