Structures linéaires : Piles
Cours
En informatique, une pile (en anglais stack) est un type abstrait de données sur le principe « dernier arrivé, premier sorti » (ou LIFO pour Last In, First Out).
Le dernier élément ajouté à la pile, ou empilé, est le premier qui sera sorti, ou dépilé.
Le dernier élément empilé est le sommet de la pile.
Le fonctionnement est donc celui d'une pile d'assiettes : on ajoute des assiettes sur la pile, et on les récupère dans l'ordre inverse, en commençant par la dernière ajoutée.
Les piles trouvent de nombreuses applications en informatique, par exemple :
-
Dans un navigateur web, une pile sert à mémoriser les pages Web visitées. L'adresse de chaque nouvelle page visitée est empilée et l'utilisateur dépile l'adresse de la page précédente en cliquant le bouton « Afficher la page précédente ».
-
La fonction « Annuler la frappe » (en anglais « Undo ») d'un traitement de texte mémorise les modifications apportées au texte dans une pile.
Interface
Les principales primitives constituant l'interface d'une pile sont :
creer() → pile
: construire une pile vide.est_vide() → bool
: vérifier si une pile est vide ou non.empiler(element)
: ajouter un élément sur la pile (Push en anglais).dépiler() → element
: enlèver un élément de la pile et le renvoyer (Pop en anglais).taille() → int
: renvoyer le nombre d'éléments dans la pile (la hauteur).
Exemple :
Soit une pile P
composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le sommet de la pile est 22). Pour chaque exemple ci-dessous on repart de la pile d'origine :
- dépiler(P)
renvoie 22 et la pile P
est maintenant composée des éléments suivants : 12, 14, 8, 7 et 19 (le sommet de P
est 19).
- empiler(P, 42)
la pile P
est maintenant composée des éléments suivants : 12, 14, 8, 7, 19, 22 et 42
- si on applique dépiler(P)
6 fois de suite, est_vide(P)
renvoie vrai.
- après avoir appliqué dépiler(P)
une fois, taille(P)
renvoie 5.
Implémentation
La pile est un type abstrait, son implémentation peut se faire sous différentes formes, par exemple avec une liste chaînée ou un tableau dynamique de type list
Python.
Avec une liste chaînée
Sur la même idée que la classe ListeChainee
vue précédemment, il est possible de peut créer une classe Pile
de toute pièce basée sur la class Cellule
.
class Cellule:
'''Cellule de Pile '''
def __init__(self, v, d=None):
self.valeur = v # Valeur de la Cellule
self.dessous = d # Cellule de dessous
class Pile:
'''Pile sous forme d'une liste chainee de cellules'''
def __init__(self):
self.sommet = None
self._hauteur = 0 # Nombre d'élément de la Pile
def est_vide(self):
return self.sommet == None
def empiler(self, v):
self.sommet = Cellule(v, self.sommet)
self._hauteur += 1
def depiler(self):
if self.est_vide(): raise IndexError("la pile est vide")
v = self.sommet.valeur
self.sommet = self.sommet.dessous
self._hauteur -= 1
return v
def taille(self):
return self._hauteur
Créons maintenant une instance de Pile
:
>>> p = Pile()
>>> p.taille()
0
>>> p.empiler('a')
>>> p.empiler('b')
>>> p.empiler('c')
>>> p.depiler()
'c'
>>> p.taille()
2
Avec le type list
de Python
Il est aussi possible de créer très facilement une classe Pile
en utilisant le type list
avec les méthodes pop()
et append()
:
class Pile:
''' structure de Pile en utilisant le type list'''
def __init__(self):
self.pile = []
def est_vide(self):
return len(self.pile) == 0
def empiler(self, v):
self.pile.append(v)
def depiler(self):
if self.est_vide(): raise IndexError("la pile est vide")
return self.pile.pop()
def taille(self):
return len(self.pile)
def __str__(self):
ch = ''
for v in self.pile:
ch = ch + "|\t" + str(v) + "\t|\n" # Affiche les élements de la pile : | v |
ch = ch + "---------"
return ch
Créons maintenant une instance de Pile
:
>>> p = Pile()
>>> p.est_vide()
True
>>> p.depiler()
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
File "<module1>", line 15, in depiler
IndexError: la pile est vide
>>> p.empiler('a')
>>> p.empiler('b')
>>> p.empiler('c')
>>> p.est_vide()
False
>>> p.depiler()
'c''
>>>
Enregistons cette classe de Pile
dans un fichier "pile.py", elle nous sera utile par la suite.
Pour faire encore plus simple, programmons une pile avec la même idée, mais sans utiliser la POO :
def creer():
return []
def est_vide(p):
return len(p) == 0
def empiler(p, v):
p.append(v) # Inutile de renvoyer p, le type list est muable
def depiler(p):
if est_vide(p): raise IndexError("la pile est vide")
return p.pop()
def taille(p):
return len(p)
def afficher(p):
for v in p:
print("|\t", v, "\t|\n") # Affiche les élements de la pile : | v |
print("---------")
>>> p = creer()
>>> est_vide(p)
True
>>> depiler(p)
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
File "<module1>", line 11, in depiler
IndexError: la pile est vide
>>> empiler(p, 'a')
>>> empiler(p, 'b')
>>> empiler(p, 'c')
>>> depiler(p)
'c'
>>> taille(p)
2
Finalement en Python, une simple variable de type list
avec la fonction len()
et les méthodes .append()
et .pop()
est une façon rapide et simple de créer une pile avec toutes ses primitives :