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 :
- • L'attente en caisse d'un magasin fonction comme une file.
- • La gestion des stockes de denrées périssables se doit d'être gérée comme une file pour éviter que les denrées les plus anciennes finissent au fond.
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.
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 :
- - Enfiler 20, puis enfiler 30, puis enfiler 40, dans f1
- - Défiler f1 et enfiler le résultat dans f1.
- - Défiler f1 et enfiler le résultat dans f2. Refaire cette opération à nouveau.
- - Défiler f2 et enfiler le résultat dans f1. Refaire cette opération à nouveau.
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.
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 →Remarque (hors programme) : La fonction print appliquée à une instance d'une classe appelle la méthode __str__ de cette classe.