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 »).
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
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
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Tester ci-dessous ces primitives
A vous d'inventer vos tests
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
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
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
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.
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)