UN empiler est une structure de données linéaire qui stocke les éléments dans un Dernier entré/premier sorti (LIFO) ou de manière premier entré/dernier sorti (FILO). Dans la pile, un nouvel élément est ajouté à une extrémité et un élément est supprimé à cette extrémité uniquement. Les opérations d'insertion et de suppression sont souvent appelées push et pop.

Les fonctions associées à la pile sont :

• vide() – Indique si la pile est vide – Complexité temporelle : O(1)
• taille() – Renvoie la taille de la pile – Complexité temporelle : O(1)
• haut() / coup d'oeil() – Renvoie une référence à l'élément le plus haut de la pile – Complexité temporelle : O(1)
• pousser(a) – Insère l'élément 'a' en haut de la pile – Complexité temporelle : O(1)
• populaire() – Supprime l'élément le plus haut de la pile – Complexité temporelle : O(1)

Mise en œuvre:

Il existe différentes manières d'implémenter une pile en Python. Cet article couvre l'implémentation d'une pile utilisant des structures de données et des modules de la bibliothèque Python.
Stack en Python peut être implémenté des manières suivantes :

• liste
• Collections.deque
• file d'attente.LifoQueue

Implémentation à l'aide de liste :

La liste de structures de données intégrée de Python peut être utilisée comme pile. Au lieu de push(), append() est utilisé pour ajouter des éléments en haut de la pile tandis que pop() supprime l'élément dans l'ordre LIFO.
Malheureusement, la liste présente quelques lacunes. Le plus gros problème est qu’il peut rencontrer des problèmes de vitesse à mesure qu’il grandit. Les éléments de la liste sont stockés les uns à côté des autres en mémoire, si la pile devient plus grande que le bloc de mémoire qui la contient actuellement, alors Python doit effectuer certaines allocations de mémoire. Cela peut conduire à ce que certains appels append() prennent beaucoup plus de temps que d'autres.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implémentation à l'aide de collections.deque :

La pile Python peut être implémentée à l'aide de la classe deque du module collections. Deque est préféré à la liste dans les cas où nous avons besoin d'opérations d'ajout et de pop plus rapides depuis les deux extrémités du conteneur, car deque fournit une complexité temporelle O(1) pour les opérations d'ajout et de pop par rapport à la liste qui fournit O(n) complexité temporelle.

Les mêmes méthodes sur deque que celles vues dans la liste sont utilisées, append() et pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implémentation à l'aide du module de file d'attente

Le module Queue dispose également d'une file d'attente LIFO, qui est essentiellement une pile. Les données sont insérées dans la file d'attente à l'aide de la fonction put() et get() extrait les données de la file d'attente.

Différentes fonctions sont disponibles dans ce module :

• taille max – Nombre d'éléments autorisés dans la file d'attente.
• vide() – Renvoie True si la file d'attente est vide, False sinon.
• complet() – Renvoie True s’il y en a taille max éléments dans la file d'attente. Si la file d'attente a été initialisée avec maxsize=0 (valeur par défaut), alors full() ne renvoie jamais True.
• obtenir() – Supprimer et renvoyer un élément de la file d'attente. Si la file d'attente est vide, attendez qu'un élément soit disponible.
• get_nowait() – Renvoyez un élément s’il est immédiatement disponible, sinon augmentez QueueEmpty.
• mettre (article) – Mettez un élément dans la file d’attente. Si la file d'attente est pleine, attendez qu'un emplacement libre soit disponible avant d'ajouter l'élément.
• put_nowait (élément) – Mettez un élément dans la file d’attente sans le bloquer. Si aucun emplacement libre n’est immédiatement disponible, augmentez QueueFull.
• qsize() – Renvoie le nombre d'éléments dans la file d'attente.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implémentation à l'aide d'une liste à chaînage unique :

La liste chaînée comporte deux méthodes addHead(item) et removeHead() qui s'exécutent en temps constant. Ces deux méthodes conviennent pour implémenter une pile.

• getSize() – Obtenez le nombre d’éléments dans la pile.
• est vide() – Renvoie True si la pile est vide, False sinon.
• coup d'oeil() – Renvoie l’élément le plus haut de la pile. Si la pile est vide, déclenchez une exception.
• pousser (valeur) – Poussez une valeur en tête de la pile.
• populaire() – Supprime et renvoie une valeur en tête de pile. Si la pile est vide, déclenchez une exception.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Récupère la taille actuelle de la pile def getSize(self): return self.size # Vérifiez si la pile est vide def isEmpty(self): return self.size = = 0 # Récupère l'élément supérieur de la pile def peek(self): # Vérification sanitaire pour voir si nous # regardons une pile vide. if self.isEmpty() : return None return self.head.next.value # Pousser une valeur dans la pile. def push(self, value): node = Node(value) node.next = self.head.next # Faites pointer le nouveau nœud vers la tête actuelle self.head.next = node #!!! # Mettez à jour le head pour qu'il soit le nouveau nœud self.size += 1 # Supprimez une valeur de la pile et retournez. def pop(self) : if self.isEmpty() : raise Exception('Popping from an vide stack') remove = self.head.next self.head.next = remove.next #!!! modifié self.size -= 1 return remove.value # Code du pilote si __name__ == '__main__' : stack = Stack() pour i dans la plage (1, 11) : stack.push(i) print(f' Pile : {stack}') pour _ dans la plage (1, 6) : top_value = stack.pop() print(f'Pop : {top_value}') # nom de la variable modifié print(f'Stack : { pile}')>

Sortir

Stack: 10->9->8->7->6->5->4->3->2->1 Pop : 10 Pop : 9 Pop : 8 Pop : 7 Pop : 6 Pile : 5->4->3->2->1>

Avantages de Stack :

• Les piles sont des structures de données simples avec un ensemble d'opérations bien défini, ce qui les rend faciles à comprendre et à utiliser.
• Les piles sont efficaces pour ajouter et supprimer des éléments, car ces opérations ont une complexité temporelle de O(1).
• Afin d'inverser l'ordre des éléments, nous utilisons la structure de données de pile.
• Les piles peuvent être utilisées pour implémenter des fonctions d'annulation/rétablissement dans les applications.

Inconvénients de Stack :

• La restriction de taille dans Stack est un inconvénient et s'ils sont pleins, vous ne pouvez plus ajouter d'éléments à la pile.
• Les piles ne fournissent pas d'accès rapide aux éléments autres que l'élément supérieur.
• Les piles ne prennent pas en charge une recherche efficace, car vous devez afficher les éléments un par un jusqu'à ce que vous trouviez l'élément que vous recherchez.