6.1 Définition d'une pile et ses propriétés
Une pile est une structure de données abstraite, représentant une collection d'éléments organisée selon le principe "dernier arrivé, premier sorti" (Last In, First Out, LIFO). Une pile peut être imaginée comme une pile de livres : le dernier livre ajouté est au sommet de la pile et sera retiré/pris en premier.
Propriétés de la pile :
- LIFO (Last In, First Out) : Le dernier élément ajouté est extrait en premier.
- Opérations limitées : La pile ne supporte que l'ajout (push), la suppression (pop) et la visualisation (peek) de l'élément au sommet.
- Accès unidirectionnel : L'accès aux éléments n'est possible que depuis le sommet de la pile.
- Simplicité de mise en œuvre : Une pile peut être facilement implémentée à l'aide d'un tableau ou d'une liste chaînée.
- Gestion de la mémoire : Les données temporaires ou les états peuvent être stockés et extraits dans l'ordre inverse de leur ajout.
Principe de fonctionnement LIFO :
- Ajout d'un élément (push) : Un nouvel élément est ajouté au sommet de la pile.
- Suppression d'un élément (pop) : Le dernier élément ajouté est supprimé du sommet de la pile.
- Visualisation du sommet (peek) : Permet de voir l'élément au sommet de la pile sans le supprimer.
Les éléments de la pile sont ajoutés et supprimés d'un seul côté, appelé le sommet (top). Ainsi, le dernier élément ajouté est toujours au sommet et sera retiré en premier.
6.2 Opérations principales
Opérations principales : push, pop, peek
Opération push : Ajoute un nouvel élément au sommet de la pile.
Complexité temporelle : O(1).
Exemple d'émulation d'une pile en Python avec une liste :
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Affiche : [10, 20]
Opération pop : Supprime et retourne l'élément au sommet de la pile.
Complexité temporelle : O(1).
Exemple d'émulation d'une pile en Python avec une liste :
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Affiche : 20
print(stack) # Affiche : [10]
Opération peek : Retourne l'élément au sommet de la pile sans le supprimer.
Complexité temporelle : O(1).
Exemple de réalisation :
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Affiche : 10
6.3 Exemples d'utilisation de la pile
Voici quelques exemples d'utilisation de la pile :
Gestion des appels de fonctions
En Python, la pile est utilisée pour suivre les fonctions pendant l'exécution du programme. Chaque fois qu'une fonction est appelée, son adresse de retour et ses variables locales sont placées sur la pile. Une fois que la fonction termine son exécution, le contrôle retourne à la fonction qui l'a appelée et les données sont extraites de la pile.
Exemple d'utilisation de la pile d'appels :
Dans cet exemple, les appels récursifs à la fonction factorial utilisent la pile d'appels pour stocker l'état de chaque appel jusqu'à ce que la condition de base (n == 1) soit atteinte.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Affiche : 120
Annulation d'opérations (Undo)
La pile est utilisée pour implémenter la fonction d'annulation d'actions dans les éditeurs de texte et autres applications. Lorsqu'un utilisateur effectue une action, elle est sauvegardée sur la pile. Lors de l'exécution de l'opération Undo, la dernière action est extraite de la pile et annulée.
Exemple d'utilisation d'une pile pour annuler des opérations :
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Exemple d'utilisation :
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Affiche : "Hello World"
editor.undo()
print(editor.text) # Affiche : "Hello"
editor.undo()
print(editor.text) # Affiche : ""
GO TO FULL VERSION