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.

Solution

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

Tester ci-dessous ces primitives

A vous d'inventer vos tests

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

Solution

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.