Aller au contenu

Structures de données linéaires - les files

I. Introduction⚓︎

Il faut se représenter une file comme... une file d'attente !

FIFO

👉 On ne peut entrer dans la file qu'en dernière position et on ne peut la quitter que si on est le premier.

👉 L'ajout d'un élément dans une file ne peut se faire qu'à la fin (en dernière position) et le retrait d'un élément ne peut se faire qu'au début (en première position).

On dit que les files sont en mode FIFO (First In, First Out qui signifie « premier entré, premier sorti »).

pile FIFO

Usage courant d'une FILE

👉 En général, on utilise des files pour mémoriser temporairement des transactions qui doivent attendre pour être traitées.

  • Les serveurs d'impression, qui doivent traiter les requêtes dans l'ordre dans lequel elles arrivent, les insèrent dans une file d'attente (ou une queue en anglais).
  • Certains moteurs multitâches, dans un système d'exploitation, doivent accorder du temps-machine à chaque tâche, sans en privilégier aucune.

Les fonctions primitives pour les FILES sont les suivantes

  • construire_file() : crée une file vide
  • est_vide(F) : teste si une file est vide,
  • enfiler(F, e) : ajoute l'élément e en dernier dans la file F.
  • defiler(F) : retire le premier élément de la file F. Précondition : F n'est pas vide.

😊 Et rien de plus ...

II. Une implémentation possible des files⚓︎

Les fonctions "primitives" pour les files

Ces fonctions "primitives" sont les suivantes : création d'une file vide, tester si une file est vide, enfiler, défiler.

Et rien de plus ...

  • enfiler : ajouter un élément en fin de file.
  • défiler : supprimer un élément en début de file
La classe File

Vous allez vous-même compléter ci-dessous une possible implémentation de ces fonctions primaires, en utilisant le vocabulaire de la programmation orientée objet que nous avons déjà abordée.

Dans toute la suite les files seront affichées entre crochets, comme des list python. Le sommet de la file est l'élément écrit le plus à droite.

👉 Ainsi, si l'on part d'une file vide, et que l'on enfile successivement les entiers 1, puis 2, puis 3, on obtiendra une file qui s'affichera de la façon suivante : [3, 2, 1]. Le sommet de cette file est l'entier 1.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Solution
🐍 Script Python
class File_a_trous :
    def __init__(self):
        self.contenu = []

    def est_vide_file(self) :
        return self.contenu == []

    def enfiler(self, x):
        self.contenu = [x] + self.contenu

    def defiler(self):
        assert not self.est_vide_file(), "la file est vide"
        return self.contenu.pop()

    def __str__(self) :
        return 'enfilage -> '+str(self.contenu) + ' -> défilage'
La classe File pour la suite

Pour pouvoir continuer, exécuter ci-dessous

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Tester ci-dessous ces primitives

A vous d'inventer vos tests

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

A vous de jouer

Ecrire ci dessous les instructions qui permettent d'obtenir successivement les affichages suivants :

enfilage -> [8] -> défilage
enfilage -> [14, 8] -> défilage
enfilage -> [12, 14, 8] -> défilage
enfilage -> [12, 14] -> défilage
enfilage -> [12] -> défilage
enfilage -> [] -> défilage

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Solution
🐍 Script Python
file = File()
file.enfiler(8)
print(file)
file.enfiler(14)
print(file)
file.enfiler(12)
print(file)
file.defiler()
print(file)
file.defiler()
print(file)
file.defiler()
print(file)

Sources : Stéphan Van Zuijlen, Alain Busser.