Implémentation avec tableau
Le cadre
Dans certains langages de programmation, il n'y a pas de listes dynamiques, mais plutôt des tableaux. Rappelons qu'ils sont de taille fixe et contiennent des éléments homogènes.
Dans le cadre de cet exercice, nous allons certes utiliser les listes dynamiques de Python, mais en nous restreignant volontairement pour simuler l'utilisation de tableaux.
- Objectif
- Construire une classe
Piledont le support des données sera dans un tableau prédéfini. Une limitation évidente sera la taille maximale de toute pile créée.
Limitations
On peut certes écrire facilement cette implémentation avec un langage de programmation plus rudimentaire comme le C, mais il faudra considérer :
- La pile aura une taille maximale prédéfinie.
- La structure de la pile consommera toujours la même quantité de mémoire ; comme si elle était toujours pleine.
- Les éléments devront être aussi de taille constante et rudimentaires. Si on veut des éléments de taille variable, il faudra utiliser une pile d'adresses (des références) vers les éléments de taille variable.
Exercice
On donne le début d'une classe Pile :
class Pile():
"""Classe Pile avec tableaux Python"""
def __init__(self, taille_max: int):
self.taille_max = taille_max
self.données = [None] * taille_max # un tableau
self.i = 0
Compléter la classe Pile (est_vide, empile et dépile) :
- L'initialiseur prend
taille_maxen paramètre, et crée une pile vide.- qui s'appuie sur un tableau de
données, initialement rempli deNone.
- qui s'appuie sur un tableau de
- On peut empiler jusqu'à atteindre la
taille_max, - mais tenter d'empiler un élément de plus provoquera
raise ValueError("Pile pleine !") - Si on dépile, on remplacera la donnée dans le tableau par
None. - Tenter de dépiler alors que la pile est vide provoquera
raise ValueError("Pile vide !") - L'attribut
self.iindique :- l'indice du tableau où on va empiler le prochain élément,
- mais également la taille réelle de la pile.
- Enfin, si on peut dépiler, l'élément se trouve à l'indice précédent.
Justification de ValueError
Les cas d'erreurs (on tente de défiler depuis une pile vide, ou on tente d'empiler sur une pile pleine) sont gérés explicitement avec raise ValueError("message") ce choix est motivé par le comportement de Python si on cherche à faire min (ou max) sur une liste vide.
On aurait pu choisir IndexError qui correspond à un pop sur une liste vide... Ou bien KeyError dans d'autres situations...
Pourquoi pas IndexError ? Une pile pourrait certes être munie d'indices, c'est presque naturel ! Mais non, donc non, ce n'est pas l'esprit d'une pile.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)