• Assurez la sécurité des applications de la bonne manière! Détectez, protégez, surveillez, accélérez et plus encore…
  • Les structures de données jouent un rôle clé dans le monde de la programmation. Ils nous aident à organiser nos données d'une manière qui peut être utilisée efficacement. le empiler 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 à la pile de livres, de chaises, etc., dans la vraie vie. Et il suit le Dernier entré / premier sorti (LIFO) principe. C'est la structure de données la plus simple. Voyons le scénario avec un exemple réel.

    Disons que nous avons une pile de livres comme suit.

    Pile de livres

    Lorsque nous voulons le troisième livre du haut, nous devons retirer les deux premiers livres du haut pour sortir le troisième livre. Ici, le livre le plus haut va en dernier à la pile et vient en premier de la pile. La structure des données empiler suit le même principe Dernier entré / premier sorti (LIFO) en programmation.

    Opérations en 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 de pousser et pop opérations.

    Nous écrirons 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()

    Renvoie si la pile est vide ou non.

    Assez d'aspects conceptuels de la empiler Structure de données. Passons à l'implémentation sans plus tarder.

    Je suppose que tu as python installé sur votre PC sinon vous pouvez également essayer le compilateur en ligne.

    Implémentation de la pile

    La mise en œuvre 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 dans Python.

    Voyons-les tous un par un.

    #1. liste

    Nous allons mettre en œuvre le empiler utilisant l' liste dans une classe. Voyons l'implémentation étape par étape de la pile.

    Step1: Écrivez une classe appelée Stack.

    class Stack:
    	pass

    Step2: Nous devons conserver les données dans une liste. Ajoutons une liste vide dans la classe Stack avec un nom éléments.

    class Stack:
    	def __init__(self):
    		self.elements = []

    Step3: À pousser les éléments dans la pile, nous avons besoin d'une méthode. Écrivons un pousser méthode qui prend des données comme argument et ajouter à la éléments liste.

    class Stack:
    	def __init__(self):
    		self.elements = []
    
    	def push(self, data):
    		self.elements.append(data)
    		return data

    Step4: De même, écrivons le pop méthode qui fait sortir l'élément le plus haut de la empiler. Nous pouvons utiliser le pop méthode de liste type de données.

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

    Nous avons terminé la mise en œuvre de la pile avec les opérations requises. Maintenant, ajoutons les fonctions d'assistance pour obtenir plus d'informations sur la pile.

    Step5: Nous pouvons obtenir l'élément le plus haut de la pile en utilisant l'index négatif. Le code element[-1] renvoie le dernier de la liste. C'est l'élément le plus élevé de la pile dans notre cas.

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

    Step6: Si la longueur du elements la liste 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 liste type de données.

    Oh! attendez, nous venons de le mettre en œuvre. Mais je n'ai pas vu comment l'utiliser. Comment l'utiliser alors?

    Venez voir comment le mettre en œuvre. Nous devons créer un objet pour le Stack classe pour l'utiliser. Ce n'est pas grave. Faisons-le d'abord.

    class Stack: 
        ## ...
    
    if __name__ == '__main__':
        stack = Stack()

    Nous avons créé l'objet stack 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 le est vide méthode. Il devrait revenir Vrai.
    • Poussez les nombres 1, 2, 3, 4, 5 dans la pile en utilisant la poussée méthode.
    • La est vide la méthode doit retourner Faux. Vérifie ça.
    • Imprimez l'élément le plus haut à l'aide du coup d'oeil méthode.
    • Pop l'élément de la pile en utilisant le pop méthode.
    • Vérifiez l'élément peek. Il devrait renvoyer l'élément 4.
    • Maintenant, sortez tous les éléments de la pile.
    • La est vide la méthode doit retourner Vrai. 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 liste Type de données. 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 liste type de données en tant que empiler. L'implémentation de stack 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 collections module intégré qui peut agir comme une pile.

    # 2. deque des collections

    Il est implémenté comme une file d'attente à deux extrémités. Puisqu'il prend en charge l'ajout et la suppression d'éléments des deux extrémités. Par conséquent, nous pouvons l'utiliser comme un empiler. Nous pouvons le faire suivre LIFO principe de la pile.

    Il est implémenté à l'aide d'autres structures de données appelées doublement lié liste. 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 a pris O (n) temps. Nous pouvons l'utiliser comme un empiler car il n'est pas nécessaire d'accéder aux éléments du milieu depuis la pile.

    Avant d'implémenter la pile, voyons les méthodes utilisées pour implémenter la pile à l'aide du file.

    • ajouter (données) - utilisé pour pousser les données vers la pile
    • pop() - utilisé pour retirer l'élément le plus haut de la pile

    Il n'y a pas de méthode alternative pour coup d'oeil et est vide. Nous pouvons imprimer la pile entière à la place de coup d'oeil méthode. Ensuite, nous pouvons utiliser le len méthode pour vérifier si le empiler est vide ou non.

    Implémentons la pile en utilisant deque du collections module.

    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 à mettre en œuvre empiler utilisant l' deque du collections module intégré. 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 didacticiel.

    # 3. LifoQueue

    Le nom du blog LifoQueue lui-même dit qu'il suit le LIFO principe. Par conséquent, nous pouvons l'utiliser comme un empiler sans aucun doute. C'est du module intégré file. le LifoQueue fournit des méthodes pratiques qui sont utiles dans l'implémentation de la pile. Voyons les

    • mettre (données) - 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() - retourne si la pile est vide ou non
    • qsize () - renvoie la longueur de la file d'attente

    Implémentons la pile en utilisant LifoQueue du file module.

    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 une connaissance suffisante des 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, accolades, accolades sont correctement équilibrées ou non.

    Voyons quelques exemples.

    Contribution: "[{}] ([])"

    Sortie : Équilibré

    Contribution: "{[}] ([])"

    Sortie : Pas équilibré

    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 personnages.
    • Si la longueur de l'expression est impaire, alors l'expression est Pas équilibré
    • Itérer à travers l'expression donnée.
      • Si le caractère courant est le crochet ouvrant de ( ou ou [, puis poussez-le pour l'empiler.
      • Sinon si le caractère courant est un crochet fermant ) ou ou ], puis sortez de la pile.
      • Si le caractère sauté 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é sinon l'équation est ne pas Équilibré.

    Nous pouvons utiliser le type de données défini pour la vérification de la correspondance entre crochets.

    ## 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 le empiler pour résoudre beaucoup plus de problèmes. Le problème ci-dessus est l'un d'entre eux. Essayez d'appliquer le concept de pile là où vous pensez qu'il vous convient le mieux.

    Conclusion

    Yah! Vous avez terminé le didacticiel. J'espère que vous avez autant apprécié le tutoriel que moi en le réalisant. Voilà pour le tutoriel.

    Codage heureux 🙂 👨‍💻