TNSI : TD Piles⚓︎

Qu'est qu'une Pile?⚓︎

Représentation Verticale

Représentation Horizontale

Def

Une Pile ou Stack est une structure abstraite de données, linéaire, qui travaille en mode LIFO (Last In First Out) , ou Dernier Arrivé Premier Sorti . On pourra par exemple penser à une pile de livres, ou à une pile d'assiettes.

Interface d'une Pile⚓︎

Pte

L'interface (c'est-à-dire les opérations disponibles) d'une Pile contient a minima :

la création d'une pile vide
l'ajout d'un élément au sommet / dernier arrivé de la pile (qui sera forcément celui du dessus dans une représentation verticale, ou celui de droite dans une représentation horizontale). On dira qu'on empile ou push , idéalement en temps constant.
le retrait d'un élément du sommet de la pile (qui sera forcément celui du dessus dans une représentation verticale, ou celui de droite dans une représentation horizontale), et le renvoi de sa valeur. On dira qu'on dépile ou pop , idéalement en temps constant.

On considère l'enchaînement d'opérations ci-dessous. Écrire à chaque étape l'état de la pile p et la valeur éventuellement renvoyée.

Bien comprendre que la classe Pile() et ses méthodes n'ont pas encore été Implémentées (c'est-à-dire n'ont pas été concrètement écrites). Nous utilisons simplement son Interface.

ÉnoncéCorrigé

# On suppose que la classe Pile est déjà implémentée :
>>> p = Pile()
>>> p.empile(3)   # ou p.push(3)
>>> p.empile(5)
>>> p.est_vide()
>>> p.empile(1)
>>> p.depile()    # ou p.pop()
>>> p.depile()
>>> p.empile(9)
>>> p.depile()
>>> p.depile()
>>> p.est_vide()

# On suppose que la classe Pile est déjà implémentée :
>>> p = Pile()    # p=None
>>> p.empile(3)   # p= 3
>>> p.empile(5)   # p= 3 5 par convention
>>> p.est_vide()  #  False
>>> p.empile(1)   # p= 3 5 1
>>> p.depile()    # p= 3 5     valeur renvoyée : 1
>>> p.depile()    # p= 3       valeur renvoyée : 5
>>> p.empile(9)   # p= 3 9
>>> p.depile()    # p= 3       valeur renvoyée :9
>>> p.depile()    # p= None    valeur renvoyée : 3
>>> p.est_vide()  # True

Implémentation d'une Pile par un Tableau⚓︎

Dans cette partie, un Tableau sera implémenté par le type de données list de Python

Implémentation d'une Pile par un Tableau

Implémenter une classe Pile, disposant des méthodes suivantes :
- Pile() : crée une pile vide. Syntaxe : p = Pile() crée une Pile vide
- est_vide()->bool : indique si la pile est vide.
- empile(x:int)->None ou push(x:int)->None : insère un élément en haut (/à droite) de la pile. Ce sera le dernier arrivé
- depile() ou pop() : renvoie la valeur de l'élément en haut /(à droite/premier à sortir) de la pile ET le supprime de la pile.
- get_sommet() qui renvoie la valeur du sommet de la Pile, sans le dépiler, ou None si la Pile est vide
- une méthode magique __repr__() : permet d'afficher la pile sous forme agréable lorsque :
  - l'on tape >>> p ou >>> print(p) dans un Interpréteur Python
  - l'on utilise l'instruction print(p) dans un Script Python Exemple d'affichage : |•|3|6|2|5| où 3 est le premier arrivé, et 5 est le sommet/dernier arrivé)
- Modifier le constructeur __init__() de sorte que l'on puisse maintenant instancier la classe Pile en lui passant en argument un objet de type list de Python:
```
# Créer une Pile `p` initialisée par la liste Python [1,2,3], 
# qui sera représentée dans un Terminal par `|•|1|2|3|`
p = Pile([1,2,3])
```
- vider() : vide la Pile. Syntaxe : p.vider() vide p
- copy() renvoie une copie profonde de la Pile (la modification de l'une n'entraine pas la modification de l'autre). Syntaxe : p1 = p.copy()
- renverse() renverse la Pile. Syntaxe : p.renverse() renverse p
- concatene() : concatène deux Piles. Syntaxe : p1.concatene(p2) concatène p2 au dessus de p1, et p2 est vidée
Quelle est la complexité en temps des opérations empile() et depile() ? Conclusion : Le type list de Python est-il parfaitement adapté pour implémenter une Pile?
Précisément, quelle méthode dans notre classe Pile est le facteur limitant, c'est à dire ralentit nos opérations? et pourquoi ?

Implémentation d'une Pile par une Liste Chaînée⚓︎

On dispose de la Classe Cellule qui permet de modéliser une Cellule d'une Pile :

class Cellule :
    def __init__(self, valeur, suivante):
        self.valeur = valeur
        self.suivante = suivante

Implémentation d'une Pile par une Liste Chaînée

À l'aide de cette classe Cellule, implémenter une classe Pile par une Liste Chaînée (Simple), disposant exactement de la même interface que dans l'exercice précédent :
- Pile() : crée une pile vide, et initialise le constructeur __init__(), avec un attribut sommet. Syntaxe : p = Pile() crée une Pile vide
- est_vide()->bool : indique si la pile est vide.
- empile(x:int)->None ou push(x:int)->None : insère un élément en haut (/à droite) de la pile. x sera le sommet / dernier arrivé
- depile() ou pop() : renvoie la valeur de l'élément en haut /(à droite/premier à sortir) de la pile ET le supprime de la pile.
  
  La classe Pile doit donc pouvoir être utilisée (par exemple) comme suit :
```
p = Pile()
p.empile(5)   # ou p.push(5)
p.empile(8)
p.depile()    # ou p.pop()
```
- get_sommet() qui renvoie la valeur du sommet de la Pile, sans le dépiler
- une méthode magique __repr__() : permet d'afficher la pile sous forme agréable lorsque :
  - l'on tape >>> p ou >>> print(p) dans un Interpréteur Python
  - l'on utilise l'instruction print(p) dans un Script Python Exemple d'affichage : |•|3|6|2|5| où 3 est le premier arrivé, et 5 est le sommet/dernier arrivé)
- Modifier le constructeur __init__() de sorte que l'on puisse maintenant instancier la classe Pile en lui passant en argument un objet de type list de Python:
```
# Créer une Pile `p` initialisée par la liste Python [1,2,3],
# qui sera représentée dans un Terminal par `|•|1|2|3|`
p = Pile([1,2,3])
```
- vider() : vide la Pile. Syntaxe : p.vider() vide p
- copy() renvoie une copie profonde de la Pile (la modification de l'une n'entraine pas la modification de l'autre). Syntaxe : p1 = p.copy()
- renverse() renverse la Pile. Syntaxe : p.renverse() renverse p
- concatene() : concatène deux Piles. Syntaxe : p1.concatene(p2) concatène p2 au dessus de p1, et p2 est vidée
Étudier la complexité en temps des méthodes empile() / push(), et de depile() / pop()
Conclusion : Une Liste Chaînée est-elle parfaitement adaptée pour implémenter une Pile?

Exemples d'Utilisation des Piles⚓︎

Historique de Navigation

À l'aide de deux variables adresses et adresse_courante, et de la classe Pile créée plus haut, simulez une gestion de l'historique de navigation internet. Seules deux fonctions go_to(nouvelle_adresse) et back() sont à créer.

Chercher sur internet, des exemples classiques d'utilisation des Piles en informatique, voire dans toute autre discipline.