Files

I. Définition

A. Définition informelle

Les files sont des structures appelées également structures FIFO : First In, First Out. Elle sont appelées files car elles fonctionnent de façon similaire à une file d'attente (en Théorie, pas en France 😉) à une caisse : les nouvelles données (comme les nouvelles personnes) se mettent à la fin de la file, et les premiers à sortir sont ceux qui étaient arrivés en premier.

Les files peuvent être vues comme des listes avec un nombre restreint d'opérateurs : l'ajout en queue, la consultation en tête, et le prélèvement en tête.

B. Définition formelle

  Nom : File
  
  Constructeurs
    fileVide: File
    ajouter: Element x File → File
  
  Opérateurs
  tete : File → Element
    tete(ajouter(e, fileVide)) = e
    tete(ajouter(e1, ajouter(e2, file))) = tete(ajouter(e2, file))
  
  prelever: File → Element x File
    prelever(ajouter(e, fileVide)) = (e, fileVide)
    prelever(ajouter(e1, ajouter(e2, file))) = (tete(ajouter(e2, file)), ajouter(e1, prelever(ajouter(e2, file))[1])) 

  estVide: File → Bool
    estVide(fileVide) = true
    estvide(ajoute(e, f)) = false
  
  Remarque sur la notation : (u,v)[1] = v

Pour aider à la compréhension de l'opérateur prelever, regardons ce que cela donne sur la file [1, 2, 3] :

[1, 2, 3] ≈
ajouter(3, ajouter(2, ajouter(1, fileVide)))
  
prelever([1, 2, 3]) ≈
prelever(ajouter(3, ajouter(2, ajouter(1, fileVide))) =
  (tete(ajouter(2, ajouter(1, fileVide))),  ajouter(3, prelever(ajouter(2, ajouter(1, fileVide)))[1])) =
  (tete(ajouter(1, fileVide))            ,  ajouter(3, prelever(ajouter(2, ajouter(1, fileVide)))[1])) =
  (1                                     ,  ajouter(3, prelever(ajouter(2, ajouter(1, fileVide)))[1])) =
  (1, ajouter(3, (tete(ajouter(1, fileVide))  ,  ajouter(2, prelever(ajouter(1, fileVide))[1]))[1])) =
  (1, ajouter(3, ajouter(2, prelever(ajouter(1, fileVide))[1]))) =
  (1, ajouter(3, ajouter(2, (1, fileVide)[1]))) =
  (1, ajouter(3, ajouter(2, fileVide))) ≈
  (1, [2, 3])

II. Les implantations de la notion de file

A. Le cas général

Une file pouvant avoir a priori un nombre quelconque d'éléments, et constituant une structure linéaire, on utilise les mêmes moyens pour les implanter que ceux utilisés pour implanter des listes, à savoir des tableaux dynamiques ou des listes chaînées.

B. En Python

En Python, les tableaux dynamiques se prêtent très bien à l'implantation de la notion de pile, d'autant plus que les opérateurs nécessaires sont déjà fournis.

Voici maintenant comment les constructeurs et opérateurs du type Pile se retrouvent parmi les fonctionnalités des tableaux dynamiques en Python :

Constructeur /
Opérateur Équivalent Python Exemple

fileVide [] f = []

ajouter append() f.append(1)

tete [0] s = f[0]

prelever pop(0) t = f.pop(0)

estVide len(...) == 0 vide = len(f) == 0

Constructeur / Opérateur	Équivalent Python	Exemple
`fileVide`	`[]`	`f = []`
`ajouter`	`append()`	`f.append(1)`
`tete`	`[0]`	`s = f[0]`
`prelever`	`pop(0)`	`t = f.pop(0)`
`estVide`	`len(...) == 0`	`vide = len(f) == 0`

C. Ré-implanter les files

Pour rendre plus clair la notion de file, il est possible de ré-implanter une file pour n'autoriser que les opérations de la structure de file sous la forme d'une class File (c'est la mise en oeuvre du Pattern Façade). Cela pourrait donner la classe suivante :

class File:
    def __init__(self):
        self.file = []

    def ajouter(self, e):
        self.file.append(e)

    def tete(self):
        return self.file[0]

    def prelever(self):
        s = self.file.pop(0)
        return s

    def estVide(self):
        return len(self.file) == 0

    def __str__(self):
        retour = ""
        for e in self.file:
            retour += str(e) + ','
        return retour

Attention ! : de file (en français) à file (en anglais), il n'y a qu'un pas... qui peut très rapidement prêter à confusion. Pour la notion de file, les anglais utilisent le mot queue, mais ce n'est pas forcément un mot facile à employer devant des lycéens...

III. Algorithmes sur les files

Vous aurez l'occasion de voir, dans le cours sur les arbres, une utilisation des files pour parcourir un arbre en largeur.

Les files sont également souvent utilisées pour stocker des données arrivant de différentes sources et devant être traitées par un seul et même serveur, potentiellement lent par rapport à l'intervalle séparant l'arrivée de 2 tâches.

Les files sont également un moyen de stocker des ressources (produites par des producteurs) en attendant leur consommation (par des consommateurs) lorsqu'une durée de péremption impose de prendre les ressources dans l'ordre.

Voici une illustration de ce dernier cas avec 2 producteurs et 1 consommateur :

from random import randint
from time import sleep

class Producteur:
    def __init__(self, nom):
        self.numeroRessource = 0
        self.nom = nom

    def produire(self):
        self.numeroRessource += 1
        nomRessource = self.nom + str(self.numeroRessource)
        print(self.nom + " produit la ressource " + nomRessource)
        return nomRessource

class Consommateur:
    def consommer(self, ressource):
        print("consommation de la ressource " + str(ressource))

def moteur():
    file = File()
    producteurA = Producteur("A")
    producteurB = Producteur("B")
    consommateur = Consommateur()

    termine = False
    nbProduits  = 0
    nbProduitsMax = 20
    
    while nbProduits == 0 or not file.estVide():
        alea = randint(0, 7)
        if alea < 3 and nbProduits < nbProduitsMax:
            # activation du producteur A
            nouvelleRessource = producteurA.produire()
            file.ajouter(nouvelleRessource)
            nbProduits += 1
        elif alea < 5 and nbProduits < nbProduitsMax:
            # activation du producteur B
            nouvelleRessource = producteurB.produire()
            file.ajouter(nouvelleRessource)
            nbProduits += 1
        else:
            if not file.estVide():
                ressourceUtilisee = file.prelever()
                consommateur.consommer(ressourceUtilisee)
        sleep(1)

moteur()