Tutoriel sur la structure des données de la pile Python
Implémentez une pile LIFO en Python. Exécutez notre exemple de code de pile interactive pour maîtriser les limites de push, pop, peek et de capacité.
Aperçu
Une pile est une structure de données linéaire qui suit le principe Last-In, First-Out (LIFO). Cela signifie que le dernier élément ajouté à la pile est le tout premier à être supprimé, à l’instar d’une pile de plaques.
La pile prend en charge deux opérations principales : push (ajoute un élément en haut) et pop (supprime l'élément le plus récemment ajouté). De plus, une opération de coup d'oeil ou de dessus permet d'inspecter l'élément supérieur sans le retirer.
En Python, les piles peuvent être facilement construites en utilisant une liste avec les méthodes `.append()` et `.pop()`, ou en utilisant l'objet `collections.deque` qui offre des opérations de file d'attente doubles optimisées en temps O(1).
Sortie de code et d'exécution
Une implémentation de Stack personnalisée utilisant la structure de liste de Python pour émuler les fonctions push, pop et peek.
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
print(f"Pushed: {item}")
def pop(self):
if self.is_empty():
return "Underflow: Stack is empty"
popped = self.items.pop()
print(f"Popped: {popped}")
return popped
def peek(self):
if self.is_empty():
return "Stack is empty"
return self.items[-1]
def size(self):
return len(self.items)
# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")
print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")
stack.pop()
print(f"Stack after Pop: {stack.items}")Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']Mise en œuvre étape par étape
- Gestion des fonctions d'annulation dans les systèmes logiciels
- Analyse syntaxique et vérification des parenthèses dans les compilateurs
- Suivi des piles d'appels d'exécution pendant la récursion dans les moteurs
Foire aux questions
Pourquoi collections.deque est-il préféré à une liste normale pour Stacks ?
Bien que les listes soient pratiques, ce sont des tableaux dynamiques sous le capot. Lors du redimensionnement, la réallocation de la mémoire peut prendre un temps O(n). L'objet deque utilise une architecture de liste doublement chaînée, garantissant des push et des pops O(1).
Les piles peuvent-elles déborder en Python ?
Une classe de pile standard en Python utilisant des tableaux de listes grandira jusqu'à ce qu'elle consomme toute la mémoire système disponible. La pile de récursivité en Python a cependant une limite par défaut (généralement 1 000) pour empêcher des boucles infinies de faire planter l'interpréteur.
Sujets connexes
Maîtrisez les opérations de file d’attente FIFO en Python. Exécutez et exécutez notre exemple de file d'attente interactive présentant les méthodes de mise en file d'attente et de retrait de la file d'attente.
Implémentation de liste à chaînage unique PythonDécouvrez comment implémenter une liste à chaînage unique en Python. Explorez l'allocation dynamique de mémoire, les opérations de nœuds, l'insertion, le parcours et la suppression.