Numérique et Sciences Informatiques > Algorithmique : Structures de Données Avancées > Piles et Files > Implémentation (avec des listes ou des tableaux)
Implémentation des Piles et Files en Python
Ce cours explore l'implémentation des piles et des files en Python en utilisant les listes et les tableaux. Nous examinerons les opérations fondamentales, les avantages et les inconvénients de chaque approche, et fournirons des exemples de code clairs et concis pour une compréhension approfondie.
Introduction aux Piles et Files
Piles (Stacks) et Files (Queues) sont des structures de données fondamentales en informatique. Elles permettent de stocker et de gérer des collections d'éléments selon des règles spécifiques. Comprendre leur fonctionnement est crucial pour concevoir des algorithmes efficaces et résoudre divers problèmes.
Implémentation d'une Pile avec une Liste Python
Python offre des listes, qui sont des structures de données dynamiques, parfaites pour implémenter des piles. Voici comment :
Exemple de Code:
python
class Pile:
def __init__(self):
self.elements = []
def est_vide(self):
return len(self.elements) == 0
def empiler(self, element):
self.elements.append(element)
def depiler(self):
if not self.est_vide():
return self.elements.pop()
else:
return None # Ou lever une exception
def sommet(self):
if not self.est_vide():
return self.elements[-1]
else:
return None # Ou lever une exception
# Utilisation:
pile = Pile()
pile.empiler(10)
pile.empiler(20)
print(pile.sommet()) # Affiche 20
print(pile.depiler()) # Affiche 20
print(pile.est_vide()) # Affiche False
Avantages: Simplicité d'implémentation, taille dynamique.
Inconvénients: Moins performant pour de très grandes piles que les tableaux (en particulier pour les opérations d'insertion et de suppression au milieu, mais ce n'est pas pertinent ici car on ajoute/supprime au sommet).
Implémentation d'une File avec une Liste Python
Comme pour les piles, on peut utiliser des listes Python pour implémenter des files. Cependant, pour une performance optimale, il est recommandé d'utiliser `collections.deque` (double-ended queue), qui est optimisée pour les opérations d'ajout et de suppression aux deux extrémités.
Exemple de Code:
python
from collections import deque
class File:
def __init__(self):
self.elements = deque()
def est_vide(self):
return len(self.elements) == 0
def enfiler(self, element):
self.elements.append(element)
def defiler(self):
if not self.est_vide():
return self.elements.popleft()
else:
return None # Ou lever une exception
def premier(self):
if not self.est_vide():
return self.elements[0]
else:
return None # Ou lever une exception
# Utilisation:
file = File()
file.enfiler(10)
file.enfiler(20)
print(file.premier()) # Affiche 10
print(file.defiler()) # Affiche 10
print(file.est_vide()) # Affiche False
Avantages: `deque` offre une performance optimale pour les opérations d'enfilement et de défilement. Facile à utiliser.
Inconvénients: Un peu plus complexe que l'implémentation avec une liste simple (mais la différence est minime).
Implémentation d'une Pile avec un Tableau (Liste Python Fixe)
Bien que les listes Python soient dynamiques, on peut simuler un tableau fixe en définissant une taille maximale pour la pile. Ceci peut être utile dans certains contextes où la taille maximale est connue à l'avance.
Exemple de Code:
python
class PileTableau:
def __init__(self, taille):
self.taille_max = taille
self.elements = [None] * taille
self.sommet = -1
def est_vide(self):
return self.sommet == -1
def est_pleine(self):
return self.sommet == self.taille_max - 1
def empiler(self, element):
if not self.est_pleine():
self.sommet += 1
self.elements[self.sommet] = element
else:
print("Pile pleine!")
def depiler(self):
if not self.est_vide():
element = self.elements[self.sommet]
self.elements[self.sommet] = None # Pour éviter de garder des références inutiles
self.sommet -= 1
return element
else:
return None # Ou lever une exception
def sommet(self):
if not self.est_vide():
return self.elements[self.sommet]
else:
return None # Ou lever une exception
# Utilisation:
pile = PileTableau(5)
pile.empiler(10)
pile.empiler(20)
print(pile.sommet()) # Affiche 20
print(pile.depiler()) # Affiche 20
print(pile.est_vide()) # Affiche False
Avantages: Peut être plus performant que les listes dynamiques dans certains cas (moins de réallocations mémoire).
Inconvénients: Taille fixe, nécessite de connaître la taille maximale à l'avance. Plus complexe à implémenter.
Implémentation d'une File avec un Tableau Circulaire
L'implémentation d'une file avec un tableau simple présente un problème : après plusieurs enfilements et défilements, l'espace utilisé au début du tableau est gaspillé. Le tableau circulaire résout ce problème en réutilisant cet espace.
Exemple de Code:
python
class FileCirculaire:
def __init__(self, taille):
self.taille_max = taille
self.elements = [None] * taille
self.tete = 0
self.queue = 0
def est_vide(self):
return self.tete == self.queue
def est_pleine(self):
return (self.queue + 1) % self.taille_max == self.tete
def enfiler(self, element):
if not self.est_pleine():
self.elements[self.queue] = element
self.queue = (self.queue + 1) % self.taille_max
else:
print("File pleine!")
def defiler(self):
if not self.est_vide():
element = self.elements[self.tete]
self.elements[self.tete] = None # Pour éviter de garder des références inutiles
self.tete = (self.tete + 1) % self.taille_max
return element
else:
return None # Ou lever une exception
def premier(self):
if not self.est_vide():
return self.elements[self.tete]
else:
return None # Ou lever une exception
# Utilisation:
file = FileCirculaire(5)
file.enfiler(10)
file.enfiler(20)
file.enfiler(30)
file.enfiler(40)
print(file.premier()) # Affiche 10
print(file.defiler()) # Affiche 10
print(file.enfiler(50))
print(file.est_pleine())
Avantages: Utilisation efficace de la mémoire, pas de gaspillage d'espace.
Inconvénients: Plus complexe à implémenter que les autres approches.
Ce qu'il faut retenir
empiler/push, dépiler/pop, enfiler/enqueue, défiler/dequeue, sommet/peek, premier/front, est_vide/isEmpty.
FAQ
-
Quelle implémentation de file est la plus performante en Python ?
L'implémentation utilisant `collections.deque` est généralement la plus performante pour les files en Python, car elle est optimisée pour les opérations d'ajout et de suppression aux deux extrémités. -
Quand devrais-je utiliser une pile plutôt qu'une file ?
Utilisez une pile lorsque l'ordre de traitement des éléments est important et que le dernier élément ajouté doit être traité en premier (LIFO). Utilisez une file lorsque l'ordre d'arrivée des éléments est important et que le premier élément arrivé doit être traité en premier (FIFO). -
Quels sont les inconvénients de l'implémentation d'une pile avec un tableau de taille fixe ?
L'inconvénient principal est que la taille de la pile est limitée et doit être connue à l'avance. Si la pile atteint sa capacité maximale, il ne sera plus possible d'ajouter de nouveaux éléments.