Les structures de données sont essentielles en programmation. Elles permettent d’organiser l’information de manière à optimiser son utilisation. La pile est une structure particulièrement simple et efficace.
Explorons la pile et sa mise en œuvre avec Python.
Qu’est-ce qu’une pile ?
Une pile est comparable à une pile de livres ou de chaises dans la vie courante. Elle suit un principe de fonctionnement dit « Dernier Entré, Premier Sorti » (DEPS ou LIFO en anglais). C’est l’une des structures de données les plus fondamentales. Illustrons cela avec un exemple concret.
Imaginons une pile de livres.
Si l’on souhaite atteindre le troisième livre en partant du haut, il faut retirer les deux livres supérieurs. Le dernier livre déposé sur la pile est donc le premier à en être retiré. En programmation, une pile de données suit ce même principe DEPS ou LIFO.
Opérations fondamentales d’une pile
Les deux actions principales associées à une pile sont :
1. Empiler (push)
Ajoute une donnée au sommet de la pile.
2. Dépiler (pop)
Retire la donnée située au sommet de la pile.
Les illustrations ci-dessous explicitent les opérations d’empilement et de dépilement.
Pour obtenir plus d’informations sur l’état de la pile, nous allons définir quelques fonctions auxiliaires :
Examinons-les.
Consulter (peek)
Retourne la donnée au sommet de la pile sans la retirer.
Est vide (is empty)
Indique si la pile est vide ou non.
Après cette introduction conceptuelle, passons sans tarder à l’implémentation.
Je suppose que Python est installé sur votre ordinateur. Sinon, vous pouvez utiliser un compilateur en ligne.
Mise en œuvre d’une pile
La pile est simple à implémenter comparée à d’autres structures de données. Avec Python, plusieurs approches sont possibles.
Explorons-les une par une.
#1. Utilisation d’une liste
Nous allons implémenter une pile à l’aide d’une liste, au sein d’une classe. Voici la démarche pas à pas :
Étape 1 : Définir une classe nommée Stack.
class Stack:
pass
Étape 2 : Les données seront stockées dans une liste. Ajoutons une liste vide, nommée elements, à la classe Stack.
class Stack:
def __init__(self):
self.elements = []
Étape 3 : Pour ajouter des éléments, il faut une méthode. Définissons une méthode push qui prend une donnée en argument et l’ajoute à la liste elements.
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
Étape 4 : Définissons de même une méthode pop qui retire l’élément situé au sommet de la pile. Nous pouvons utiliser la méthode pop propre aux listes en Python.
class Stack:
## ...
def pop(self):
return self.elements.pop()
L’implémentation des opérations essentielles de la pile est terminée. Ajoutons maintenant les fonctions auxiliaires pour obtenir plus d’informations sur l’état de la pile.
Étape 5 : L’élément situé au sommet de la pile correspond au dernier élément de la liste. L’accès au dernier élément de la liste se fait avec l’indice négatif -1. On peut donc utiliser elements[-1].
class Stack:
## ...
def peek(self):
return self.elements[-1]
Étape 6 : Si la longueur de la liste elements est 0, alors la pile est vide. Définissons une méthode qui retourne un booléen indiquant si la pile est vide ou non.
class Stack:
## ...
def is_empty(self):
return len(self.elements) == 0
L’implémentation de la pile à l’aide d’une liste est terminée !
Mais comment l’utiliser ? Il faut créer un objet de la classe Stack. C’est simple, faisons-le.
class Stack:
## ...
if __name__ == '__main__':
stack = Stack()
L’objet pile est créé, nous pouvons l’utiliser. Procédons par étapes pour tester les opérations de la pile :
- Vérifier si la pile est vide à l’aide de la méthode is_empty. Cela doit retourner True.
- Empiler les nombres 1, 2, 3, 4 et 5 avec la méthode push.
- La méthode is_empty doit retourner False.
- Afficher l’élément situé au sommet de la pile avec la méthode Peek.
- Dépiler un élément avec la méthode pop.
- Vérifier l’élément au sommet de la pile avec peek. Cela doit retourner 4.
- Dépiler tous les éléments de la pile.
- La méthode is_empty doit retourner True.
Si tous les tests sont validés, notre implémentation de la pile est correcte. Essayez d’écrire le code correspondant à ces étapes.
Vous n’avez pas écrit le code ? Pas de problème, voici une version complète.
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
stack = Stack()
## test de is_empty -> true
print(stack.is_empty())
## empilement des éléments
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
## test de is_empty à nouveau -> false
print(stack.is_empty())
## affichage de l'élément au sommet de la pile -> 5
print(stack.peek())
## dépilement de l'élément du sommet -> 5
stack.pop()
## vérification de l'élément au sommet via peek -> 4
print(stack.peek())
## dépilement de tous les éléments
stack.pop()
stack.pop()
stack.pop()
stack.pop()
## dernier test de is_empty -> true
print(stack.is_empty())
Bravo ! L’implémentation de la pile à partir de zéro, en utilisant une liste, est terminée. L’exécution du code ci-dessus doit afficher la sortie suivante :
True False 5 4 True
En réalité, une liste peut être directement utilisée comme une pile. L’implémentation ci-dessus permet de comprendre comment une pile est mise en œuvre dans d’autres langages.
Vous pouvez aussi consulter ces articles sur les listes.
Voyons maintenant comment utiliser deque du module collections, qui peut également jouer le rôle d’une pile.
#2. Utilisation de deque de collections
Un deque (double-ended queue) est une file d’attente à double extrémité. Il permet d’ajouter et de retirer des éléments des deux côtés. Par conséquent, il peut servir de pile, en respectant le principe LIFO.
Un deque est implémenté avec une liste doublement chaînée. L’insertion et la suppression d’éléments sont efficaces. L’accès aux éléments au milieu d’une liste chaînée prend un temps O(n), mais cela n’est pas nécessaire pour l’utilisation de deque comme pile. Seuls les éléments aux extrémités sont concernés.
Avant d’implémenter la pile, regardons les méthodes utilisées par deque :
- append(data) – ajoute la donnée au sommet de la pile
- pop() – retire l’élément du sommet de la pile
Il n’y a pas de méthodes dédiées pour peek ou is_empty. On peut afficher la pile complète en guise de peek, et utiliser len pour savoir si elle est vide.
Implémentons la pile avec deque du module collections :
from collections import deque ## création d'un objet deque stack = deque() ## verification de la pile vide -> true print(len(stack) == 0) ## empilement des éléments stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## vérification à nouveau -> false print(len(stack) == 0) ## affichage de la pile print(stack) ## dépilement de l'élément du haut -> 5 stack.pop() ## affichage de la pile print(stack) ## dépilement de tous les éléments stack.pop() stack.pop() stack.pop() stack.pop() ## dernière vérification, la pile est vide -> true print(len(stack) == 0)
Voilà ! L’implémentation de la pile avec deque du module collections est terminée. La sortie de ce programme devrait être :
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Deux méthodes d’implémentation de la pile ont été examinées. Y a-t-il d’autres solutions ? Bien sûr ! Voici la dernière méthode proposée.
#3. Utilisation de LifoQueue
LifoQueue, par son nom, indique clairement qu’il suit le principe LIFO. Il peut donc être utilisé comme une pile. Il est issu du module queue. LifoQueue propose des méthodes utiles à la mise en œuvre d’une pile :
- put(data) – ajoute ou empile une donnée
- get () – retire ou dépile l’élément du sommet
- empty () – indique si la pile est vide
- qsize() – renvoie la taille de la file d’attente
Implémentons une pile avec LifoQueue du module queue :
from queue import LifoQueue
## création d'un objet LifoQueue
stack = LifoQueue()
## vérification que la pile est vide -> true
print(stack.empty())
## empilement des éléments
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
## vérification à nouveau -> false
print(stack.empty())
## dépilement des éléments
print(stack.get())
print(stack.get())
print(stack.get())
## affichage de la taille
print("Size", stack.qsize())
print(stack.get())
print(stack.get())
## dernière vérification -> true
print(stack.empty())
Si vous exécutez ce programme sans le modifier, vous obtiendrez la sortie suivante :
True False 5 4 3 Size 2 2 1 True
Application des piles
Vous disposez maintenant de connaissances suffisantes pour appliquer les piles à des problèmes de programmation. Prenons un exemple que nous allons résoudre avec une pile.
Étant donné une expression, écrire un programme pour vérifier si les parenthèses, accolades et crochets sont correctement équilibrés.
Voici quelques exemples :
Entrée : « [{}]([]) »
Sortie : Équilibré
Entrée : « {[}]([]) »
Sortie : Non équilibré
Une pile est parfaitement adaptée à ce problème. Voici les étapes de la résolution :
- Créer une pile pour stocker les caractères.
- Si la longueur de l’expression est impaire, alors l’expression est déséquilibrée.
- Parcourir l’expression :
- Si le caractère courant est une parenthèse ouvrante ( ou { ou [, l’empiler.
- Si le caractère courant est une parenthèse fermante ) ou } ou ], dépiler.
- Si la parenthèse dépilée correspond à la parenthèse courante, continuer, sinon, l’expression n’est pas équilibrée.
- Après avoir parcouru l’expression, si la pile est vide, l’expression est équilibrée, sinon elle est déséquilibrée.
Un ensemble (set) peut être utilisé pour vérifier la correspondance entre les parenthèses.
## pile
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
def balance_check(expression):
## vérification de la longueur
if len(expression) % 2 != 0:
## déséquilibrée si impaire
return False
## pour la vérification
opening_brackets = set('([{')
pairs = set([ ('(',')'), ('[',']'), ('{','}') ])
## initialisation de la pile
stack = Stack()
## parcours de l'expression
for bracket in expression:
## est-ce que la parenthèse courante est ouvrante ?
if bracket in opening_brackets:
## on l'empile
stack.push(bracket)
else:
## on dépile la dernière parenthèse
popped_bracket = stack.pop()
## on vérifie la correspondance
if (popped_bracket, bracket) not in pairs:
return False
return stack.is_empty()
if __name__ == '__main__':
if balance_check('[{}]([])'):
print("Équilibré")
else:
print("Non équilibré")
if balance_check('{[}]([])'):
print("Équilibré")
else:
print("Non équilibré")
Les piles peuvent être utilisées pour résoudre de nombreux autres problèmes. Celui-ci n’en est qu’un exemple. N’hésitez pas à appliquer le concept de pile chaque fois que cela vous semble pertinent.
Conclusion
Félicitations ! Vous avez terminé ce tutoriel. J’espère que vous avez apprécié autant que j’ai aimé le créer. Ce tutoriel est maintenant terminé.
Bon codage 🙂 👨💻