17 - Implémenter une Pile

⏪

⏬

⏩

1 - Type list

2 - Pile tuple

3 - Objet

4 - Dico+Tableau

Nous sommes parvenus à implémenter le type Liste sous la forme de plusieurs structures de données ayant des comportements internes différents mais ayant les mêmes fonctions d'interface primitives.

Liste contiguë IMMUABLE avec des tableaux statiques : mauvaise idée, insertion et suppression linéaire partout.
Liste contiguë MUABLE avec des tableaux dynamiques, comme le type list de Python : insertion et suppression à coût constant sur la dernière case mais linéaire ailleurs.
Liste chaînée IMMUABLE avec un tuple () ou (valeur de tête, queue) : insertion et suppression à coût constant sur la tête, mais linéaire alleurs.
Liste chaînée MUABLE avec des Classes Cellule et Liste : insertion et suppression à coût constant sur la tête, mais linéaire alleurs.

Aujourd'hui, nous allons implémenter le type abstrait Pile.

Prerequis : l'activité sur la Pile et celles sur les implémentations des Listes.

Documents de cours : open document ou pdf

1 - Implémentation d'une pile via un tableau dynamique

⇩ ⇧ ⤊

Les 5 fonctions primitives

Les 5 fonctions primitives à réaliser avec le meilleur coût possible sont :

PRIMITIVES pour un type IMMUABLE

nouvellePile() -> Pile : on crée une nouvelle Pile vide.
estPileVide(p:Pile) -> bool ou juste estVide() : renvoie un booléen qui vaut True si la pile p transmise est une pile vide.
empiler(p:Pile, elt:Elt) -> Pile : on renvoie une pile en rajoutant l'élément elt au sommet p.
depiler(p:Pile NON VIDE) -> Pile : on supprime le sommet et renvoie la nouvelle pile p. La fonction n'est définie que si la pile n'est pas vide.
lireSommet(p:Pile NON VIDE) -> Elt : on renvoie l'élément qui occupe le sommet. La fonction n'est définie que si la pile n'est pas vide.

Attention, pour les types muables, les fonctions d'insertion et de suppression ont un prototype différent :

PRIMITIVES pour un type MUABLE

empiler(p:Pile, elt:Elt) -> None
depiler(p:Pile NON VIDE) -> Element

Le principe est donc de tenter de réaliser une implémentation où les primitives auront un coût le plus faible possible.

Tentons de partir sur des primitives à coût constant.

Cela veut donc dire qu'on veut que les fonctions d'insertion et de suppression soient à coût constant.

Réfléchissons :

Nous voulons implémenter la Pile sous forme d'un tableau de type list.
Nous savons que l'insertion et la suppression sur l'indice 0 est à coût LINEAIRE dans ces tableaux dynamiques.
Nous savons que l'insertion et la suppression sur l'indice de fin (avec les méthodes append() et pop() est à coût amorti CONSTANT dans ces tableaux dynamiques.
CONCLUSION : nous allons placer le SOMMET de notre Pile du côté de l'indice final.

Quelques explications sur le contenu interne du tableau (on notera que les instructions correspondent bien à un type mutable) : on ne stocke pas la réponse d'empiler() puisque cette réponse est ... None.


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


>>> empiler(a, 10)


>>> empiler(a, 20)


>>> depiler(a)
20

Localisation du Sommet dans l'implémentation tableau

Les données de la Pile sont dans un tableau.

On place le Sommet de la Pile à la fin du tableau pour profiter des coûts constants des méthodes append() et pop().

graph LR A("[0]") --- B("[1]") --- C("[2]") -.- D("[n-2]") --- E("[n-1] Sommet") -. empilement -.- I(("+")) E -. dépilement -.- F(("-")) style A fill:#99f,stroke:#333,stroke-width:2px style E fill:#ff9,stroke:#333,stroke-width:2px style B fill:#99f,stroke:#333,stroke-width:2px style C fill:#99f,stroke:#333,stroke-width:2px style D fill:#99f,stroke:#333,stroke-width:2px

01° Compléter les différentes primitives pour parvenir à implémenter notre Pile MUABLE sous forme d'un tableau dynamique à l'interne.

'''MODULE d'implémentation de type abstrait PILE MUABLE
    en utilisant des TABLEAUX DYNAMIQUES
 
La Pile vide sera représentée par un tableau vide [].
Le sommet d'une Pile non vide est situé en fin de tableau.
 
Fonctions primitives
--------------------
... : nouvelle_pile() -> 'Pile'
... : est_pile_vide(p:'Pile') -> bool
... : empiler(p:'Pile', elt:'Element') -> None
... : depiler(p:'Pile NON VIDE') -> 'Element'
... : lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
'''
 
def nouvelle_pile() -> 'Pile':
    '''Renvoie une nouvelle Pile vide'''
    pass
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    pass
 
def empiler(p:'Pile', elt:'Element' ) -> None:
    '''Modifie la pile p en rajouter elt au sommet'''
    pass
 
def depiler(p:'Pile NON VIDE') -> 'Element':
    '''Supprime le sommet de la Pile p et renvoie l'élément supprimé'''
    pass
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    pass
 
 
 
if __name__ == '__main__':
    a = nouvelle_pile()
    empiler(a, 0)
    empiler(a, 5)
    empiler(a, 10)
    empiler(a, 15)
     
    s = lire_sommet(a)
    assert s == 15
     
    depiler(a)
    s = lire_sommet(a)
    assert s == 10

02° Estimer le coût des cinq fonctions primitives.

Correction ?

...CORRECTION...

Difficile de répondre sans connaître les codes des méthodes correspondantes de Python. C'est bien cela le problème de cette façon de faire.

Si on suppose que

l'accès à la dernière case avec les crochets est à coût constant,
le rajout d'une case en fin de tableau avec append() et
la suppression de la dernière case pop() est à coût constant,

alors les opérations sur le sommet (lecture/modification et insertion/suppression) sont toutes à coût constant.

Implémentation du type Pile (MUABLE) en utilisant un TABLEAU DYNAMIQUE Python

'''MODULE d'implémentation de type abstrait PILE MUABLE
    en utilisant des TABLEAUX DYNAMIQUES
 
La Pile vide sera représentée par un tableau vide [].
Le sommet d'une Pile non vide est situé en fin de tableau.
 
Fonctions primitives
--------------------
CST : nouvelle_pile() -> 'Pile'
CST : est_pile_vide(p:'Pile') -> bool
CST : empiler(p:'Pile', elt:'Element') -> None
CST : depiler(p:'Pile NON VIDE') -> 'Element'
CST : lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
'''
 
def nouvelle_pile() -> 'Pile':
    '''Renvoie une nouvelle Pile vide'''
    return []
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    return p == []
 
def empiler(p:'Pile', elt:'Element' ) -> None:
    '''Modifie la pile p en rajouter elt au sommet'''
    p.append(elt)                                 # rajoute un élément à la fin du tableau
 
def depiler(p:'Pile NON VIDE') -> 'Element':
    '''Supprime le sommet de la Pile p et renvoie l'élément supprimé'''
    return p.pop()                                # supprime et renvoie le dernier élément du tableau
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    return p[len(p)-1]                            # ou même return p[-1]
 
 
 
if __name__ == '__main__':
    a = nouvelle_pile()
    empiler(a, 0)
    empiler(a, 5)
    empiler(a, 10)
    empiler(a, 15)
     
    s = lire_sommet(a)
    assert s == 15
     
    depiler(a)
    s = lire_sommet(a)
    assert s == 10

Attention : dans la version MUABLE (ou MUTABLE en franglais), la pile est modifiée directement en mémoire. Pour modifier une pile, il faut donc écrire quelque chose comme empiler(a, 15) puisque la fonction ne renvoie rien. N'écrivez SURTOUT PAS a = empiler(a, 15). Sinon, votre Pile contiendra None après exécution !

03° Utiliser cette implémentation 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 = nouvelle_pile()
>>> empiler(a, 5)
>>> a
[5]
 
>>> empiler(a, 10)
>>> a
[5, 10]
 
>>> empiler(a, 20)
>>> a
[5, 10, 20]
 
>>> depiler(a)
20
 
>>> a
[5, 10]
 
>>> depiler(a)
10
 
>>> a
[5]
 
>>> empiler(a, 40)
>>> a
[5, 40]
 
>>> depiler(a)
40
 
>>> a
[5]
 
>>> 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.

2 - Implémentation d'une Pile via une liste chaînée de tuples

⇩ ⇧ ⤊

Nous allons ici implémenter une Pile IMMUABLE en reprenant l'idée d'une liste chaînée dont les cellules sont des tuples (valeur de Tête, Queue) en remplaçant les noms des éléments pour qu'ils soient ceux de la Pile : un tuple (valeur du sommet, reste de la Pile).

Tentons de partir sur des primitives à coût constant.

Cela veut donc dire qu'on veut que les fonctions d'insertion et de suppression soient à coût constant.

Réfléchissons :

Nous voulons implémenter la Pile sous forme d'un tuple n'ayant que deux éléments : la valeur à l'indice 0 et la cellule suivante sur l'indice 1.
Nous savons que l'insertion et la suppression sur la tête de la liste chainée est à coût CONSTANT.
Nous savons que l'insertion et la suppression sur la cellule de fin est à côut LINEAIRE.
CONCLUSION : nous allons placer le SOMMET de notre Pile du côté de la TETE de la Liste chaînée.

Localisation du Sommet dans l'implémentation liste chaînée de tuples

Les données de la Pile sont dans les cellules de la liste chaînée.

On place le Sommet de la Pile sur la Tête de la liste chaînée pour profiter des coûts constants des fonctions inserer_tete() et supprimer_tete().

graph LR F(("+")) -.- empilement -.- A("Tete et Sommet") --> B("Cellule 1") --> C("Cellle 2") -.-> D("Cellule n-2") ---> E("Cellule n-1 de Fin") I(("+")) -.- dépilement -.- A style E fill:#99f,stroke:#333,stroke-width:2px style A fill:#ff9,stroke:#333,stroke-width:2px style B fill:#99f,stroke:#333,stroke-width:2px style C fill:#99f,stroke:#333,stroke-width:2px style D fill:#99f,stroke:#333,stroke-width:2px

04° Compléter les différentes primitives pour parvenir à implémenter notre Pile IMMUABLE sous forme du tuple à l'interne.

'''MODULE d'implémentation de type abstrait PILE IMMUABLE
   en utilisant des Cellules TUPLES pour former une liste chaînée
 
La Pile vide sera représentée par un tuple vide ().
Le sommet d'une Pile non vide est situé du même côté que la tête de la liste chaînée associée.
 
Fonctions primitives
--------------------
... : nouvelle_pile() -> 'Pile'
... : est_pile_vide(p:'Pile') -> bool
... : empiler(p:'Pile', elt:'Element') -> 'Pile'
... : depiler(p:'Pile NON VIDE') -> 'Pile'
... : lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
'''
 
def nouvelle_pile() -> 'Pile':
    '''Renvoie une nouvelle Pile vide'''
    pass
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    pass
 
def empiler(p:'Pile', elt:'Element' ) -> 'Pile':
    '''Renvoie une pile basée sur p mais en rajoutant elt au sommet'''
    pass
 
def depiler(p:'Pile NON VIDE') -> 'Pile':
    '''Renvoie une pile basée sur p mais en supprimant le sommet'''
    pass
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    pass
 
 
 
if __name__ == '__main__':
    a = nouvelle_pile()
    a = empiler(a, 0)
    a = empiler(a, 5)
    a = empiler(a, 10)
    a = empiler(a, 15)
     
    s = lire_sommet(a)
    assert s == 15
     
    a = depiler(a)
    s = lire_sommet(a)
    assert s == 10

05° Estimer le coût des cinq fonctions primitives.

Correction ?

...CORRECTION...

On retrouve les mêmes coûts qu'avec la liste chaînée dont les cellules sont des tuples : toutes les opérations sont à coût CONSTANT sur la tête.

Et c'est pour cela qu'on a placer le sommet du côté de la tête.

Implémentation du type Pile IMMUABLE en utilisant des Cellules TUPLES pour former une liste chaînée

'''MODULE d'implémentation de type abstrait PILE IMMUABLE
   en utilisant des Cellules TUPLES pour former une liste chaînée
 
La Pile vide sera représentée par un tuple vide ().
Le sommet d'une Pile non vide est situé du même côté que la tête de la liste chaînée associée.
 
Fonctions primitives
--------------------
CST : nouvelle_pile() -> 'Pile'
CST : est_pile_vide(p:'Pile') -> bool
CST : empiler(p:'Pile', elt:'Element') -> 'Pile'
CST : depiler(p:'Pile NON VIDE') -> 'Pile'
CST : lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
'''
 
def nouvelle_pile() -> 'Pile':
    '''Renvoie une nouvelle Pile vide'''
    return ()
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    return p == ()
 
def empiler(p:'Pile', elt:'Element' ) -> 'Pile':
    '''Renvoie une pile basée sur p mais en rajoutant elt au sommet'''
    return (elt, p)                               # renvoie un tuple contenant elt et menant ensuite à la pile p reçue
 
def depiler(p:'Pile NON VIDE') -> 'Pile':
    '''Renvoie une pile basée sur p mais en supprimant le sommet'''
    return p[1]                                   # renvoie un tuple qui est le reste de la pile p
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    return p[0]                                   # renvoie la valeur stockée dans la cellule Sommet
 
 
 
if __name__ == '__main__':
    a = nouvelle_pile()
    a = empiler(a, 0)
    a = empiler(a, 5)
    a = empiler(a, 10)
    a = empiler(a, 15)
     
    s = lire_sommet(a)
    assert s == 15
     
    a = depiler(a)
    s = lire_sommet(a)
    assert s == 10

Attention : dans la version IMMUABLE, la pile n'est pas vraiment modifiée. Pour modifier une pile, il faut donc écrire quelque chose comme a = empiler(a, 15)

06° Utiliser cette implémentation 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 = nouvelle_pile()
>>> a = empiler(a, 5)
>>> a
(5, ())
 
>>> a = empiler(a, 10)
>>> a
(10, (5, ()))
 
>>> a = empiler(a, 20)
>>> a
(20, (10, (5, ())))
 
>>> a = depiler(a)
(10, (5, ()))
 
>>> a
(10, (5, ()))
 
>>> depiler(a)
(5, ())
 
>>> a
(10, (5, ()))     # on voit que a n'a pas été modifié car on a juste écrit depiler(a)
 
>>> a = empiler(a, 40)
>>> a
(40, (10, (5, ())))
 
>>> a = depiler(a)
(10, (5, ()))
 
>>> a
(10, (5, ()))     # on voit que a a été modifié car on a écrit a = depiler(a)
 
>>> a = depiler(a)
(5, ())

3 - Implémentation d'une pile via une liste chaînée basée sur des cellules-objets

⇩ ⇧ ⤊

Nous allons ici implémenter une Pile MUABLE en reprenant l'idée d'une liste chaînée dont les cellules sont des instances d'une classe Cellule n'ayant que deux attributs : v pour la valeur et s pour le successeur.

Tentons de partir sur des primitives à coût constant.

Cela veut donc dire qu'on veut que les fonctions d'insertion et de suppression soient à coût constant.

Réfléchissons :

Nous voulons implémenter la Pile sous forme d'une liste chaînée simple. Comme pour la liste chaînée précédente, on sait qu'on ne parvient à insérer et supprimer à coût constant qu'au niveau de la Tête.
CONCLUSION : nous allons placer le SOMMET de notre Pile du côté de la TETE de la Liste chaînée.

Localisation du Sommet dans l'implémentation liste chaînée d'objets-cellules

Les données de la Pile sont dans les cellules de la liste chaînée.

On place le Sommet de la Pile sur la Tête de la liste chaînée pour profiter des coûts constants des fonctions inserer_tete() et supprimer_tete().

07° Compléter les différentes primitives pour parvenir à implémenter notre Pile MUABLE sous forme d'objets à l'interne.

Commencez par réaliser les méthodes de l'objet puis compléter les fonctions pour qu'un utilisateur utilisant vos fonctions ne se rende pas compte qu'on utilise des objets pour implémenter la Pile.

'''MODULE d'implémentation d'une Pile sous forme d'une liste Chaînée MUABLE
  en utilisant des Cellules-Objets pour former une liste chaînée
  où la Tete de la liste correspond au Sommet de la Pile.
 
  On peut manipuler directement l'objet Pile via les méthodes.
  On peut utiliser les fonctions sans se rendre compte qu'on manipule un objet.
 
Méthodes primitives de la classe Pile
-------------------------------------
CST : Pile() -> 'Pile'
CST : Pile.est_pile_vide(p:'Pile') -> bool
CST : Pile.empiler(p:'Pile', elt:'Element') -> None
CST : Pile.depiler(p:'Pile NON VIDE') -> 'Element'
CST : Pile.lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
Fonctions primitives de la Pile
-------------------------------
CST : Pile() -> 'Pile'
CST : Pile.est_pile_vide(p:'Pile') -> bool
CST : Pile.empiler(p:'Pile', elt:'Element') -> None
CST : Pile.depiler(p:'Pile NON VIDE') -> 'Element'
CST : Pile.lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
 
'''
# Déclaration des classes Cellule et Pile
 
class Cellule:
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
 
class Pile:
    def __init__(self):
        self.sommet = None
 
    def est_pile_vide(self:'Pile') -> bool:
        pass
 
    def empiler(self:'Pile', elt:'Element') -> None:
        pass
 
    def depiler(self:'Pile NON VIDE') -> 'Element':
        pass
 
    def lire_sommet(self:'Pile NON VIDE') -> 'Element':
        '''Renvoie la valeur au sommet de la Pile'''
        pass
 
# Déclaration des fonctions primitives si on veut "cacher" l'objet
 
def nouvelle_pile() -> 'Pile':
    pass
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    pass
 
def empiler(p:'Pile', elt:'Element' ) -> None:
    '''Rajoutant elt au sommet de la pile p'''
    pass
 
def depiler(p:'Pile NON VIDE') -> 'Element':
    '''Dépile et renvoie le sommet de la pile p'''
    pass
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    pass
 
 
# Programme-test
 
if __name__ == '__main__':
    p = nouvelle_pile()
    empiler(p, 0)
    empiler(p, 5)
    empiler(p, 10)
    assert lire_sommet(p) == 10
    depiler(p)
    assert lire_sommet(p) == 5

08° Estimer le coût des cinq fonctions primitives.

Correction ?

...CORRECTION...

On retrouve les mêmes coûts qu'avec la liste chaînée dont les cellules sont des tuples : toutes les opérations sont à coût CONSTANT sur la tête.

Et c'est pour cela qu'on a placer le sommet du côté de la tête.

Implémentation du type Pile MUABLE en utilisant des Cellules Objets pour former une liste chaînée

'''MODULE d'implémentation d'une Pile sous forme d'une liste Chaînée MUABLE
  en utilisant des Cellules-Objets pour former une liste chaînée
  où la Tete de la liste correspond au Sommet de la Pile.
 
  On peut manipuler directement l'objet Pile via les méthodes.
  On peut utiliser les fonctions sans se rendre compte qu'on manipule un objet.
 
Méthodes primitives de la classe Pile
-------------------------------------
CST : Pile() -> 'Pile'
CST : Pile.est_pile_vide(p:'Pile') -> bool
CST : Pile.empiler(p:'Pile', elt:'Element') -> None
CST : Pile.depiler(p:'Pile NON VIDE') -> 'Element'
CST : Pile.lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
Fonctions primitives de la Pile
-------------------------------
CST : Pile() -> 'Pile'
CST : Pile.est_pile_vide(p:'Pile') -> bool
CST : Pile.empiler(p:'Pile', elt:'Element') -> None
CST : Pile.depiler(p:'Pile NON VIDE') -> 'Element'
CST : Pile.lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
 
'''
# Déclaration des classes Cellule et Pile
 
class Cellule:
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
 
class Pile:
    def __init__(self):
        self.sommet = None
 
    def est_pile_vide(self:'Pile') -> bool:
        return self.sommet is None
 
    def empiler(self:'Pile', elt:'Element') -> None:
        '''Rajoute une nouvelle cellule contenant elt au sommet de la Pile'''
        nouvelle = Cellule(elt, None)  # Etape 1 : création de la cellule
        nouvelle.s = self.sommet       # Etape 2 : on relie la nouvelle cellule à l'"ancien" sommet
        self.sommet = nouvelle         # Etape 3 : modification de la liste
 
    def depiler(self:'Pile NON VIDE') -> 'Element':
        '''Supprime la cellule de tête et renvoie l'élément qui y était stocké'''
        ancienne_valeur = self.sommet.v  # Etape 1 : on mémorise la valeur au sommet
        self.sommet = self.sommet.s      # Etape 2 : le sommet devient le successeur du sommet supprimé
        return ancienne_valeur           # Etape 3 : on renvoie la valeur stockée
 
    def lire_sommet(self:'Pile NON VIDE') -> 'Element':
        '''Renvoie la valeur au sommet de la Pile'''
        return self.sommet.v
 
# Déclaration des fonctions primitives si on veut "cacher" l'objet
 
def nouvelle_pile() -> 'Pile':
    '''Renvoie une nouvelle Pile vide'''
    return Pile()
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    return p.est_pile_vide()
 
def empiler(p:'Pile', elt:'Element' ) -> None:
    '''Rajoutant elt au sommet de la pile p'''
    p.empiler(elt)
 
def depiler(p:'Pile NON VIDE') -> 'Element':
    '''Dépile et renvoie le sommet de la pile p'''
    return p.depiler()
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    return p.lire_sommet()
 
 
# Programme-test
 
if __name__ == '__main__':
    p = nouvelle_pile()
    empiler(p, 0)
    empiler(p, 5)
    empiler(p, 10)
    assert lire_sommet(p) == 10
    depiler(p)
    assert lire_sommet(p) == 5

Mais on peut faire bien plus simple : notre Pile utilise une liste chaînée muable. Pourquoi ne pas importer cette structure que nous avons déjà réalisée et simplement la manipuler ?

09° Télécharger le module suivant qui implémente une liste chaînée sous forme de Cellules-objets. Répérer bien le répertoire dans lequel vous le placer puisque vous allez devoir y placer un second programme.

MODULE Liste chaînée objet MUABLE

10° Créer ce programme en le plaçant au même endroit que notre module liste_chainee_tete.

'''MODULE d'implémentation d'une Pile sous forme d'une liste Chaînée MUABLE
  en utilisant des Cellules-Objets pour former une liste chaînée
  où la Tete de la liste correspond au Sommet de la Pile.
 
Fonctions primitives de la Pile
-------------------------------
CST : Pile() -> 'Pile'
CST : Pile.est_pile_vide(p:'Pile') -> bool
CST : Pile.empiler(p:'Pile', elt:'Element') -> None
CST : Pile.depiler(p:'Pile NON VIDE') -> 'Element'
CST : Pile.lire_sommet(p:'Pile NON VIDE') -> 'Element'
 
'''
 
from liste_chainee_tete import Liste
 
# Déclaration des fonctions primitives si on veut "cacher" l'objet
 
def nouvelle_pile() -> 'Pile':
    '''Renvoie une nouvelle Pile vide'''
    return Liste()
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    return p.est_liste_vide()
 
def empiler(p:'Pile', elt:'Element' ) -> None:
    '''Rajoutant elt au sommet de la pile p'''
    p.inserer_tete(elt)
 
def depiler(p:'Pile NON VIDE') -> 'Element':
    '''Dépile et renvoie le sommet de la pile p'''
    return p.supprimer_tete()
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    return p.premier()
 
 
# Programme-test
 
if __name__ == '__main__':
    p = nouvelle_pile()
    empiler(p, 0)
    empiler(p, 5)
    empiler(p, 10)
    assert lire_sommet(p) == 10
    depiler(p)
    assert lire_sommet(p) == 5

CONCLUSION

Avantage de ce module par rapport à la Pile où nous avions tous reconstruit : beaucoup plus léger, on utilise juste la Liste.

Désavantage : notre module possède une dépendance. Il faut donc d'abord récuper le module sur la Liste avant de pouvoir utiliser le notre.

4 - Mini-Projet pour les plus rapides : Pile sous forme dictionnaire + tableau statique

⇩ ⇧ ⤊

Bon, à vous de travailler : on veut créer une implémentation de Pile muable ne pouvant contenir que 10 élements.

Le principe est le suivant :

On crée un dictionnaire qui encodera la pile et qui intégre

le nombre d'éléments dans la Pile via une clé "nbr",
le nombre d'éléments maximum dans la Pile via une clé "max",
les données de la Pile via une clé "data"

On crée un tableau statique contenant 10 cases vides. Ce tableau est destiné à contenir les données de notre Pile et sa référence est la valeur associée à la clé "data".

Un exemple d'utilisation qui devra fonctionner de la même manière avec votre implémentation une fois qu'elle sera fonctionnelle.


>>> a = nouvellePile()
>>> empiler(5, a)
>>> a
{'nb': 1, 'max': 10, 'data': [5, None, None, None, None, None, None, None, None, None]}
 
>>> empiler(10, a)
>>> a
{'nb': 2, 'max': 10, 'data': [5, 10, None, None, None, None, None, None, None, None]}
 
>>> empiler(20, a)
>>> a
{'nb': 3, 'max': 10, 'data': [5, 10, 20, None, None, None, None, None, None, None]}
 
>>> estPileVide(a)
False
 
>>> estPilePleine(a)
False
 
>>> taille(a)
3
 
>>> depiler(a)
20
 
>>> a
{'nb': 2, 'max': 10, 'data': [5, 10, None, None, None, None, None, None, None, None]}
 
>>> empiler(40, a)
>>> a
{'nb': 3, 'max': 10, 'data': [5, 10, 40, None, None, None, None, None, None, None]}
 
>>> depiler(a)
40
 
>>> depiler(a)
10
 
>>> depiler(a)
5
 
>>> depiler(a)
>>> a
{'nb': -1, 'max': 10, 'data': [None, None, None, None, None, None, None, None, None, None]}

Remarquez bien que comme nous avons dépiler une pile vide, le compteur final donne quelque chose d'aberrant : la taille de la pile vaudrait -1 éléments !

Et voici le début de l'implémentation. A vous de la finir !

'''Implémentation de type abstrait PILE MUABLE en utilisant un dictionnaire et un tableau statique'''
 
# Phase d'importation
 
# Phase de déclaration des CONSTANTES et variables globales
 
TAILLE = 10
 
# Phase de déclaration des classes et fonctions
 
class Elt:
    '''Juste pour pouvoir noter Elt dans les prototypes'''
 
class Pile:
    '''Juste pour pouvoir noter Pile dans les prototypes'''
 
def nouvellePile() -> Pile:
    '''Renvoie la référence d'une nouvelle Pile de TAILLE limitée'''
    p = {}
    p['nb'] = 0  # contient le nombre de données stockées
    p['max'] = TAILLE
    p['data'] = [None for x in range(TAILLE)]  # Aucune donnée au début
    return p
 
def estPileVide(p:Pile) -> bool:
    '''Renvoie True si la Pile est bien vide, False sinon'''
    return p['nb'] == 0
 
def estPilePleine(p:Pile) -> bool:
    '''Renvoie True si la Pile est pleine, False sinon'''
    pass
 
def empiler(elt:Elt, p:Pile) -> None:
    '''Empile l'élément dans une pile NON PLEINE'''
    pass
 
def depiler(p:Pile) -> Elt:
    '''Dépile et renvoie le sommet d'une pile NON VIDE'''
    pass
 
def lireSommet(p:Pile) -> Elt:
    '''Renvoie la donnée stockée au sommet de la pile NON VIDE p'''
    pass
 
def taille(p:Pile) -> int:
    pass
 
 
def tester():
    '''Fonction ne servant qu'à valider en partie vos fonctions d'interface'''
    print("DEBUT DU JEU DE TEST...")
    a = nouvellePile()
    assert a == {'nb': 0, 'max': 10, 'data': [None, None, None, None, None, None, None, None, None, None]}
    print("... Création : ok")
    empiler(5, a)
    assert a == {'nb': 1, 'max': 10, 'data': [5, None, None, None, None, None, None, None, None, None]}
    empiler(10, a)
    assert a == {'nb': 2, 'max': 10, 'data': [5, 10, None, None, None, None, None, None, None, None]}
    empiler(20, a)
    assert a == {'nb': 3, 'max': 10, 'data': [5, 10, 20, None, None, None, None, None, None, None]}
    print("... Empilement : ok")
    assert estPileVide(a) == False
    assert estPilePleine(a) == False
    assert taille(a) == 3
    assert depiler(a) == 20
    assert a == {'nb': 2, 'max': 10, 'data': [5, 10, None, None, None, None, None, None, None, None]}
    empiler(40, a)
    assert a == {'nb': 3, 'max': 10, 'data': [5, 10, 40, None, None, None, None, None, None, None]}
    assert depiler(a) == 40
    assert depiler(a) == 10
    assert depiler(a) == 5
    assert a == {'nb': 0, 'max': 10, 'data': [None, None, None, None, None, None, None, None, None, None]}
    print("... Dépilement : ok")
    print("FIN DU JEU DE TESTS.")
 
# --- Programme principal ---
 
if __name__ == '__main__':
    import doctest
    DEBUG = False  # Passer la constante à True pour activer le jeu de tests via assertions
    if DEBUG:
        tester()
    doctest.testmod()  # Pour utiliser la documentation comme jeu de tests

✎ 08° Voici la notation :

Implémentation correcte : 8 points
Avoir utiliser autant que possible les fonctions d'interface déjà réaliser, même dans le code des autres fonctions d'interface : 2 points
Justification du type de coût en lecture, en insertion et en suppression : 2 points
Création d'une fonction inverser() qui inverse le sommet et l'élément suivant pour une pile d'au moins 2 éléments : 2 points
Création d'une fonction vider() qui vide la pile NON VIDE : 2 points
Documentation des différentes fonctions d'interface : 2 points
Réalisation d'assertion pour vérifier que les piles à gérer ne sont ni vide avant lecture ou suppression, ni pleine en cas d'insertion, que la pile contient bien au moins deux éléments avant inversion... : 2 points.

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

⏪

⏫

⏩