Les structures de données sont un ensemble de valeurs de données, les relations entre elles et les fonctions ou opérations qui peuvent être appliquées aux données. Il existe maintenant de nombreuses structures de données disponibles. Mais aujourd'hui, nous nous concentrerons sur les structures de données en pile. Je vais aborder les sujets suivants:
- Pourquoi des structures de données?
- Types de structures de données
- Qu'est-ce que la structure de données de pile?
- Création d'une structure de données de pile
- Pousser les éléments dans la pile
- Éléments pop de la pile
- Applications de la structure de données de pile
Pourquoi des structures de données?
Pour y répondre, vous devrez réfléchir à un grand niveau. Pensez à la façon dont Google Maps vous montre le meilleur itinéraire en seulement une fraction de secondes, à la façon dont il renvoie le résultat de votre recherche en microsecondes. Il ne traite pas que 100 sites Web, il traite plus d'un milliard de sites et vous montre toujours des résultats si rapidement.
Eh bien, bien que l'algorithme utilisé joue un rôle crucial, la structure de données ou le conteneur utilisé est le fondement de cet algorithme. Dans toute application, organiser et stocker les données d'une manière ou dans une structure qui convient le mieux à leur utilisation est la clé d'un accès et d'un traitement efficaces des données.
shallow vs deep copy java
Types de structures de données
Certaines structures de données standard peuvent être utilisées pour travailler efficacement avec les données. Nous pouvons même les personnaliser ou en créer de nouveaux en fonction de notre application.
Qu'est-ce que la structure de données de pile?
Prenons quelques exemples réels:
- Expédition en fret
- Assiettes sur un plateau
- Pile de pièces
- Pile de tiroirs
- Manœuvre de trains dans une gare de triage
Tous ces exemples suivent un Dernier entré, premier sorti stratégie. Considérez les assiettes sur un plateau, lorsque vous voulez choisir une assiette, vous êtes obligé de choisir une assiette par le haut, alors que lorsque les assiettes étaient conservées sur le plateau, elles doivent être dans l'ordre inverse. Ci-dessus des exemples qui suivent le Dernier entré, premier sorti (LIFO) principe sont connus comme Empiler .
Hormis les opérations complémentaires, je peux dire que les principales opérations possibles sur la pile sont:
- Poussez ou insérez un élément vers le haut de la pile
- Pop ou supprimer un élément du haut de la pile
Création d'une structure de données de pile
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- taille max est le nombre maximum d'éléments attendus dans la pile.
- Les éléments de la pile sont stockés dans la liste python.
- Top indique l'index le plus haut de la pile qui est initialement pris -1 pour marquer la pile vide.
Le statut initial de la pile peut être vu dans la figure où max_size = 5
Poussez l'élément dans la pile
Maintenant, si vous voulez entrer ou pousser un élément dans la pile, vous devez vous rappeler que
- Le haut pointera l'index vers lequel l'élément sera inséré.
- Et qu'aucun élément ne sera inséré lorsque la pile est pleine, c'est-à-dire lorsque max_size = top.
Alors, quel devrait être l'algorithme ??
# renvoie la taille maximale de la pile def get_max_size (self): return self .__ max_size # renvoie la valeur booléenne que la pile soit pleine ou non, True si pleine et False sinon def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes élément en haut de la pile def push (self, data): if (self.is_full ()): print ('stack is already full') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #Vous pouvez utiliser le __str __ () ci-dessous pour imprimer les éléments de l'objet DS lors du débogage def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg = 'Stack data (Top to Bottom):' + msg return msgMaintenant, lorsque vous exécutez ce qui suit:
stack1 = pile (4)
#Pousser tous les éléments requis.
stack1.push («A»)
stack1.push («B»)
stack1.push («C»)
stack1.push («E»)
impression (stack1.is_full ())
impression (pile1)
la méthode system.exit mettra fin à l'application.
Production:
la pile est déjà pleine
Vrai
Données de la pile (de haut en bas): D C B A
Éléments pop de la pile
Maintenant, comme vous avez inséré les éléments dans la pile, vous voulez les faire apparaître, vous devez donc prendre soin de ce qui suit:
- La pile n'est pas vide, c'est-à-dire en haut! = -1
- Lorsque vous supprimez les données, le haut doit pointer vers le haut précédent de la pile.
Alors, quel sera l'algorithme ??
#returns bool value si la pile est vide ou non, True si vide et False sinon def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('rien à pop, déjà vide') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 return a # afficher tous les éléments de la pile de haut en bas def display (self): pour i dans la plage (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()Maintenant, compte tenu de la pile créée précédemment, essayez de faire apparaître des éléments
impression (stack1.pop ())
impression (stack1.pop ())
impression (pile1)
impression (stack1.pop ())
impression (stack1.pop ())
impression (stack1.pop ())
Production:
ré
C
Données de la pile (de haut en bas): B A
B
À
rien à éclater, déjà vide
Applications de la structure de données de pile
- Exemple 1:
Une pile est utilisée pour implémenter un algorithme de correspondance entre crochets pour l'évaluation des expressions arithmétiques et également pour l'implémentation d'appels de méthode.
Réponse à laquelle est 5.
- Exemple 2:
Presse-papiers sous Windows utilise deux piles pour implémenter les opérations undo-redo (ctrl + z, ctrl + y). Vous auriez travaillé sur des éditeurs de mots Windows tels que MS-Word, Notepad, etc. Voici un texte écrit en MS-Word. Observez comment le texte a changé en cliquant sur Ctrl-Z et Ctrl-Y.
convertir le binaire en entier java
Voici un code qui simule une opération d'annulation-refaire. Parcourez le code et observez comment la pile est utilisée dans cette implémentation.
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('La pile est pleine !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('La pile est vide! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' La pile est vide ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Vous pouvez utiliser le __str __ () ci-dessous pour imprimer les éléments du Objet DS lors du débogage def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Empiler les données (de haut en bas): '+ msg return ms g #fonction pour implémenter une opération de suppression ou de retour arrière def remove (): global clipboard, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) #fonction pour implémenter l'opération d'annulation def undo (): global clipboard, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Il n'y a pas de données à annuler') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) #fonction pour implémenter l'opération de refaire def redo (): presse-papiers global, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Il n'y a pas de données à refaire ') else: data = redo_stack.pop () if (données non dans le presse-papiers): print (' Il n'y a pas de données à refaire ') redo_stack.push (données) else: clipboard.remove (données) undo_stack.push ( data) print ('Redo:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (presse-papiers)) remove () undo () redo ()Production:
Supprimer: [«A», «B», «C», «D», «E»]
Annuler: [«A», «B», «C», «D», «E», «F»]
Rétablir: [«A», «B», «C», «D», «E»]
Avec cela, nous arrivons à la fin de cet article Stack Data Structure in Python. Si vous avez réussi à comprendre et à exécuter les codes par vous-même, vous n'êtes plus un débutant dans Stacks Data Structure.
Vous avez une question pour nous? Veuillez le mentionner dans la section commentaires de cet article et nous vous répondrons dans les plus brefs délais.
Pour obtenir des connaissances approfondies sur Python ainsi que sur ses différentes applications, vous pouvez vous inscrire en direct avec assistance 24/7 et accès à vie.