Files

Généralités sur les files

Une « file » (ou « queue » en anglais) est une structure de données linéaire dans laquelle les éléments sont accessibles selon une méthode FIFO (« First-In First-Out » en anglais) : le premier élément inséré dans la liste est le premier à en sortir.

• Insérer un élément dans la file est appelé « enfiler » (« enqueue » en anglais).
• Supprimer un élément de la file est appelé « défiler » (« dequeue » en anglais).

L’accès aux objets de la file se fait grâce à deux pointeurs, l’un pointant sur l’élément qui a été inséré en premier et l’autre pointant sur celui inséré en dernier.

Vidéo sur les files

Les files par Foxxpy : Mathématiques et algorithmie (11:29)

Primitives

Voici les primitives communément utilisées pour manipuler des files. Il n'existe pas de normalisation pour les primitives de manipulation de file. Leurs noms sont donc indiqués de manière informelle.

• « Enfiler » : ajoute un élément dans la file.
• « Défiler » : renvoie le prochain élément de la file, et le retire de la file.
• « La file est-elle vide ? » : renvoie « vrai » si la file est vide, « faux » sinon.
• « Nombre d'éléments dans la file » : renvoie le nombre d'éléments dans la file.

Exemple d'implémentation en Python

🐍 Editeur

class File:
    """Définit un objet de type File"""

    def __init__(self: object) -> None:
        """Constructeur"""
        self.datas = []    # Utilisation d'un tableau Python

    def enfiler(self: object, data: any) -> None:
        """Méthode pour enfiler une donnée en queue dans la file"""
        self.datas.append(data)

    def defiler(self: object) -> any:
        """Méthode pour défiler la donnée en tête dans la file"""
        if self.datas:
            return self.datas.pop(0)

    def estVide(self: object) -> bool:
        """Méthode pour tester si la file est vide"""
        return self.datas == []

    def longueur(self: object) -> int:
        """Méthode pour obtenir la longueur de la file"""
        return len(self.datas)

    def __str__(self: object) -> str:
        """Méthode pour afficher le contenu de la file"""
        ch = "\nEtat de la file:\n"
        for x in self.datas:
            ch +=  str(x) + " "
        return ch


if __name__ == "__main__":
    q = File()
    q.enfiler(8)
    q.enfiler(1)
    q.enfiler(3)
    q.enfiler(5)
    q.enfiler(2)
    print(q)
    q.defiler()
    q.enfiler(7)
    print("La file est-elle vide :", q.estVide())
    print(q)
    print("Longueur de la file :", q.longueur())

L'exécution de ce programme donne :

▶️ Console

>>>
Etat de la file:
8 1 3 5 2 
La file est-elle vide : False

Etat de la file:
1 3 5 2 7 
Longueur de la file : 5
>>>

Applications

Ce type de structure de données linéaire est utilisé par exemple :

• En général, pour mémoriser temporairement des transactions qui doivent attendre pour être traitées ;
• Les serveurs d'impression, qui traitent ainsi les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente (« queue ou « spool » en anglais) ;
• Certains moteurs multitâches, dans un système d'exploitation, qui doivent accorder du temps-machine à chaque tâche, sans en privilégier aucune ;
• Un algorithme de parcours en largeur utilise une file pour mémoriser les noeuds visités ;
• Pour créer toutes sortes de mémoires tampons (« buffers » en anglais) ;
• En gestion des stocks, les algorithmes doivent respecter la gestion physique des stocks pour assurer la cohérence physique/valorisation.

File (animations en ligne)

File implémentée avec un tableau

File implémentée avec une liste chaînée