Python 8 : Les files
Les files
Introduction
This article is about the Queue data structure. In order to keep up with this course, you should have an idea about Python 3, some necessary concepts about data structures like List and OOP(Object Oriented Programming) .
Une file est une simple structure de données qu'on peut employer dans notre vie quotidienne, on essaiera d'expliquer par un exemple le concept des files par les files d'attente.
vous êtes dans une file d'attente et vous attendez à ce que vous soyez servi:
- des personnes s'ajoutent à la file d'attente d'un côté et d'autres la quittent d'un autre côté.
- la première personne à arriver est la première personne à sortir de la file.
- une fois tout le monde est servi, il n'y a personne qui attend de quitter la file.
Projetons ce qu'on vient d'expliquer sur les files comme étant des structures de données:
- Les files sont ouvertes des deux côtés extremums, des éléments peuvent être ajoutés à la queue de la file et d'autres peuvent être retirés de la tête de la file.
- le premier élément ajouté et le premier à être retiré (First In First Out).
- Si tous les éléments sont retirés, alors la file devient vide et si vous essayez de retirer d'autres éléments, un message d'avertissement va être lancé.
- Si la file est pleine et vous tentez d'ajouter un élément, un message d'avertissement sera lancé.
Notes:
- Le point d'entrée et de la sortie d'une file sont différents l'un de l'autre.
- Enfiler- Ajouter un élément à la file.
- Défiler - Enlever un élément de la file.
- L'accès aléatoire à la file n'est pas permis- Vous ne pouvez pas ajouter ou enlever un élément du milieu de la file.
Implementation
On va voir trois différents implémentations. On utilisera les listes pour la première, la bibliothèque deque pour la deuxième et un tableau pour la dernière.
L'implémentation des files avec une liste
On va définir une classe file et on va lui ajouter des méthodes pour performer les opérations ci-dessous:
- Enfiler des éléments au début de la file et lancer un avertissement si la file est pleine.
- Défiler des éléments de la fin de la file et lancer un avertissement si la file est vide.
- Contrôler la taille de la file.
- Afficher les éléments de la file.
class file
# le constructeur crée une liste
def inint_file(self):
self.file = list()
# ajouter des elements à la file
def enfiler(self,info):
#vérifier pour éviter une entrée deux fois( n'est pas nécessaire )
if info not in self.file:
self.file.insert(0,info)
return True
return False
#enlever le dernier element de la file
def defiler(self):
if len(self.file)>0:
return self.file.pop()
return ("File vide!")
#avoir la taille de la file
def size(self):
return len(self.file)
#afficher les elements de la file
def affFile(self):
return self.file
maFile = file()
print(maFile.enfiler(2)) #affiche True
print(maFile.enfiler(3)) #affiche True
print(maFile.enfiler(1)) #affiche True
print(maFile.enfiler(3)) #affiche False
print(maFile.enfiler(4)) #affiche True
print(maFile.size()) #affiche 4
print(maFile.defiler()) #prints 2
print(maFile.defiler()) #prints 3
print(maFile.defiler()) #prints 1
print(maFile.defiler()) #prints 4
print(maFile.size()) #prints 0
print(maFile.defiler()) #affiche File vide!
L'implémentation des files en utilisant deque
En important la bibliothèque deque, celle-ci nous fourni des commandes prédéfinies comme append() pour enfiler et la commande popleft() pour défiler.
#Importer la bibliothèque
from collections import deque
#creer une file
file = deque([1,5,7,4])
#enfiler des elements à la file
file.append(9) #[1,5,7,4,9]
file.append(11) #[1,5,7,4,9,11]
#defiler des elements de la file
file.popleft() #[5,7,4,9,11]
file.popleft() #[7,4,9,11]
#affichage des elements de la file
print(file)
Note:
Cette implémentation est plus efficace que la première car à chaque fois que vous insérez un élément à la position 0, tous les autres éléments seront déplacés d'une seule position.
l'implémentation des files en utilisant les tableaux
Les listes en Python ont facilité l'implémentation d'une file. Toutefois, il faut tenir compte de quelques points:
- Les éléments sont ajoutés à la fin et enlevés du début.
- Traiter les listes comme des tableaux(une taille fixe)- borner la liste virtuellement pour s'assurer que la taille de la liste ne dépasse pas une taille limite.
- Utiliser un pointeur sur la queue pour surveiller les éléments ajoutés à la file-le pointeur sur la queue va toujours pointer sur le prochain espace vide.Quand la file est pleine, le pointeur sur la queue dépassera la taille déclarée.
- Utiliser un pointeur sur la tête pour surveiller les éléments retirés de la file - le pointeur sur la tête va pointer sur l'element qui va être défilé par la suite. Après une opération de défilement, le pointeur sur la tête va pointer sur le second élément dans la file. Aucun élément ne sera retiré de la file car une fois un élément est retiré, la liste déplace automatiquement ses éléments vers la gauche d'une position. Cela veut dire que la position 0 contiendra toujours un élément, ce qui est à l'encontre du concept de la file.
- Utiliser une méthode de réinitialisation - Cette méthode est appelée pour réinitialiser la file. Par exemple, si la file contient trois éléments alors la tête = 0, queue = 4. Maintenant, si on défile tous les éléments, la file sera vide ce qui veut dire que tête=queue=4.Si on veut alors défiler un élément, cela se produira au niveau de la position 4 ce qui est faux. Par conséquent, il est nécessaire de réinitialiser ces pointeurs à 0. Notez que puisqu'on ne supprime pas vraiment les éléments, la liste contient toujours les éléments "supprimés", par conséquent, une nouvelle liste doit être créé.
Algorithme
- Créer une liste et un entier MaxSize en désignant une taille maximale virtuelle de la liste.
- la tête et la queue sont initialisées à 0.
- la méthode de Size:
- calculer le nombre d'éléments de la file ->taille = queue -tête
- la méthode de réinitialisation(Reset):
- réinitialiser la tête et la queue à 0.
- créer une nouvelle file .
- l'opération d'enfiler
- vérifier si la taille est inférieur à MaxSize:
- si oui, pop(sauter) le premier élément de la liste et incrémenter la tête de 1
- sinon:
- faire appel Reset
- afficher le message de file vide
- vérifier si la taille est inférieur à MaxSize:
Programme
class file:
#constructeur
def inint_file(self):
self.file = list()
self.maxSize = 8
self.tete = 0
self.queue = 0
#Ajouter des elements
def enfiler(self,info):
#verifier si la file est pleine
if self.size() >= self.maxSize:
return ("File Pleine")
self.file.append(data)
self.queue += 1
return True
#supprimer des elements
def defiler(self):
#verifier si la file est vide
if self.size() <= 0:
self.initFile()
return ("File Vide")
info = self.file[self.tete]
self.tete+=1
return info
#Calculate size
def size(self):
return self.queue - self.tete
#Reinitialiser la file
def initFile(self):
self.queue = 0
self.tete = 0
self.file = list()
q = file()
print(q.enfiler(1))#affiche True
print(q.enfiler(2))#affiche True
print(q.enfiler(3))#affiche True
print(q.enfiler(4))#affiche True
print(q.enfiler(5))#affiche True
print(q.enfiler(6))#affiche True
print(q.enfiler(7))#affiche True
print(q.enfiler(8))#affiche True
print(q.enfiler(9))#affiche File Pleine
print(q.size())#affiche 8
print(q.defiler())#affiche 8
print(q.defiler())#affiche 7
print(q.defiler())#affiche 6
print(q.defiler())#affiche 5
print(q.defiler())#affiche 4
print(q.defiler())#affiche 3
print(q.defiler())#affiche 2
print(q.defiler())#affiche 1
print(q.defiler())#affiche File Vide
#la file est Reinitialisée
print(q.enfiler(1))#affiche True
print(q.enfiler(2))#affiche True
print(q.enfiler(3))#affiche True
print(q.enfiler(4))#affiche True
Note:
L'élément 9 n'a pas été ajouté à la file, par conséquent la taille de la file ne change pas.
Il y'a d'autres méthodes qu'on peut utiliser comme celle pour retourner l'élément qui se trouve en tête de la file ou pour vérifier si la file est vide etc.
déclarer une liste et un entier MaxSize, déclarer une taille maximale de la file.
la tête et la queue sont initialisées à 0.
la méthode size
Posted on Utopian.io - Rewarding Open Source Contributors
Thank you for the contribution. It has been approved.
You can contact us on Discord.
[utopian-moderator]
Hey @raptorjesus I am @utopian-io. I have just upvoted you!
Achievements
Suggestions
Get Noticed!
Community-Driven Witness!
I am the first and only Steem Community-Driven Witness. Participate on Discord. Lets GROW TOGETHER!
Up-vote this comment to grow my power and help Open Source contributions like this one. Want to chat? Join me on Discord https://discord.gg/Pc8HG9x