Comprendre l'implémentation des piles en Python

Les structures de données jouent un rôle clé dans le monde de la programmation. Elles nous aident à organiser nos données de manière à ce qu’elles puissent être utilisées efficacement. La pile est l’une des structures de données les plus simples

Découvrons la pile et son implémentation en Python

Qu’est-ce qu’une pile ?

Une pile est similaire à une pile de livres, de chaises, etc. dans la vie réelle. Elle suit le principe du dernier entré/premier sorti (LIFO ). Il s’agit de la structure de données la plus simple. Voyons le scénario à l’aide d’un exemple concret

Supposons que nous ayons une pile de livres comme suit

Lorsque nous voulons le troisième livre du haut, nous devons retirer les deux premiers livres du haut pour obtenir le troisième livre. Ici, le livre le plus haut va en dernier dans la pile et vient en premier de la pile. La structure de données stack 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()

Retire ou fait sortir l’élément le plus haut de la pile

Vous trouverez ci-dessous des illustrations des opérations push et pop

Nous allons écrire quelques fonctions d’aide qui nous aideront à obtenir plus d’informations sur la pile

Voyons-les

peek()

Renvoie l’élément le plus haut de la pile

is_empty()

Indique si la pile est vide ou non

Assez d’aspects conceptuels de la structure de données de la pile. Passons maintenant à l’implémentation sans plus attendre

Je suppose que vous avez installé Python sur votre PC. Si ce n’est pas le cas, vous pouvez également essayer le compilateur en ligne

Implémentation de la pile

L’implémentation de la pile est la plus simple comparée aux autres implémentations de structures de données. Nous pouvons implémenter une pile de plusieurs façons en Python

Voyons-les une à une

#1. Liste

Nous allons implémenter la pile en utilisant la liste dans une classe. Voyons l’implémentation de la pile étape par étape

Étape 1 : Écrivez une classe appelée Stack

classe 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. Ecrivons une méthode push qui prend des données en argument et les ajoute à 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 la même manière, écrivons la méthode pop qui extrait l’élément le plus haut de la pile. Nous pouvons utiliser la méthode pop du type de données liste

class Stack :
## ...
def pop(self) :
return self.elements.pop()

Nous avons terminé l’implémentation de la pile avec les opérations requises. Maintenant, ajoutons les fonctions d’aide 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 <span data-token-index="2" data-reactroot="">element[-1]</span> renvoie le dernier élément de la liste. Dans notre cas, il s’agit de l’élément le plus haut de la pile

class Stack :
## ...

def peek(self) :
return self.elements[-1]

Étape 6 : Si la longueur de la liste des éléments est de 0, alors la pile est vide. Ecrivons une méthode qui renvoie 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 liste

Oh ! attendez, nous venons juste de l’implémenter. Mais nous n’avons pas vu comment l’utiliser. Comment l’utiliser alors ?

Voyons comment l’implémenter. Nous devons créer un objet pour la classe Stack afin de l’utiliser. Ce n’est pas bien grave. Commençons par le faire

class Stack :
 ## ...

if __name__ == '__main__' :
 stack = Stack()

Nous avons créé l’objet stack et sommes prêts à l’utiliser. Suivons les étapes suivantes pour tester les opérations de la pile

Vérifiez si la pile est vide ou non en utilisant la méthode is_empty . Elle doit renvoyer True.
Insérez les nombres 1, 2, 3, 4, 5 dans la pile à l’aide de la méthode push .
La méthode is_empty doit renvoyer False. Vérifiez-le.
Imprimez l’élément le plus haut à l’aide de la méthode peek .
Retirez l’élément de la pile à l’aide de la méthode pop .
Vérifiez l’élément peek. Il doit renvoyer l’élément 4.
Maintenant, retirez tous les éléments de la pile.
La méthode is_empty doit renvoyer True. Vérifiez-le.

Notre implémentation de la 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()
    
 ## vérification de la méthode is_empty -> true
 print(stack.is_empty())

 ## pousser les éléments
 stack.push(1)
 stack.push(2)
 stack.push(3)
 stack.push(4)
 stack.push(5)

 ## vérifiant à nouveau la méthode is_empty -> false
 print(stack.is_empty())

 ## imprimant l'élément le plus haut de la pile -> 5
 print(stack.peek())

 ## extraction de l'élément le plus haut -> 5
 stack.pop()

 ## vérification de l'élément le plus haut à l'aide de la méthode peek -> 4
 print(stack.peek())

 ## extraction de tous les éléments
 stack.pop()
 stack.pop()
 stack.pop()
 stack.pop()

 ## vérification de la méthode is_empty pour la dernière fois -> true
 print(stack.is_empty())

Nous avons terminé l’implémentation de la pile à partir de zéro en utilisant le type de données liste . Si vous exécutez le code ci-dessus, vous obtiendrez la sortie mentionnée ci-dessous

True
False


True

Nous pouvons directement utiliser le type de données liste comme une pile. L’implémentation ci-dessus de la pile vous aide à comprendre l’implémentation de la pile dans d’autres langages de programmation

Vous pouvez également consulter ces articles sur les listes

Vérifier si la liste est vide

Aplatir une liste

Convertir une liste en dictionnaire

Voyons la fonction deque du module intégré collections qui peut agir comme une pile

#2. deque from collections

Il est implémenté comme une file d’attente à double extrémité. Puisqu’elle supporte l’ajout et le retrait d’éléments aux deux extrémités, nous pouvons l’utiliser comme une pile. Nous pouvons donc l’utiliser comme une pile. Nous pouvons lui faire suivre le principe LIFO de la pile

Elle est mise en œuvre à l’aide d’autres structures de données appelées liste doublement liée. Ainsi, les performances d’insertion et de suppression d’éléments sont cohérentes. L’accès aux éléments de la liste doublement liée prend O(n) temps. 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) – permet d’ajouter les données à la pile
pop() – utilisée pour retirer l’élément le plus haut de la pile

Il n’existe 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

## création de l'objet deque
stack = deque()

## vérification si la pile est vide ou non -> true
print(len(stack) == 0)

## pousser les éléments
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## vérifie à nouveau si la pile est vide ou non -> false
print(len(stack) == 0)

## imprime la pile
print(stack)

## extrait l'élément le plus haut -> 5
stack.pop()

## impression de la pile
print(stack)

extraction de tous les éléments
stack.pop()
stack.pop()
stack.pop()
stack.pop()

vérification du fait que la pile est vide ou non pour la dernière fois -> true
print(len(stack) == 0)

Voilà, c’est fait. Nous avons appris à implémenter une pile en utilisant le deque du module intégré collections . Vous obtiendrez la sortie mentionnée 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 façons d’implémenter une pile ? Oui, c’est possible ! 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 . Nous pouvons donc l’utiliser comme une pile sans aucun doute. Il provient du module intégré queue. Le LifoQueue fournit quelques méthodes pratiques qui sont utiles dans l’implémentation d’une pile. Voyons-les

put(data) – ajoute ou pousse les données dans la file d’attente
get() – enlève ou retire l’élément le plus haut de la file d’attente
empty() – indique 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 queue

from queue import LifoQueue

## création d'un objet LifoQueue
stack = LifoQueue()

## vérification si la pile est vide ou non -> true
print(stack.empty())

## pousser les éléments
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## vérifier à nouveau si la pile est vide ou non -> false
print(stack.empty())

## extraction de tous les éléments
print(stack.get())
print(stack.get())
print(stack.get())

## vérification de la taille de la pile
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

vérifier si la pile est vide ou non pour la dernière fois -> 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


Size 2


True

Application de la pile

Vous avez maintenant suffisamment de connaissances sur les piles pour les appliquer à des problèmes de programmation. Voyons un problème et résolvons-le à l’aide d’une pile

Étant donné une expression, écrivez un programme pour vérifier si les parenthèses, les accolades et les accolades bouclées sont équilibrées correctement ou non

Voyons quelques exemples

Entrée : “[{}]([])”

Sortie : Équilibré

Entrée : “{[}]([])”

Sortie : Non équilibré

Nous pouvons utiliser la pile pour résoudre le problème ci-dessus. Voyons les étapes à suivre pour résoudre le problème

Créez une pile pour stocker les caractères.
Si la longueur de l’expression est impaire, l’expression n’est pas équilibrée
Interrogez l’expression donnée
- Si le caractère courant est le crochet ouvrant de ( ou { ou [, placez-le sur la pile.
- Sinon, si le caractère actuel est un crochet fermant ) ou } ou ], il est extrait de la pile.
- Si le caractère extrait correspond au crochet de départ, continuez, sinon les crochets ne sont pas équilibrés.
Après l’itération, si la pile est vide, l’équation est équilibrée , sinon l’équation n’ est pas équilibrée.

Nous pouvons utiliser le type de données set pour vérifier la correspondance des parenthèses

## stack
classe 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 de l'expression
 if len(expression) % 2 != 0 :
 ## pas équilibrée si la longueur est impaire
 return False
    
 ## pour la vérification
 opening_brackets = set('([{')
 pairs = set([ ('(',')'), ('[',']'), ('{','}') ])
    
 ## initialisation de la pile
 stack = Stack()
    
 ## itération à travers l'expression donnée
 for bracket in expression :

       ## vérifier si la parenthèse courante est ouverte ou non
 if bracket in opening_brackets :
 ## ajouter à la pile
 stack.push(bracket)
 else :
 ## extraction du dernier crochet de la pile
 popped_bracket = stack.pop()
        
 ## vérification de l'existence d'une paire entre le crochet extrait et le crochet actuel
 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 est un. Essayez d’appliquer le concept de pile là où vous pensez qu’il vous convient le mieux