NSI Terminale
L'idée : utiliser un attribut servant de "pointeur" désignant l'indice de l'élément du tableau constituant le sommet de la pile.
Cet attribut sera initialisé à 0 pour indiquer une pile vide, et incrémenté ( reps. décrémenté ) APRÈS chaque empilage ( resp. dépilage ).
On peut aussi faire le choix de l'initialiser à -1 pour une pile vide, et faire l'incrémentation/décrémentation AVANT chaque empilage/dépilage.
class PileStat:
def __init__(self,n):
self.taille = n
self.sommet = 0 # indice du sommet dans le tableau ( indique en fait l'indice "une position au dessus du sommet" )
self.pile = [None]*self.taille # si self.sommet == self.taille, c'est donc que la pile est pleine.
def est_vide(self):
return self.sommet == 0
def empiler(self, elt):
assert self.sommet < self.taille, "Stack overflow ( la pile est pleine )"
self.pile[self.sommet] = elt # on place l'élément au sommet
self.sommet += 1 # on incrémente le pointeur de sommet
def depiler(self):
assert not self.est_vide(), "Stack underflow ( la pile est vide )"
s = self.pile[self.sommet-1] # s contient l'élément au sommet de la pile
self.pile[self.sommet-1] = None # on "efface" l'élément au sommet
self.sommet -= 1 # on décrémente le pointeur de sommet
return s # on renvoie l'élément à l'ancien sommet
On retrouve bien ici les concepts de la POO : ce qui représente la pile elle-même est l'objet self; le tableau Python utilisé n'est qu'un attribut de cet objet, le reste de la classe étant
ses méthodes.
Tests à réaliser :
pile = PileStat(10)
pile.empiler(12)
pile.empiler(25)
pile.empiler(36)
print(pile.depiler())
for i in range(11): # pour i = 10, la pile devrait déborder
pile.empiler(i)
while not pile.est_vide():
print(pile.depiler())
Trop facile 😊 :
class PileDyna:
def __init__(self):
self.pile = []
def est_vide(self):
return len(self.pile) == 0 # ou self.pile == []
def empiler(self, elt):
self.pile.append(elt)
def depiler(self):
assert not self.est_vide(), "Stack underflow ( la pile est vide )"
return self.pile.pop()
La méthode Python pop renvoie l'élément supprimé en fin de tableau, on peut donc l'utiliser directement après le return.
1. Tableau de taille fixe :
2. Tableau dynamique ( type list Python ) :
append et pop en O(1), mais c'est du "pseudo" O(1) ( cf. chapitre sur les listes ).3. Autre implémentation judicieuse :
Une implémentation par liste chaînée, avec le sommet de la pile en tête de liste, permet d’avoir des opérations de dépilage et d'empilage en "vrai" O(1).
Il s'agit du code de la pile dynamique, mais en utilisant un objet de type Liste pour implémenter la pile, et en remplaçant les méthodes append et pop
respectivement par les méthodes insert_first et pop_first de la liste chaînée :
from liste_chainee import Liste
class PileOptim:
def __init__(self):
self.pile = Liste()
def est_vide(self):
return self.pile.is_empty()
def empiler(self, elt):
self.pile.insert_first(elt)
def depiler(self):
assert not self.est_vide(), "Stack underflow ( la pile est vide )"
return self.pile.pop_first()
Le code complet des 3 classes est dans le fichier pile.py.
Dans tous les exercices utilisant une pile ( quelque soit sa version ), il faudra alors importer au début du script le fichier contenant les deux classes précédentes :
from pile import *
Oui, il faudra une deuxième pile : en "vidant" complètement la première dans la deuxième, et en renvoyant cette deuxième, on a bien renversé la première...
Pour ne pas modifier la pile d'origine, il en faudra également une troisième pour stocker temporairement les éléments dépilés de la première pile, de façon en fin de fonction à pouvoir y ré-empiler ses éléments :
from pile import *
def inversion_pile(pile):
p_inv = Pile() # pile inversée
p_temp = Pile() # pile temporaire
while not pile.est_vide():# tant que la pile d'origine n'est pas vide,
elt = pile.depiler() # on dépile son sommet,
p_inv.empiler(elt) # et on stocke ce sommet dans p_inv
p_temp.empiler(elt) # et dans p_temp.
while not p_temp.est_vide():
pile.empiler(p_temp.depiler()) # on ré-empile tous ses éléments sauvegardés dans la pile d'origine
return p_inv # et on ne renvoie que la pile inversée !
L'idée :
from pile import *
def inversion_chaine(ch: str)->str :
pile = Pile() # création de la pile
for car in ch: # empilage des caractères de la chaîne
pile.empiler(car)
c2 = '' # nouvelle chaîne
while not pile.est_vide(): # tant que la pile n'est pas vide,
c2 = c2 + pile.depiler()# on dépile chaque caractère et on le concatène à la nouvelle chaîne.
return c2
Remarque :
Vous avez déjà fait cet exercice avec une fonction récursive, et on avait alors parlé à ce moment de "pile d'exécution".
L'exécution des fonctions récursives fait effectivement appel à la structure de données PILE que vous venez d'étudier, pour stocker les résultats intermédiaires et les résultats à renvoyer.
Vous pourriez d'ailleurs refaire tous les exercices du chapitre Récursivité, mais en écrivant un code itératif utilisant une pile !
Vous connaissez bien entendu l'algorithme de recherche d'un maximum/d'un minimum dans un tableau : il faut parcourir le tableau, et comparer chacun de ses éléments au maximum/au minimum "courant" stocké dans une variables.
Ici, le TAD PILE ne permet pas un parcours de la structure, il faut donc s'arranger avec le fait que l'on n'a accès qu'à son sommet...
L'idée :
from pile import *
def maximum_pile(pile)->int:
p_temp = Pile()
maximum = pile.depiler() # maximum initialisé au premier élément de la pile
p_temp.empiler(maximum) # à empiler tout de suite dans la pile temporaire de sauvegarde
while not pile.est_vide():
elt = pile.depiler()
if elt > maximum:
maximum = elt
p_temp.empiler(elt)
while not p_temp.est_vide():
pile.empiler(p_temp.depiler())
return maximum
def minimum_pile(pile)->int:
p_temp = Pile()
minimum = pile.depiler()
p_temp.empiler(minimum)
while not pile.est_vide():
elt = pile.depiler()
if elt < minimum:
minimum = elt
p_temp.empiler(elt)
while not p_temp.est_vide():
pile.empiler(p_temp.depiler())
return minimum
Il faut ici deux piles supplémentaires :
from pile import *
def copie_pile(pile):
p_temp = Pile()
p_copie = Pile()
while not pile.est_vide():
p_temp.empiler(pile.depiler())
while not p_temp.est_vide():
elt = p_temp.depiler()
pile.empiler(elt)
p_copie.empiler(elt)
return p_copie
Attention, écrire simplement : p_copie = pile ne réalise par une copie de l'objet pile dans un nouvel obkjt p_copie; les variables désignent en fait
le même objet en mémoire, on ne fait donc pas du tout de copie ( idem à cours sur la copie de tableaux en Première ).
from pile import *
def sum_stack(n):
s = Pile()
while n != 0:
s.empiler(n)
n -= 1
print(s)
while not s.est_vide():
try:
resultat = s.depiler() + s.depiler()
s.empiler(resultat)
print(s)
except:
pass
return resultat
print(somme(10)) # renvoie 55
On change l'opération effectuée lors du dépilage des données :
from pile import *
def fact(n):
s = Pile()
while n != 0:
s.empiler(n)
n -= 1
print(s)
while not s.est_vide():
try:
resultat = s.depiler() * s.depiler()
s.empiler(resultat)
print(s)
except:
pass
return resultat
print(fact(10)) # renvoie 3628800
from pile import *
def somme(L):
s = Pile
n = 0
while n != len(L):
s.empiler(L[n])
n += 1
print(s)
while not s.est_vide():
try:
resultat = s.depiler() + s.depiler()
s.empiler(resultat)
print(s)
except:
pass
return resultat
On peut remarquer qu'en utilisant une pile, on s'affranchit des limites de niveaux de récursion imposées par Python ( 1000 appels récursifs au maximum par défaut ! ).
Essayez de calculer fact(1000) avec l'algorithme récursif... avec une pile, c'est possible !!
from pile import *
def check_parenth(exp: str)->bool:
pile = Pile()
ouvrants ='{(['
fermants = '})]'
for car in exp :
if car in ouvrants:
pile.empiler(car)
if car in fermants:
if not pile.est_vide() :
f = pile.depiler()
if ouvrants.index(f) != fermants.index(car): # la méthode 'index' permet de trouver l'indice d'un élément donné dans un tableau
return False
else:
return False
return pile.est_vide()
False et l'analyse s'arrête ( ligne 14 ). False.True ( lignes 20 ); si ce n'est pas
le cas, cela signifie qu'il y avait plus d'ouvrants que de fermants, on renvoie donc False.