Listes-Piles-Files
Partie 2: files
Les files sont une autre structure de données qui permettent de stocker des objets. Ces objets sont ajoutés ou retirés un par un.
Dans une file, le dernier élément ajouté est positionné en fin de file et il sera le dernier élément retiré si on vide la file.
Partie A : File créée avec deux piles
il est possible de créer une file avec deux piles. Une pile contient les nouveaux éléments ajoutés et sur l’autre pile on prend les éléments à retirer.
Si la pile de sortie est vide, on renverse la pile d’entrée ( les éléments du fond deviennent ainsi le sommet) et on l’affecte comme pile de sortie.
Voici le code d'une telle implémentation, elle nécessite la classe Pile précédente pour fonctionner.
def créer_pile():
return Pile()
class File:
def __init__(self):
self.entree = creer_pile()
self.sortie = creer_pile()
def est_vide(self):
return self.entree.est_vide() and self.sortie.est_vide()
def ajouter(self, valeur):
self.entree.empiler(valeur)
def retirer (self):
if self.sortie.est_vide():
# ici on remplit
while not self.entree.est_vide():
self.sortie.empiler(self.entree.depiler())
if self.sortie.est_vide():
raise IndexError("la file est vide")
return self.sortie.depiler()
Question 3.1
Construire la File qui contient les valeurs 1, 2, 3 , 4 ( le 4 étant la queue de la File), vous appellerez votre file "une_file"
Question 3.2
Ajouter l'élément de valeur 5 en fin de file.
Question 3.3
Ecrire une fonction qui affiche le contenu de la File.
Question 3.4
Retirer deux éléments et écrire le code qui affiche le sommet de la File.
Partie B: File bornée
On souhaite réaliser une file bornée ( nombre maximums d'éléments fixés à la création) à l'aide d'un tableau que l'on créé avec le type liste de python.
On appelle le nombre d’éléments dans la file nb
On appelle la capacité de la file cap
L’indice du premier élément est appelé premier
L’indice de l’emplacement d’un élément à rajouter sera : (premier + nb) % cap
Exemple:
En rouge ce sont les indices des cases d'un tableau qui peut contenir cap = 10 éléments et qui en contient nb=4 pour l'instant, le prochain élément devra être insérer dans la case d'indice 6:
Ci-dessous le même tableau dans un autre état, il contient maintenant 7 éléments, le premier élément est dans la case d'indice 3, la prochaine donnée doit être ajouter en fin de file qui est à l'emplacement :
(premier + nb) % cap = (3 + 7) % 10 = 10 % 10 = 0
Voici une classe qui implémente cette file:
class Filebornee:
def __init__(self, cap):
self.contenu = [None]*cap
self.premier = 0
self.nb=0
def est_vide(self):
return .....
def est_pleine(self):
return .....
def ajouter ( self, valeur):
if self.est_pleine():
raise IndexError("File pleine")
indice_nouvel_emplacement = ( self.premier + self.nb) % len ( self.contenu)
self.contenu[indice_nouvel_emplacement] = valeur
self.nb +=1
def retirer(self):
if self.est_vide():
raise IndexError("File vide")
valeur_retirée = self.contenu[self.premier]
self.nb-=1
self.premier = ( self.premier + 1) % len ( self.contenu)
Question 3.5
Remplacer les pointillés dans les deux méthodes est_vide(self) et est_pleine(self)
Question 3.6
Créer un objet Filebornee de 10 cases
Remplir la file avec les données 1, 5, 6, 2, 3, 1, 5, 4, 2, 8 ( 8 est fin de File)
Retirer les trois premières valeurs de la file.
Ajouter l'élément 14 en fin de File, afficher l'indice de son emplacement, justifier cet indice par le calcul avec la relation donnée ci-dessus.
Créé avec HelpNDoc Personal Edition: Créer des fichiers d'aide pour la plateforme Qt Help