Les structures de données jouent un rôle clé dans le monde de la programmation. Ils nous aident à organiser nos données de manière à pouvoir les utiliser efficacement. La pile est l’une des structures de données les plus simples.
Découvrons la pile et son implémentation en Python.
Table des matières
Qu’est-ce qu’une pile ?
Une pile est similaire à la pile de livres, de chaises, etc., dans la vraie vie. Et il suit le principe Last-in/First-out (LIFO). C’est la structure de données la plus simple. Voyons le scénario avec un exemple concret.
Disons que nous avons une pile de livres comme suit.
Lorsque nous voulons le troisième livre du haut alors, nous devons retirer les deux premiers livres du haut pour sortir le troisième livre. Ici, le livre le plus haut va en dernier sur la pile et vient en premier de la pile. La pile de structure de données suit le même principe Last-in/First-out (LIFO) en programmation.
Opérations dans la pile
Il y a principalement deux opérations dans une pile
1. pousser (données)
Ajoute ou pousse les données dans la pile.
2. pop()
Supprime ou fait apparaître l’élément le plus haut de la pile.
Voir les illustrations ci-dessous des opérations push et pop.
Nous allons écrire quelques fonctions d’assistance qui nous aideront à obtenir plus d’informations sur la pile.
Voyons-les.
coup d’oeil()
Renvoie l’élément le plus haut de la pile.
est vide()
Retourne si la pile est vide ou non.
Assez d’aspects conceptuels de la structure de données de la pile. Passons à l’implémentation sans plus tarder.
Je suppose que vous avez installé python sur votre PC, sinon vous pouvez également essayer le compilateur en ligne.
Implémentation de la pile
L’implémentation de la pile est la plus simple par rapport aux autres implémentations de structure de données. Nous pouvons implémenter une pile de plusieurs manières en Python.
Voyons-les tous un par un.
#1. Liste
Nous allons implémenter la pile en utilisant la liste dans une classe. Voyons pas à pas l’implémentation de la pile.
Étape 1 : écrivez une classe appelée Stack.
class Stack: pass
Étape 2 : Nous devons conserver les données dans une liste. Ajoutons une liste vide dans la classe Stack avec des éléments de nom.
class Stack: def __init__(self): self.elements = []
Étape 3 : Pour pousser les éléments dans la pile, nous avons besoin d’une méthode. Écrivons une méthode push qui prend des données comme argument et les ajoutons à la liste des éléments.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
Étape 4 : De même, écrivons la méthode pop qui fait sortir l’élément le plus haut de la pile. Nous pouvons utiliser la méthode pop du type de données list.
class Stack: ## ... def pop(self): return self.elements.pop()
Nous avons terminé l’implémentation de la pile avec les opérations requises. Ajoutons maintenant les fonctions d’assistance pour obtenir plus d’informations sur la pile.
Étape 5 : Nous pouvons obtenir l’élément le plus haut de la pile en utilisant l’index négatif. Le code élément[-1] renvoie le dernier de la liste. C’est l’élément le plus haut de la pile dans notre cas.
class Stack: ## ... def peek(self): return self.elements[-1]
Étape 6 : Si la longueur de la liste des éléments est 0, alors la pile est vide. Écrivons une méthode qui retourne si l’élément est vide ou non.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Nous avons terminé l’implémentation de la pile en utilisant le type de données de liste.
Oh! attendez, nous venons de l’implémenter. Mais, je n’ai pas vu comment l’utiliser. Comment l’utiliser alors ?
Venez nous allons voir comment le mettre en œuvre. Nous devons créer un objet pour que la classe Stack l’utilise. Ce n’est pas grave. Faisons-le d’abord.
class Stack:
## ...
if __name__ == '__main__':
stack = Stack()Nous avons créé l’objet pile et sommes prêts à l’utiliser. Suivons les étapes ci-dessous pour tester les opérations de la pile.
- Vérifiez si la pile est vide ou non en utilisant la méthode is_empty. Il doit renvoyer True.
- Poussez les chiffres 1, 2, 3, 4, 5 dans la pile en utilisant la méthode push.
- La méthode is_empty doit renvoyer False. Vérifie ça.
- Imprimez l’élément le plus haut en utilisant la méthode Peek.
- Pop l’élément de la pile en utilisant la méthode pop.
- Vérifiez l’élément Peek. Il devrait renvoyer l’élément 4.
- Maintenant, pop tous les éléments de la pile.
- La méthode is_empty doit renvoyer True. Vérifie ça.
Notre implémentation de pile est terminée si elle passe toutes les étapes ci-dessus. Essayez d’écrire le code pour les étapes ci-dessus.
Avez-vous écrit le code? Non, ne vous inquiétez pas, vérifiez le code ci-dessous.
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()
## checking is_empty method -> true
print(stack.is_empty())
## pushing the elements
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
## again checking is_empty method -> false
print(stack.is_empty())
## printing the topmost element of the stack -> 5
print(stack.peek())
## popping the topmost element -> 5
stack.pop()
## checking the topmost element using peek method -> 4
print(stack.peek())
## popping all the elements
stack.pop()
stack.pop()
stack.pop()
stack.pop()
## checking the is_empty method for the last time -> true
print(stack.is_empty())
Hourra! nous avons terminé l’implémentation de la pile à partir de zéro en utilisant le type de données list. Vous verrez la sortie comme mentionné ci-dessous si vous exécutez le code ci-dessus.
True False 5 4 True
Nous pouvons directement utiliser le type de données list comme pile. L’implémentation de la pile ci-dessus vous aide également à comprendre l’implémentation de la pile dans d’autres langages de programmation.
Vous pouvez également consulter ces articles liés à la liste.
Voyons le deque intégré du module intégré collections qui peut agir comme une pile.
#2. deque de collections
Il est implémenté comme une file d’attente à double extrémité. Puisqu’il prend en charge l’ajout et la suppression d’éléments des deux extrémités. Nous pouvons donc l’utiliser comme une pile. On peut lui faire suivre le principe LIFO de la pile.
Il est implémenté à l’aide d’autres structures de données appelées liste doublement chaînée. Ainsi, les performances d’insertion et de suppression d’éléments sont cohérentes. L’accès aux éléments de la liste chaînée du milieu prenait un temps O(n). Nous pouvons l’utiliser comme une pile car il n’est pas nécessaire d’accéder aux éléments du milieu à partir de la pile.
Avant d’implémenter la pile, voyons les méthodes utilisées pour implémenter la pile à l’aide de la file d’attente.
- append(data) – utilisé pour pousser les données vers la pile
- pop() – utilisé pour supprimer l’élément le plus haut de la pile
Il n’y a pas de méthodes alternatives pour peek et is_empty. Nous pouvons imprimer toute la pile à la place de la méthode peek. Ensuite, nous pouvons utiliser la méthode len pour vérifier si la pile est vide ou non.
Implémentons la pile en utilisant deque du module collections.
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
C’est ça. Nous avons appris à implémenter la pile en utilisant le deque du module intégré collections. Vous obtiendrez la sortie comme mentionné ci-dessous si vous exécutez le programme ci-dessus.
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Jusqu’à présent, nous avons vu deux façons d’implémenter la pile. Existe-t-il d’autres moyens d’implémenter une pile ? Ouais! Voyons la dernière façon d’implémenter une pile dans ce tutoriel.
#3. LifoQueue
Le nom LifoQueue lui-même indique qu’il suit le principe LIFO. Par conséquent, nous pouvons l’utiliser comme une pile sans aucun doute. Il provient de la file d’attente du module intégré. Le LifoQueue fournit quelques méthodes pratiques qui sont utiles dans l’implémentation de la pile. Voyons-les
- put(data) – ajoute ou pousse les données dans la file d’attente
- get () – supprime ou fait apparaître l’élément le plus haut de la file d’attente
- vide () – renvoie si la pile est vide ou non
- qsize() – renvoie la longueur de la file d’attente
Implémentons la pile en utilisant LifoQueue du module de file d’attente.
from queue import LifoQueue
## creating LifoQueue object
stack = LifoQueue()
## checking whether stack is empty or not -> true
print(stack.empty())
## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
## again checking whether stack is empty or not -> false
print(stack.empty())
## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())
## checking the stack size
print("Size", stack.qsize())
print(stack.get())
print(stack.get())
## checking the whether stack is empty or not for the last time -> true
print(stack.empty())
Vous obtiendrez la sortie mentionnée ci-dessous si vous exécutez le programme ci-dessus sans le modifier.
True False 5 4 3 Size 2 2 1 True
Application de la pile
Maintenant, vous avez suffisamment de connaissances sur les piles pour l’appliquer à des problèmes de programmation. Voyons un problème et résolvons-le en utilisant une pile.
Étant donné une expression, écrivez un programme pour vérifier si les parenthèses, les accolades, les accolades sont correctement équilibrées ou non.
Voyons quelques exemples.
Saisir: « [{}]([]) »
Sortie : Équilibré
Saisir: « {[}]([]) »
Sortie : non équilibrée
Nous pouvons utiliser la pile pour résoudre le problème ci-dessus. Voyons les étapes pour résoudre le problème.
- Créez une pile pour stocker les caractères.
- Si la longueur de l’expression est impaire, alors l’expression n’est pas équilibrée
- Itérer dans l’expression donnée.
- Si le caractère courant est le crochet ouvrant de ( ou { ou [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]puis sortez de la pile.
- Si le caractère sauté correspond à la parenthèse de départ, continuez, sinon les parenthèses ne sont pas équilibrées.
- Après l’itération, si la pile est vide, l’équation est équilibrée, sinon l’équation est non équilibrée.
Nous pouvons utiliser le type de données set pour la vérification des correspondances entre parenthèses.
## stack
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):
## checking the length of the expression
if len(expression) % 2 != 0:
## not balanced if the length is odd
return False
## for checking
opening_brackets = set('([{')
pairs = set([ ('(',')'), ('[',']'), ('{','}') ])
## stack initialization
stack = Stack()
## iterating through the given expression
for bracket in expression:
## checking whether the current bracket is opened or not
if bracket in opening_brackets:
## adding to the stack
stack.push(bracket)
else:
## popping out the last bracket from the stack
popped_bracket = stack.pop()
## checking whether popped and current bracket pair
if (popped_bracket, bracket) not in pairs:
return False
return stack.is_empty()
if __name__ == '__main__':
if balance_check('[{}]([])'):
print("Balanced")
else:
print("Not Balanced")
if balance_check('{[}]([])'):
print("Balanced")
else:
print("Not Balanced")Nous pouvons utiliser la pile pour résoudre de nombreux autres problèmes. Le problème ci-dessus en fait partie. Essayez d’appliquer le concept de pile là où vous pensez que cela vous convient le mieux.
Conclusion
Yah ! Vous avez terminé le didacticiel. J’espère que vous avez apprécié le tutoriel autant que moi lors de sa réalisation. Voilà pour le tuto.
Bon codage 🙂 👨💻