Les Files

Un type abstrait de données (ou TAD) est défini par son interface (comment on s'en sert) plutôt que par son implémentation (comment il fonctionne, comment il a été programmé).

Un TAD est théorique et indépendant des langages de programmation.

Définition

Une file (aussi appelée « queue » ou « FIFO » pour first in, first out) est un type abstrait de données dans lequel un seul élément est accessible à la fois : le premier de la file.

Interface d'une file

Une interface possible de file (en programmation impérative) est :

Méthode/Opérations	Description
F = File()	Initialisation d'une file vide.
est_vide(F)	Renvoie True si la file est F vide, False sinon.
enfiler(F, elt)	Enfile un nouvel élément en queue de la file.
defiler(F)	Lorsque la file n'est pas vide, supprime le premier élément de la file et renvoie la valeur de cet élément.

Remarque

Dans certains cas, l'interface propose deux opérations pour le défilement :

• une opération pour renvoyer la valeur du premier élément (sans défiler) ;
• une opération pour supprimer le premier élément (défiler) sans renvoyer sa valeur.