C3.2 : Les files

Présentations des files

Présentations

Comme les piles, les files sont des structures de données linaires (ou séquentielles).

La manipulation des données d'une file se fait suivant le principe « premier arrivé, premier sorti » (en anglais FIFO pour first in, first out). Autrement dit, les éléments sont ajoutés d'un côté et enlevés de l'autre.

Exemples

Plusieurs exemples de la vie courantes illustrent le principe des files :

Interface d'une file

L'interface minimale des files doit permettre les actions suivantes :

  • - Créer une structure vide ;
  • - Tester si la structure est vide ;
  • - Ajouter un élément à la structure : enfiler ;
  • - Enlever (en renvoyant) un élément à la structure : défiler.

Implémentation

Rappel : Comme toutes les structures de données, les files peuvent être implémentées par des classes (ce que nous verrons dans cette activité), mais également à l'aide de fonctions...

Implémentation d'une classe File en python

Proposer, en Python, l'implémentation d'une classe File basée sur l'utilisation d'un attribut privé de type list.

Afficher la correction 
# Première version
# Les éléments sont enfilés de la gauche vers la droite.
# C'est-à-dire qu'ils sont ajoutés à gauche et enlevés à droite
class File:
    def __init__(self):
        self.__donnees = []

    def est_vide(self):
        return self.__donnees == []

    def enfile(self, elt):
        self.__donnees = [elt] + self.__donnees

    def defile(self):
        if not self.est_vide():
            return self.__donnees.pop()
        else:
            return None

# Deuxième version
# Les éléments sont enfilés de la droite vers la gauche.
# C'est-à-dire qu'ils sont ajoutés à droite et enlevés à gauche
class File:
    def __init__(self):
        self.__donnees = []

    def est_vide(self):
        return self.__donnees == []

    def enfile(self, elt):
        self.__donnees.append(elt)

    def defile(self):
        if not self.est_vide():
            return self.__donnees.pop(0)
        else:
            return None

Applications

Application 1 : Manipuler les files

On considère les deux files représentées ci-dessous.

Représenter les deux files après chacune des quatre séries d'opérations suivantes :

Application 2 : Vider une file

Écrire une fonction vider(file) qui prend une instance de la classe File en paramètre et modifie cette instance pour qu'elle ne contienne plus aucun élément.

Afficher la correction 
class File:
    def __init__(self):
        self.__donnees = []

    def est_vide(self):
        return self.__donnees == []

    def enfile(self, elt):
        self.__donnees.append(elt)

    def defile(self):
        if not self.est_vide():
            return self.__donnees.pop(0)
        else:
            return None

def vider(f):
    while not(f.est_vide()):
        f.defile()

# Programme principal
fi1 = File()
fi1.enfile(10)
fi1.enfile(20)
fi1.enfile(30)
print(fi1.est_vide())
vider(fi1)
print(fi1.est_vide())

Application 3 : Afficher les files en ajoutant une méthode à la classe File

Ajouter une méthode to_str à la classe File. Cette méthode doit renvoyer la file sous la forme d'une chaine de caractère (en précisant le sens de la file).

Ainsi le code suivant doit renvoyer la chaine "→ C B A →".

f = File()
f.enfile('A')
f.enfile('B')
f.enfile('C')
print(f.to_str()) # Doit afficher : → C B A →
Afficher la correction 
class File:
    def __init__(self):
        self.__donnees = []

    def est_vide(self):
        return self.__donnees == []

    def enfile(self, elt):
        self.__donnees = [elt] + self.__donnees

    def defile(self):
        if not self.est_vide():
            return self.__donnees.pop()
        else:
            return None
    def to_str(self):
        chaine = "→ "
        for elt in self.__donnees:
            chaine = chaine + str(elt) + " "
        chaine = chaine + "→"
        return chaine

# Programme principal
f = File()
f.enfile('1er')
f.enfile('2ème')
print(f.to_str())

Remarque (hors programme) : La fonction print appliquée à une instance d'une classe appelle la méthode __str__ de cette classe.

Afficher l'exemple 
class File:
    def __init__(self):
        self.__donnees = []

    def est_vide(self):
        return self.__donnees == []

    def enfile(self, elt):
        self.__donnees = [elt] + self.__donnees

    def defile(self):
        if not self.est_vide():
            return self.__donnees.pop()
        else:
            return None
    def __str__(self):
        chaine = "→ "
        for elt in self.__donnees:
            chaine = chaine + str(elt) + " "
        chaine = chaine + "→"
        return chaine

# Programme principal
f = File()
f.enfile('A')
f.enfile('B')
f.enfile('C')
print(f)