Aller au contenu

Interface (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 Synthèse de ce qu'il faut retenir pour le bac

Interface du type abstrait Pile⚓︎

Point de cours 1

Une pile est un ensemble ordonné d'éléments qui se manipule comme une pile d'assiettes :

  • on peut ajouter une assiette au sommet de la pile, c'est l'opération empiler
  • on peut tester si une pile est vide, c'est l'opération pile_vide
  • si la pile n'est pas vide, on peut retirer l'assiette du sommet de de la pile, c'est l'opération dépiler

Comme dans une liste un seul élément est accessible directement, le sommet de la pile.

alt

Source : Gilles Lassus

L'interface du type abstrait Pile peut se réduire à quatre opérations :

Opération Signature Description
creer_pile creer_pile() Renvoie une pile vide
pile_vide pile_vide(pile) Renvoi un booléen indiquant si la pile est vide
empiler empiler(pile, elt) Ajoute elt au sommet de la pile
depiler depiler(pile) Retire l'élément au sommet de la pile et le renvoie

Quelques propriétés à retenir :

  • Le premier élément qu'on peut retirer d'une pile est forcément le dernier à y être entré, on dit que c'est une structure Last In First Out (LIFO).
  • En particulier si on dépile tous les élément, l'ordre dans lequel on les retire de la pile est l'inverse de leur ordre d'insertion.
  • L'opération empiler peut renvoyer une nouvelle pile si on implémente une pile immuable ou modifier la pile par effet de bord, si on implémente une pile mutable (voir cours liste mutable).
  • Les implémentations correctes du type Pile garantissent une complexité constante en \(O(1)\) pour les opérations depiler et empiler.

alt

Source : Pierre Duclosson

Exemple 1 : applications des piles

La structure de Pile se retrouve dans de nombreuses situations où on doit gérer un ensemble d'éléments :

  • à la fin d'un devoir un enseignant récupére une pile de copies et souvent il les corrige en commençant par le sommet de la pile.
  • les couches géologiques forment évidemment une pile
  • la pile de dossiers à traiter sur un bureau ...

Néanmoins si la pile est une structure naturelle pour stocker des objets car les opérations depiler et empiler sont peu coûteuses, ce n'est pas toujours une solution satisfaisante :

  • dans un rayon de supermarché il n'est pas raisonnable de stocker des yaourts sous forme de pile, sinon les plus anciens risquent de n'être jamais achetés
  • les personnes qui attendent depuis longtemps devant une salle de concerts avec placement libre ne souhaitent pas que les derniers arrivés soient les premiers entrés !

On retrouve aussi la structure de Pile dans de nombreuses situations en informatique :

  • L'historique d'un navigateur Web conserve les pages parcourues dans une pile : la flèche gauche permet de revenir en arrière (dépiler) et la flèche droite d'avancer (empiler)
  • Lors de l'évaluation d'une fonction récursive les contextes des appels récursifs imbriqués sont stockés dans une pile dont la taille est d'ailleurs limitée pour éviter les appels infinis. Lorsque la pile d'appels déborde, c'est le fameux stack overflow ! Pour éviter le dépassement de capacité de la pile d'appels, on peut exprimer une fonction récursive sous forme de boucle en utilisant une pile. Nous verrons une application dans l'algorithme d'exploration de graphe en profondeur.

Ci-dessous un exemple d'évolution de pile lors du calcul récursif du quatrième terme de la suite de Fibonacci.

alt

Source : Gilles Lassus

Exercice 1

💻 Saisir ses réponses sur Capytale

Faire un tableau d'évolution des variables stack et stack2 au cours de l'exécution du code ci-dessous. On considère qu'il s'agit de piles mutables.

🐍 Script Python
1
2
3
4
5
6
7
stack = creer_pile()
empiler(stack, 8)
empiler(stack, 4)
empiler(stack, 3)
stack2 = creer_pile()
while not pile_vide(stack):
    empiler(stack2, depiler(stack))

On représente une pile par sommet ->3,4,8| et une pile vide par sommet ->|.

Ligne stack stack2
1 sommet ->| rien
2 sommet ->8| rien
3 sommet ->4,8| rien
4 sommet ->3,4,8| rien
5 sommet ->3,4,8| sommet ->|
6 sommet ->3,4,8| sommet ->|
7 sommet ->4,8| sommet -3|
6 sommet ->4,8| sommet ->3|
7 sommet ->8| sommet ->4,3|
6 sommet ->8| sommet ->4,3|
7 sommet ->| sommet ->8,4,3|
6 sommet ->| sommet ->8,4,3|

Exercice 2

💻 Saisir ses réponses sur Capytale

Question 1

On considère une fonction utilisant les opérations du type abstrait Pile :

🐍 Script Python
1
2
3
4
5
6
7
8
9
def mystere(pile):
    autre = creer_pile()
    k = 0
    while not pile_vide(pile):
        empiler(autre, depiler(pile))
        k = k + 1
    while not pile_vide(autre):
        empiler(pile, depiler(autre))
    return k

Donnez la trace de l'application de cette fonction à la pile ci-dessous (sommet en haut):

📋 Texte
|    3     |
|__________|
|    4     |
|__________|
|    8     |
|__________|

On représente la pile initiale par sommet ->3,4,8| et la pile vide par sommet ->|

Ligne k pile autre
4 0 sommet ->3,4,8| sommet ->|
5 0 sommet ->4,8| sommet ->3|
6 1 sommet ->4,8| sommet ->3|
4 1 sommet ->4,8| sommet ->3|
5 1 sommet ->8| sommet ->4,3|
6 2 sommet ->8| sommet ->4,3|
4 2 sommet ->4,8| sommet ->3|
5 2 sommet ->| sommet ->8,4,3|
6 3 sommet ->| sommet ->8,4,3|
4 3 sommet ->| sommet ->8,4,3|
7 3 sommet ->| sommet ->8,4,3|
8 3 sommet ->8| sommet ->4,3|
7 3 sommet ->8| sommet ->4,3|
8 3 sommet ->4,8| sommet ->3|
7 3 sommet ->4,8| sommet ->3|
8 3 sommet ->3,4,8| sommet ->|
7 3 sommet ->3,4,8| sommet ->|
9 3 sommet ->3,4,8| sommet ->|

Question 2

En vous inspirant de la question précédente, écrire en Python une fonction qui détermine le maximum d'une pile d'entiers et le renvoie. La pile doit être revenue à son état initial après évaluation de la fonction.

🐍 Script Python
def maximum(pile):
    autre = creer_pile()
    maxi = depiler(pile)
    empiler(autre, maxi)
    while not pile_vide(pile):
        sommet = depiler(pile)
        if sommet > maxi:
            maxi = sommet
        empiler(autre, sommet)
    while not pile_vide(tmp):
        empiler(pile, depiler(autre))
    return maxi

Question 3

Écrire en Python une fonction qui inverse en place une pile d'entiers, c'est-à-dire qu'elle modifie la pile par effet de bord en inversant l'ordre des éléments dans la pile. On pourra utiliser deux piles auxiliaires.

🐍 Script Python
def inverser(pile):
    autre1 = creer_pile()
    while not pile_vide(pile):
        empiler(autre1, depiler(pile))
    autre2 = creer_pile()
    while not pile_vide(autre1):
        empiler(autre2, depiler(autre1))
    while not pile_vide(autre2):
        empiler(pile, depiler(autre2))