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.
IImplé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 introduitslà.
![Tableau de 19 lignes, 2 colonnes ;Corps du tableau de 19 lignes ;Ligne 1 : ; class Queue:; Ligne 2 : ; def __init__(self):; Ligne 3 : ; self.data = []; Ligne 4 : ; ; Ligne 5 : ; def is_empty(self):; Ligne 6 : ; return not bool(self.data); Ligne 7 : ; ; Ligne 8 : ; def enqueue(self, value):; Ligne 9 : ; self.data.append(value); Ligne 10 : ; ; Ligne 11 : ; def dequeue(self):; Ligne 12 : ; return self.data.pop(0); Ligne 13 : ; f = Queue(); Ligne 14 : ; f.enqueue(](/modules-assets/images/PB_Bac_06461_NSIT_gene/PB_Bac_06461_NSIT_gene_p093-120_C04_Tab_41.png)
Résultat :
REMARQUE
Les 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.
IIImplé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.
Il est fondamental de noter que 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é.