On propose ici deux implémentations du type abstrait file (Queue). La première, très simple, ne remplit pas toutes les conditions en termes de complexité en temps (l’insertion ne se fait pas en temps constant). La seconde, plus technique, se base sur une liste chaînée.
I. Implémentation à base de listes Python
Le code suivant, à base de liste Python, implémente l’interface définie, mais ne respecte pas les contraintes de complexité. En effet, l’opération dequeue s’exécute en temps linéaire en la longueur de la liste car les listes Python ne permettent pas la suppression de leur premier élément en temps constant.
Les concepts de programmation orientée objet utilisés ici sont introduits.
Résultat :
RemarqueLes files d’attente sont très utilisées en informatique : mémoriser des transactions en attente accédant à une base de données, gérer la file des impressions en attente d’un système d’impression… Nous les retrouverons dans le chapitre suivant dans les algorithmes de parcours en largeur des arbres.
II. Implémentation avec une liste chaînée
Une liste chaînée double (double-ended queue en anglais) est une liste chaînée qui contient aussi une référence vers le dernier élément de la liste.
Ce détail supplémentaire permet de réaliser une suppression en tête de liste et un ajout en fin de liste, en temps constant dans les deux cas. La classe Node permet de modéliser les éléments de la liste chaînée.
À noter
La manière d’utiliser la file (son interface) est exactement la même dans les deux implémentations (le programme de test est le même !). Il est courant de commencer la programmation avec une implémentation améliorable d’une structure de données. Puis, par la suite, la structure de données est améliorée sans que le code principal ait besoin d’être retouché.