17 - Implémenter une Pile

⏪

⏬

⏩

1 - Pile tuple

2 - Pile tableau

3 - FAQ

Nous avons vu la différence entre les types abstraits et les structures de données concrètes.

Nous sommes parvenus à implémenter le type abstrait Liste sous la forme de plusieurs structures de données ayant le bon comportement.

Aujourd'hui, nous allons voir quelques implémentations possibles du type Pile et File. Nous allons donc créer les structures de données permettant de programmer des piles et des files.

Prerequis : les deux activités sur Pile et File, ainsi qu'au moins l'une des activités d'implémentation du type liste.

1 - Implémentation d'une Pile en tant que tuple

⇩ ⇧ ⤊

On rappelle d'abord ce qu'est le type abstrait Pile :

Type abstrait PILE - Principe LIFO

Principe général d'organisation de la PILE : LIFO

Une pile est un type abstrait de données ayant les propriétés suivantes :

il s'agit d'une séquence finie et ordonnée de données
on s'impose d'agir uniquement sur l'une des extrémités qu'on nomme le sommet :

insérer un élément au sommet se nomme l'empilement
supprimer un élément au sommet se nomme le dépilement

On désigne également la pile sous l'acronyme LIFO pour Last In First Out (à savoir), ou en français : Dernier arrivé, premier parti.

Fonctions d'interface pour une PILE (en version non mutable ici)

Voici la description des fonctions d'interface fondamentales que les algorithmes vont pouvoir effectuer sur le type Pile.

nouvellePile() -> Pile : on crée une nouvelle pile vide. On pourra l'identifier à (). En anglais, cela pourrait donner newStack.
pileVide(p:Pile) -> bool : renvoie un booléen qui vaut True si la pile p transmise est une pile vide. On peut également la nommer estVide. En anglais, cela pourrait donner isNil ou isNull.
empiler(elt:Elt, p:Pile) -> Pile : on renvoie une pile en rajoutant l'élément elt au sommet de la pile p. En anglais, ça se nomme push. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1))
depiler(p:Pile) -> Pile : on supprime le sommet et renvoie la nouvelle pile. En anglais, ça se nomme pop. La fonction n'est définie que si la pile n'est pas vide. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1)).
lireSommet(p:Pile) -> Elt : on renvoie l'élément qui occupe le sommet. La fonction n'est définie que si la pile n'est pas vide. En anglais, ça se nomme peek ou top

Si on regarde bien cette structure, on voit qu'elle correspond à une Liste en se donnant comme restriction de ne pouvoir agir que sur la Tête, qu'on nomme ici Sommet.

On peut donc écrire cette structure en reprenant notre implémentation tuple (tete,queue) en remplaçant les noms des éléments pour qu'ils soient ceux de la Pile.

Implémentation d'une Pile (non mutable) sous forme d'un tuple

class Elt :
    '''Juste pour pouvoir noter Elt dans les prototypes'''
 
class Pile :
    '''Juste pour pouvoir noter Pile dans les prototypes'''
 
'''Implémentation de type abstrait Pile en utilisant des tuples (sommet, autre_pile)'''
 
def nouvellePile() -> Pile :
    '''Renvoie une liste vide'''
    return ()
 
def pileVide(p:Pile) -> bool :
    '''Renvoie True si la pile est vide'''
    return p == ()
 
def empiler(elt:Elt, p:Pile) -> Pile :
    '''Renvoie une nouvelle pile où x est le sommet et pile la suite de notre nouvelle pile.'''
    return (elt, p)
 
def lireSommet(p:Pile) -> Elt :
    '''Renvoie la valeur stockée au sommet, sans la supprimer de la pile'''
    if not pileVide(p):
        return p[0]
 
def depiler(p:Pile) -> Pile :
    '''Renvoie une nouvelle pile où on a supprimé l'ancien sommet'''
    if pileVide(p): # la liste envoyée est ()
        return nouvellePile()
    else :
        return p[1]
 
def afficherPile(p:Pile) -> str:
    '''Renvoie une représentation de la Pile sous forme d'une séquence commençant par le sommet'''
    representation = "Sommet de la Pile "
    while not(pileVide(p)) :
        sommet = lireSommet(p)
        representation = representation + f" -> {sommet}"
        p = depiler(p)
    return representation

J'ai rajouté ici une fonction d'interface afficherPile permettant à l'utilisateur d'avoir une vision globale des données pour vous montrer ce que contient la pile. Normalement, nous ne sommes pas censés le faire : on ne devrait pouvoir accéder à ce qu'il y a sous le Sommet qu'après avoir enlevé ce sommet. Mais c'est juste pour vous montrer qu'on peut représenter les données de la Pile comme on veut.

Remarque : si on place 5 puis 10 puis 20 dans la pile, l'utilisation de la fonction afficherPile montrera ceci dans la console :


>>> a = nouvellePile()
>>> a = empiler(5, a)
>>> a = empiler(10, a)
>>> a
(10, (5, ()))
 
>>> a = empiler(20, a)
>>> a
(20, (10, (5, ())))
 
>>> afficherPile(a)
'Pile : Sommet -> 20 -> 10 -> 5'

01° Mettre en mémoire la version ci-dessous.

Au vu du code de la fonction ci-dessous, a-t-on affaire à une version mutable ou non mutable ?

 1
 2
 3

def empiler(elt:Elt, p:Pile) -> Pile :
    '''Renvoie une nouvelle pile où x est le sommet et pile la suite de notre nouvelle pile.'''
    return (elt, p)

Conclusion : lorsqu'on veut empiler, doit-on écrire a = empiler(5, a) ou juste empiler(5, a) ?

Correction ?

...CORRECTION...

La fonction empiler renvoie une donnée de type Liste, on voit bien qu'il s'agit d'une version non mutable.

Il faudra donc écrire le premier code, a = empiler(5, a) de façon à stocker la nouvelle pile dans une nouvelle variable, portant le même nom que l'ancienne si on veut.

Mais ceci fonctionne aussi : b = empiler(5, a).

02° L'utilisation stricte des fonctions d'interface permet-il à l'utilisateur de connaître l'implémentation interne des données ?

Correction ?

...CORRECTION...

Nous l'avons déjà vu de nombreuses fois : non.

La fonction afficherPile nous permet de fournir n'importe quelle représentation des données. Cela n'a pas forçément de lien avec la façon dont les vraies données sont mémorisées.

03° Regarder les instructions ci-dessous. Demandez vous ce qui va s'afficher sur la console à chaque fois que quelque chose doit s'afficher. Vérifiez ensuite en tapant le code dans le Shell.


>>> a = nouvellePile()
>>> a = empiler('bonjour', a)
>>> a = empiler('à', a)
>>> a = empiler('tous', a)
>>> a = empiler('!', a)
>>> afficherPile(a)
??? premier affichage à trouver ???
 
>>> x = lireSommet(a)
>>> x
??? deuxième affichage à trouver ???
 
>>> x = lireSommet(a)
>>> x
??? troisième affichage à trouver ???
 
>>> afficherPile(a)
??? quatrième affichage à trouver ???
 
>>> a = depiler(a)
>>> x = lireSommet(a)
>>> x
??? cinquième affichage à trouver ???
 
>>> afficherPile(a)
??? sixième affichage à trouver ???

Correction ?

...CORRECTION...


>>> a = nouvellePile()
>>> a = empiler('bonjour', a)
>>> a = empiler('à', a)
>>> a = empiler('tous', a)
>>> a = empiler('!', a)
>>> afficherPile(a)
'Pile : Sommet -> ! -> tous -> à -> bonjour'
 
>>> x = lireSommet(a)
>>> x
'!'
 
>>> x = lireSommet(a)
>>> x
'!'
 
>>> afficherPile(a)
'Pile : Sommet -> ! -> tous -> à -> bonjour'
 
>>> a = depiler(a)
>>> x = lireSommet(a)
>>> x
'tous'
 
>>> afficherPile(a)
'Pile : Sommet -> tous -> à -> bonjour'

04° Quel est le coût de la fonction empiler? De la fonction depiler ? De la fonction lireSommet ?

Correction ?

...CORRECTION...

Dans les 3 cas, il suffit d'agir sur le sommet. On a un accès constant puisqu'il suffit d'aller lire l'index 0 pour le sommet ou 1 pour le reste de la pile.

2 - Implémentation d'une pile dans un tableau dynamique

⇩ ⇧ ⤊

Nous pourrions implémenter la Pile comme un tableau statique ou comme une liste chaînée puisque la Pile est une sorte de cas particulier du type Liste.

En Python, les Piles ne sont pas nativement implémentées. Regardons comment réaliser une implémentation du type Pile en utilisant les méthodes natives de la structure de données tableau dynamique dont le type natif est list en Python... Je ne suis pas chef du vocabulaire. J'y suis pour rien .

Le principe est simple :

La méthode append des objets list permet de rajouter l'élément à la fin du tableau.
La méthode pop des objets list permet de supprimer l'élément situé à la fin du tableau, et elle le renvoie !

Implémentation du type Pile (mutable) en utilisant un tableau dynamique Python

class Elt :
    '''Juste pour pouvoir noter Elt dans les prototypes'''
 
class Pile :
    '''Juste pour pouvoir noter Pile dans les prototypes'''
 
'''Implémentation de type abstrait Pile en utilisant des tableaux dynamiques'''
 
def nouvellePile() -> Pile:
    return []
 
def pileVide(p:Pile) -> bool:
    return p == []
 
def empiler(elt:Elt, p:Pile) -> None:
    p.append(elt) # rajoute un élément à la fin du tableau
 
def depiler(p:Pile) -> Elt:
    if not pileVide(p):
        return p.pop() # supprime et renvoie le dernier élément du tableau
 
def lireSommet(p:Pile) -> Elt:
    if not pileVide(p):
        return p[len(p)-1] # ou return pile[-1]

Attention : dans la version mutable, la pile est modifiée directement en mémoire. Du coup, la fonction empiler ne renvoie rien (c'est une sorte de "procédure") et la fonction depiler est souvent utilisée pour renvoyer l'élément qu'on vient de supprimer.

Quelques explications sur le contenu interne du tableau (on notera que les instructions correspondent bien à un type mutable) :


>>> a = nouvellePile()
>>> empiler(5, a)


>>> empiler(10, a)


>>> empiler(20, a)


>>> depiler(a)
20

05°Estimer le coût des trois fonctions empiler, depiler et lireSommet.

Correction ?

...CORRECTION...

Difficile de répondre sans connaître les codes des méthodes correspondantes.

Si on suppose que l'accès à la dernière case , le rajout d'une case en fin de tableau et la suppression de la dernière case sont à coût constant, alors les trois opérations sont à coût constant.

06° Mettre en mémoire la version ci-dessous.

Au vu du code, a-t-on affaire à une version mutable ou non mutable ?

 1
 2

def empiler(elt:Elt, p:Pile) -> None:
    p.append(elt) # rajoute un élément à la fin du tableau

Doit-on écrire a = empiler(5, a) ou juste empiler(5, a) ?

Correction ?

...CORRECTION...

On constate que la fonction empiler ne renvoie rien et que la fonction depiler renvoie un élément, et non pas pas une nouvelle Pile. La structure de données Pile créée ici est donc une structure mutable.

Il faut donc taper empiler(5, a)

N'utilisez surtout pas la première version : vous allez juste remplir la variable a avec ... rien puisque la fonction renvoie renvoie None. Vous allez donc supprimer votre belle pile.

Si vous écrivez ceci : a = empiler(5, a)

Il se passe ceci : a = None

07° Utiliser cette version et sa fonction d'affichage pour constater qu'on a bien une Pile et, qu'à part la mutabilité, on ne peut pas savoir comment tout cela est implémenté à l'interne tant qu'on utilise uniquement les fonctions d'interface.


>>> a = nouvellePile()
>>> empiler(5, a)
>>> empiler(10, a)
>>> empiler(20, a)
>>> depiler(a)
20
 
>>> depiler(a)
10
 
>>> empiler(40, a)
>>> depiler(a)
40
 
>>> depiler(a)
5

Notez bien le comportement en Pile : le 40, qu'on rajoute plus tard, sort immédiatement alors qu'il est arrivé bien après : comportement LIFO.

Ce dernier exemple vous permet aussi de vous rendre compte que la pile fonctionne vraiment comme une pile d'assiettes ou de legos : on récupère nécessairement le dernier élément qu'on a inséré dans la Pile.

3 - FAQ

⇩ ⇧ ⤊

C'est quoi ce `return pile[-1]` alternatif dans la dernière fonction ?

Un raccourci Python pour dire : le premier élément en partant de la fin. C'est comme si on avait demandé un index valant la longeur du tableau - 1.

C'est une Pythonnerie. Un index de -1 veut dire le dernier élément. Un index de -2 veut dire l'avant-dernier...

On ne peut donc pas utiliser ceci dans un algorithme : dans certains langages, une demande d'index de -1 va déclencher une erreur.

22
23
24

def lireSommet(p:Pile) -> Elt:
    if not pileVide(p):
        return p[len(p)-1] # ou return pile[-1]

On pourait donc écrire ceci en Python :

22
23
24

def lireSommet(p:Pile) -> Elt:
    if not pileVide(p):
        return p[-1]

Activité publiée le 14 10 2020
Dernière modification : 14 10 2020
Auteur : ows. h.

⏪

⏫

⏩

17 - Implémenter une Pile

1 - Implémentation d'une Pile en tant que tuple

Type abstrait PILE - Principe LIFO

Implémentation d'une Pile (non mutable) sous forme d'un tuple

2 - Implémentation d'une pile dans un tableau dynamique

Implémentation du type Pile (mutable) en utilisant un tableau dynamique Python

3 - FAQ

C'est quoi ce return pile[-1] alternatif dans la dernière fonction ?

C'est quoi ce `return pile[-1]` alternatif dans la dernière fonction ?