2025.08.17

NSI Cours Terminale : Pile

Ce cours a été écrit grâce à une collaboration entre Pierre Brun, professeur de mathématiques et moi, Jared Asuncion. Il s'agit d'un cours de spécialité NSI pour des terminales générales.

Elles ont été initialement rédigées sous forme de notebooks Jupyter, mais nous les avons converties en HTML pour une meilleure lisibilité dans les browsers.

C'est un travail en cours de réalisation. N'hésitez pas à nous contacter à l'adresse mail nsi arobase guissmo point com pour tout commentaires, questions ou suggestions.

Auparavant

  • On a appris comment définir des classes en Python en utilisant le mot-clé class.
  • On a appris ce que sont les attributs et les méthodes, ainsi que comment les définir et les utiliser.

Piles

Une structure de pile (penser à une pile d’assiette) est associée à la méthode Last In, First Out (LIFO; dernier arrivé, premier sorti).

Les éléments sont empilés les uns au-dessus des autres, et on ne peut toujours dépiler que l’élément du haut de la pile. Le dernier élément à être arrivé est donc le premier à être sorti.

from magie import VisualisationPile
# --- #
vp = VisualisationPile()
vp.empiler("lundi")
vp.empiler("mardi")
vp.empiler("mercredi")
vp.depiler()
vp.empiler("jeudi")
vp.empiler("vendredi")
vp.depiler()
# --- #
vp.visualiser()

Exemples de données stockées sous forme de pile

Dans un navigateur internet, la liste des pages parcourues est stockée sous forme de pile : la fonction « Page précédente » permet de « dépiler » peu à peu les pages précédemment parcourues.

Dernier arrivé, premier sorti ! La page web qui a été visitée le plus récemment est la première page qui est dépilée par la fonction « Page précédente ».

Lors de l’exécution d’une fonction récursive, le processeur empile successivement les appels à traiter : seule l’instruction du haut de la pile peut être traitée.

from magie import arbre_d_appels
@arbre_d_appels
def F(n):
    if n == 0 :
        return 0
    if n == 1 :
        return 1
    return F(n-1) + F(n-2)

Observation de la pile d’exécution

Appelons F(n) la fonction calculant de manière récursive le nn-ième terme de la suite. Observons en détail la pile d’exécution lors du calcul de F(4).

On s’aperçoit notamment que :

∙\bullet les appels récursifs ne sont PAS simultanés (rappelons que la simultanéité n’existe théoriquement pas en informatique). On pourrait s’imaginer que la relation F(4)=F(3)+F(2)F(4) = F(3) + F(2) allait déclencher deux «fils» récursifs calculant respectivement F(3)F(3) et F(2)F(2). Il n’en est rien, on va jusqu’au bout du calcul de F(3)F(3) avant de s’intéresser à F(2)F(2).

∙\bullet conséquence de la remarque précédente : le calcul de F(2)F(2) s’effectue 2 fois. Une amélioration future (appelée mémoïsation, voir le cours de programmation dynamique) sera de conserver cette valeur de F(2)F(2) afin d’améliorer les calculs.

On peut construire par exemple l’arbre d’appel de fibo(4) :

F(4)

Interface d’une Pile

L’objectif est de créer une classe Pile qui possède un unique attribut contenu. L’instruction Pile() créera une pile vide. Chaque objet Pile disposera des méthodes suivantes :

  • est_vide : indique si la pile est vide (renvoie un booléen)
  • empiler : insère un élément (passé en paramètre) en haut de la pile. Ne renvoie rien.
  • depiler : renvoie la valeur de l’élément en haut de la pile ET le supprime de la pile.

Ces 3 méthodes sont essentielles et se retrouveront systématiquement dans chaque interface. Nous y ajouterons, uniquement par commodité, la méthode suivante :

  • __str__ : permet d’afficher la pile sous forme agréable (par ex : |3|6|2|5|)

Implémentation avec une liste

Pour cette section, nous allons implémenter une classe Pile.

Exécuter Pile() doit renvoyer un objet de la classe Pile qui représente une pile vide.

En plus de sa méthode __init__, on va implémenter :

  • une méthode est_vide qui ne prend aucun argument et qui renvoie True si la pile est vide. Sinon, elle renvoie False.

  • une méthode empiler qui prend un argument x. Elle ajoute l’élément x au sommet de la pile.

  • une méthode depiler qui ne prend aucun argument. Elle enlève l’élément au sommet de la pile et le renvoie. S’il n’existe pas, renvoie None.

  • sa méthode __str__ qui renvoie les éléments de la pile de haut en bas, séparés par des espaces.

  • sa méthode __len__ qui renvoie combien d’éléments sont dans la pile.

class Pile:
    
    def ❓❓❓:
        # On utilise une liste pour répresenter la pile.
        self.contenu = ❓❓❓
        
    def est_vide(self):
        return ❓❓❓
    
    def empiler(self, ❓❓❓):
        ❓❓❓
        
    def depiler(self):
        if self.est_vide():
            return ❓❓❓
        return ❓❓❓
    
    def __str__(self):
        resultat = ❓❓❓
        for element in ❓❓❓:
            resultat = str(❓❓❓) + " " + resultat
        return resultat
    
    def __len__(self):
        return ❓❓❓

ma_pile = Pile()
print( ma_pile.depiler() ) # None
ma_pile.empiler(33)
ma_pile.empiler(44)
ma_pile.empiler('+')
print(ma_pile) # + 44 33
print(ma_pile.depiler()) # +
print(ma_pile) # 44 33
print(len(ma_pile)) # 2

None
+ 44 33 
+
44 33 
2

Exercices

Selon Shrek:

Les ogres, c’est comme les oignons. Ils ont des couches.

Dans cet exercice, nous allons explorer cette citation perspicace en utilisant de piles en Python.

Instanciez un objet de classe Pile et affectez-le à une variable appelée shrek.

Empilez les cinq chaînes suivantes dans l’objet shrek :

  • 'expériences passées'
  • 'vulnérabilités émotionnelles'
  • 'apparence extérieure'
  • 'personnalité'
  • 'souvenirs et désirs profonds'

tel que si nous enlevons (dépile) les couches une par une, la première enlevée (dépilée) sera 'apparence extérieure', puis 'personnalité', ensuite 'expériences passées', puis 'vulnérabilités émotionnelles', et enfin 'souvenirs et désirs profonds'.”

# ⚠️ Exécutez toujours les deux cellules précédentes avant de lancer ce test. ⚠️
print( shrek.depiler() ) # apparence extérieure
print( shrek.depiler() ) # personnalité
print( shrek.depiler() ) # expériences passées
print( shrek.depiler() ) # vulnérabilités émotionnelles
print( shrek.depiler() ) # souvenirs et désirs profonds

Rappelez-vous qu’une liste possède parmi ses méthodes .append() et .pop(). Nous pourrions représenter une pile avec une liste sans écrire toute une classe.

Par exemple, nous pouvons initialiser pile comme une liste vide.

pile = []
  • Quelle méthode d’une liste pouvons-nous utiliser pour « empiler » une valeur ?
  • Empilez la valeur 1 puis 2 puis 3 à pile.
pile.❓❓❓(1)
pile.❓❓❓(2)
pile.❓❓❓(3)
print(pile) # [1, 2, 3]
  • Complétez les phrases suivantes en disant « haut » ou « bas » :
    • Le premier élément pile[0] de la liste pile représente le ❓❓❓ de la pile qu’elle représente.
    • Le dernier élément pile[-1] de la liste pile représente le ❓❓❓ de la pile qu’elle représente.
  • Quelle méthode d’une liste pouvons-nous utiliser pour « depiler » une valeur ?
  • Depiler un élément de pile.
pile.❓❓❓()
print(pile) # [1, 2]

Modifiez le code suivant afin qu’il renvoie le sommet actuel de la pile.

pile[❓❓❓]

Écrivez un code qui renvoie le nombre d’éléments dans la pile.

# Pour cet exemple, il doit renvoyer `2`.

La fonction suivante prend un objet de la classe Pile.

def mystere(pile):
    resultat = Pile()
    while len(pile) > 0:
        x = pile.depiler()
        resultat.empiler(x)
    return resultat

Supposons qu’on appelle mystere(pile) pour une pile qui contient (du haut vers le bas) 111, 222 et 333 :

  • Que renverra mystere(pile) ?
  • La taile de notre pile originale change-t-elle ? Si oui, pourquoi ?
# Utiliser cette cellule pour experimenter.

La fonction suivante est censée dépiler l’élément du haut de la pile et renvoyer cet élément entouré d’emojis de fleurs, mais elle ne fonctionne pas correctement.

  • Expliquez pourquoi elle ne fonctionne pas correctement.
  • Corrigez la fonction.
def fleurs(pile):
    # Dépile l'élément au sommet de la pile.
    pile.depiler()
    # Puis, le renvoie entouré de fleurs.
    return "🌸 " + str(pile.depiler()) + " 🌸"

ma_pile = Pile()
ma_pile.empiler("Bonjour !")
ma_pile.empiler("Je veux de la brioche.")
ma_pile.empiler("Les fleurs sentent bon !")
fleurs(ma_pile) # 🌸 Les fleurs sentent bon ! 🌸

Écrivez une fonction appelée empiler_plusiers_fois qui prend 3 arguments :

  • pile, une liste qui représente une pile,
  • x, la valeur à empiler, et
  • n, un entier positif, le nombre de fois que x doit être empilé sur la pile.

Elle empile la valeur x n fois sur pile. En gros, cette fonction modifie pile et ne retourne rien.

def empiler_plusiers_fois(❓, ❓, ❓):
    for ❓ in range(❓):
        ❓.❓(❓)

ma_pile = [1, 2, 3, 4, 5]
resultat = empiler_plusiers_fois(ma_pile, 6, 4)
print(ma_pile) # [1, 2, 3, 4, 5, 6, 6, 6, 6]
print(type(resultat)) # <class 'NoneType'>
empiler_plusiers_fois(ma_pile, 7, 2)
print(ma_pile) # [1, 2, 3, 4, 5, 6, 6, 6, 6, 7, 7]
empiler_plusiers_fois(ma_pile, 8, 0)
print(ma_pile) # [1, 2, 3, 4, 5, 6, 6, 6, 6, 7, 7]

Cette fonction modifie un de ses arguments, qui est une liste. Cela sera-t-il possible si nous choisissons de représenter la pile comme un tuple à la place ? Justifiez votre réponse.

Écrivez une fonction somme_curieuse qui prend un objet nombres de la classe Pile en argument.

Nous supposons que tous les éléments de nombres sont des nombres.

La fonction somme_curieuse commence avec une variable resultat égale à 0.

Elle dépile chaque élément de nombres un par un.

Chaque fois qu’elle dépile un élément, elle ajoute x*y à resultat, où x est la valeur de l’élément dépilé et y est le nombre d’éléments restants dans la liste.

Elle renvoie resultat.

❓❓❓ somme_curieuse(nombres):
    resultat = ❓❓❓
    ❓❓❓ len(nombres) > 0:
        x = ❓❓❓
        y = ❓❓❓
        ❓❓❓ x*y
    return ❓❓❓

ma_pile = Pile()
ma_pile.empiler(5)
ma_pile.empiler(-3.14)
ma_pile.empiler(100)
ma_pile.empiler(-1000)
print( somme_curieuse(ma_pile) ) # -2803.14
print( len(ma_pile) ) # 0

L’exemple ci-dessus a été calculé comme suit :

(−1000×3)+(100×2)+(−3.14×1)+(5×0)=−2803.14(-1000 \times 3) + (100 \times 2) + (-3.14 \times 1) + (5 \times 0) = -2803.14

Écrire une classe PileEntiers.

Elle doit fonctionner exactement de la même manière que Pile, mais avec certaines contraintes lors de l’empilement.

  • Si vous essayez d’empiler quelque chose qui n’est pas de type entier, affichez Type invalide ! au lieu de l’empiler.
  • Si vous essayez d’empiler un entier dont la valeur est supérieure ou égale au nombre actuellement au sommet de la pile, alors affichez Nombre trop élevé ! au lieu de l’empiler.

Vous pouvez copier et modifier la classe Pile si vous le souhaitez.

ma_pile = PileEntiers()
ma_pile.empiler('11') # Type invalide !
ma_pile.empiler(11)
ma_pile.empiler(8)
ma_pile.empiler(5)
print(ma_pile) # 5 8 11
ma_pile.empiler(11) # Nombre trop élevé !
print(ma_pile) # 5 8 11
ma_pile.empiler(1)
ma_pile.empiler(-2)
print(ma_pile) # -2 1 5 8 11 
ma_pile.empiler(0) # Nombre trop élevé !

Écrivez une fonction depile_express qui prend un argument, pile, qui est une liste représentant une pile.

La fonction dépile la valeur du dessus de la liste si elle existe. Si le nombre dépilé est un entier positif, disons x, alors elle dépile x éléments de plus ou jusqu’à ce que la pile soit vide.

Consultez les exemples pour plus d’informations.

ma_pile = ['a', 1, 'b', 5, -1, 'c', 'd', 2, 'e', 0]
depile_express(ma_pile)
print(ma_pile) # ['a', 1, 'b', 5, -1, 'c', 'd', 2, 'e']
depile_express(ma_pile)
print(ma_pile) # ['a', 1, 'b', 5, -1, 'c', 'd', 2]
depile_express(ma_pile)
print(ma_pile) # ['a', 1, 'b', 5, -1]
depile_express(ma_pile)
print(ma_pile) # ['a', 1, 'b', 5]
depile_express(ma_pile)
print(ma_pile) # []

Dans cet exercice, nous définissons une classe Livres.

Elle aura deux attributs : l’un sera le titre et l’autre le nombre de volumes.

Cette classe représente une pile de livres, avec le premier volume en bas et le volume le plus récent en haut.

class Livres:
    def __init__(self, titre, vols):
        self.titre = titre
        self.volumes = vols

De plus, dans cet exercice, nous allons représenter des piles en utilisant des listes. Nous n’empilerons que des objets de la classe Livres dans cette liste.

Regardez l’exemple suivant :

potter = Livres(titre="Harry Potter", vols=7)
rougon = Livres("Les Rougon-Macquart", 20)
prince = Livres(titre="Le Petit Prince", vols=1)

ma_pile = Pile()
ma_pile.empiler(rougon)
ma_pile.empiler(prince)
ma_pile.empiler(potter)

Écrivez une fonction depile_livre qui dépile un volume du haut de la pile et imprime le nom du livre.

Plus précisement:

Si la pile est vide, elle renvoie la chaîne “Plus de livres !”.

Supposez que le sommet de la pile (qui est un objet de la classe Livres) a un attribut de volume de valeur vo.

Si vo est exactement un, dépilez l’objet du haut de la pile.
Si vo est strictement supérieur à un, décrémentez cet attribut de 11.

Dans les deux cas, renvoyez une chaîne de la forme : titre : Volume vo.

Regardez les exemples pour plus de clarté.

potter = Livres(titre="Harry Potter", vols=7)
rougon = Livres("Les Rougon-Macquart", 20)
prince = Livres(titre="Le Petit Prince", vols=1)

ma_pile = Pile()

ma_pile.empiler(prince)
print( depile_livre(ma_pile) ) # Le Petit Prince : Volume 1
print( depile_livre(ma_pile) ) # Plus de livres !

ma_pile.empiler(rougon)
ma_pile.empiler(prince)
ma_pile.empiler(potter)

print( depile_livre(ma_pile) ) # Harry Potter : Volume 7
print( depile_livre(ma_pile) ) # Harry Potter : Volume 6
print( depile_livre(ma_pile) ) # Harry Potter : Volume 5
print( depile_livre(ma_pile) ) # Harry Potter : Volume 4
print( depile_livre(ma_pile) ) # Harry Potter : Volume 3
print( depile_livre(ma_pile) ) # Harry Potter : Volume 2
print( depile_livre(ma_pile) ) # Harry Potter : Volume 1
print( depile_livre(ma_pile) ) # Le Petit Prince : Volume 1
print( depile_livre(ma_pile) ) # Les Rougon-Macquart : Volume 20
print( depile_livre(ma_pile) ) # Les Rougon-Macquart : Volume 19

Modifiez uniquement la valeur de la chaîne s ci-dessous afin que la cellule suivante affiche VICTOIRE !.

pile1 = Pile()
pile1.empiler('V')
pile1.empiler('I')
pile1.empiler('C')
pile1.empiler('T')
pile1.empiler('O')
pile1.empiler('R')

pile2 = Pile()
pile2.empiler('E')
pile2.empiler(' ')
pile2.empiler('!')

# Vous ne pouvez modifier que cette ligne !
s = "❓❓❓"
############################################
resultat = ""

for c in s:
    if c == '<':
        pile1.empiler(pile2.depiler())
    if c == '>':
        pile2.empiler(pile1.depiler())
    if c == '1':
        x = pile1.depiler()
        resultat += x
        pile1.empiler(x)
    if c == '2':
        x = pile2.depiler()
        resultat += x
        pile2.empiler(x)

print(resultat)
Posts on NSIRSS
Posts on this blog RSS