Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Dernière révision Les deux révisions suivantes | ||
gestion_piles [2008/04/26 19:17] tyrtamos |
gestion_piles [2008/05/02 08:18] tyrtamos |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
- | ====== Gestion de piles lifo et fifo ====== | + | ====== Gestion de piles LIFO et FIFO ====== |
+ | (modification le 2/5/2008: ajout taille maxi et améliorations diverses) | ||
- | ===== Gestion | + | On rencontre souvent ces problèmes de gestion |
- | Une pile lifo est assimilable à un tas: | + | Le code proposé ici permet non seulement la gestion élémentaire (empile et depile), mais aussi de nombreuses possibilités supplémentaires: |
+ | |||
+ | * on peut empiler n' | ||
+ | |||
+ | * on peut fixer une taille maxi, | ||
+ | |||
+ | * on peut insérer ou retirer un élément à n' | ||
+ | |||
+ | * on peut lire un élément de n' | ||
+ | |||
+ | * on peut obtenir une copie de tout ou partie de la pile, | ||
+ | |||
+ | * on peut avoir un accès direct à la pile si les méthodes proposées ne suffisent pas. Par exemple pour chercher, lire ou modifier un attribut de l' | ||
+ | |||
+ | Les données et opérations anormales (exemple: tenter de dépiler une pile vide) génèrent des exceptions afin que des réponses erronées ne soient jamais renvoyées silencieusement. Il appartient au code utilisateur de gérer ces exceptions. | ||
+ | |||
+ | ===== Gestion de piles LIFO (dernier entré, premier sorti) ===== | ||
+ | |||
+ | Une pile LIFO est assimilable à un tas: | ||
* quand on ajoute un élément (=empile), on le met au dessus de la pile. | * quand on ajoute un élément (=empile), on le met au dessus de la pile. | ||
Ligne 17: | Ligne 36: | ||
class PileLifo(object): | class PileLifo(object): | ||
- | """ | + | """ |
- | def __init__(self): | + | |
- | self._pile=[] | + | def __init__(self, |
- | + | self.pile=[] | |
- | def empile(self, | + | self.maxpile = maxpile |
- | self._pile.append(element) | + | |
- | + | def empile(self, | |
- | def depile(self): | + | |
- | return self._pile.pop() | + | raise ValueError |
- | + | | |
- | def element(self, | + | idx=len(self.pile) |
- | return self._pile[i] | + | self.pile.insert(idx, |
- | + | ||
- | def pile(self, | + | def depile(self,idx=-1): |
- | if imax=None: | + | if len(self.pile)==0: |
- | imax=len(self._pile) | + | raise ValueError (" |
- | return list(self._pile[imin: | + | if idx< |
- | + | raise ValueError (" | |
- | def estvide(self): | + | return self.pile.pop(idx) |
- | return len(self._pile)==0 | + | |
+ | def element(self, | ||
+ | if idx< | ||
+ | raise ValueError (" | ||
+ | return self.pile[idx] | ||
+ | |||
+ | def copiepile(self, | ||
+ | if imax==None: | ||
+ | imax=len(self.pile) | ||
+ | if imin<0 or imax> | ||
+ | raise ValueError (" | ||
+ | return list(self.pile[imin: | ||
+ | |||
+ | def pilevide(self): | ||
+ | return len(self.pile)==0 | ||
+ | |||
+ | def pilepleine(self): | ||
+ | return self.maxpile!=None and len(self.pile)==self.maxpile | ||
+ | |||
def taille(self): | def taille(self): | ||
- | return len(self._pile) | + | return len(self.pile) |
# exemples d' | # exemples d' | ||
x=PileLifo() | x=PileLifo() | ||
- | print x.pile() # affiche [] | + | print x.copiepile() # affiche [] |
- | print x.estvide() # affiche True | + | print x.pilevide() # affiche True |
x.empile(' | x.empile(' | ||
x.empile(5) | x.empile(5) | ||
x.empile([' | x.empile([' | ||
- | print x.pile() # affiche [' | + | print x.copiepile() # affiche [[' |
z=x.depile() | z=x.depile() | ||
- | print z # affiche [' | + | print z # affiche |
- | print x.pile() | + | print x.copiepile() |
print x.taille() | print x.taille() | ||
print x.element() | print x.element() | ||
Ligne 59: | Ligne 95: | ||
__**Commentaires sur ce code:**__ | __**Commentaires sur ce code:**__ | ||
- | **A l' | + | **x=PileLifo(maxpile=None):** |
* créé une instance de la classe PileLifo() et l' | * créé une instance de la classe PileLifo() et l' | ||
- | * la pile créée appartient à l' | + | * la pile créée appartient à l' |
+ | * en mentionnant un paramètre, on peut fixer une taille maxi de la pile. Sans ce maxi, il n'y a pas de limite supérieure, | ||
- | **x.empile(element): | + | **x.empile(element,idx=None):** |
- | * insère | + | * ajoute |
- | * on peut empiler | + | * en ajoutant un index comme paramètre supplémentaire, |
- | * il n' | + | * génère une exception si on a précisé une taille maxi de la pile et si elle est déjà pleine |
- | **x.depile() ou z=x.depile() :** | + | **x.depile(idx=-1):** |
- | * retire de la pile l' | + | * sans paramètre, |
* on peut dépiler sans récupérer l' | * on peut dépiler sans récupérer l' | ||
- | * une tentative | + | * avec un index comme paramètre, on peut retirer un élément |
+ | * génère | ||
- | **x.element() ou x.element(i):** | + | **x.element(idx=-1):** |
- | * sans argument, renvoie l' | + | * sans paramètre, renvoie l' |
- | * avec un argument, renvoie l' | + | * avec un index comme paramètre, renvoie l' |
- | * si l' | + | * si l' |
- | **x.pile() ou x.pile(imin, | + | **x.copiepile() ou x.copiepile(imin, |
- | * sans argument, renvoie la pile complète sous forme d'une liste. Vous noterez la présente de list() dans le code: sans cela, une modification de la liste renvoyée modifierait la pile. | + | * sans paramètre, renvoie |
- | * avec argument(s), vous pouvez préciser l' | + | * avec un ou deux paramètres, vous pouvez préciser l' |
- | * attention: les index d'une liste de longueur lg vont de 0 à lg-1 | + | * rappel: les index d'une liste de longueur lg vont de 0 à lg-1 |
* x.pile(2) ou x.pile(imin=2) renvoie comme liste la pile à partir de l' | * x.pile(2) ou x.pile(imin=2) renvoie comme liste la pile à partir de l' | ||
* x.pile(2,5) ou x.pile(2, | * x.pile(2,5) ou x.pile(2, | ||
* x.pile(imax=5): | * x.pile(imax=5): | ||
- | * NB: le syntaxe x.pile(imin=2, | + | * NB: le syntaxe x.pile(imin=2, |
- | * si l'un des index fournis n'est pas valide | + | * si l'un des index fournis n'est pas valide, génère une exception |
- | **x.estvide():** | + | **x.pilevide():** |
* renvoie True si la pile est vide, et False si elle ne l'est pas. | * renvoie True si la pile est vide, et False si elle ne l'est pas. | ||
+ | |||
+ | **x.pilepleine(): | ||
+ | * renvoie True si la pile est limitée en taille et si elle est pleine, et False si elle ne l'est pas. | ||
**x.taille(): | **x.taille(): | ||
* renvoie le nombre d' | * renvoie le nombre d' | ||
- | ===== Gestion de piles fifo (premier entré, premier sorti) ===== | + | ===== Gestion de piles FIFO (premier entré, premier sorti) ===== |
- | Une pile fifo est assimilable à une file d' | + | Une pile FIFO est assimilable à une file d' |
* quand on ajoute un élément (=empile), on l' | * quand on ajoute un élément (=empile), on l' | ||
Ligne 109: | Ligne 150: | ||
class PileFifo(object): | class PileFifo(object): | ||
- | """ | + | """ |
- | def __init__(self): | + | |
- | self._pile=[] | + | def __init__(self, |
- | + | self.pile=[] | |
- | def empile(self, | + | self.maxpile = maxpile |
- | self._pile.insert(0,element) | + | |
- | + | def empile(self, | |
- | def depile(self): | + | |
- | return self._pile.pop() | + | raise ValueError (" |
- | + | self.pile.insert(idx,element) | |
- | def element(self, | + | |
- | return self._pile[i] | + | def depile(self,idx=-1): |
- | + | if len(self.pile)==0: | |
- | def pile(self, | + | raise ValueError (" |
+ | if idx< | ||
+ | raise ValueError (" | ||
+ | return self.pile.pop(idx) | ||
+ | |||
+ | def element(self, | ||
+ | if idx< | ||
+ | raise ValueError (" | ||
+ | return self.pile[idx] | ||
+ | |||
+ | def copiepile(self, | ||
if imax==None: | if imax==None: | ||
- | imax=len(self._pile) | + | imax=len(self.pile) |
- | return list(self._pile[imin: | + | if imin<0 or imax> |
- | + | raise ValueError (" | |
- | def estvide(self): | + | return list(self.pile[imin: |
- | return len(self._pile)==0 | + | |
+ | def pilevide(self): | ||
+ | return len(self.pile)==0 | ||
+ | |||
+ | def pilepleine(self): | ||
+ | return self.maxpile!=None and len(self.pile)==self.maxpile | ||
+ | |||
def taille(self): | def taille(self): | ||
- | return len(self._pile) | + | return len(self.pile) |
| | ||
# exemples d' | # exemples d' | ||
x=PileFifo() | x=PileFifo() | ||
- | print x.pile() # affiche [] | + | print x.copiepile() # affiche [] |
- | print x.estvide() # affiche True | + | print x.pilevide() # affiche True |
x.empile(' | x.empile(' | ||
x.empile(5) | x.empile(5) | ||
x.empile([' | x.empile([' | ||
- | print x.pile() # affiche [[' | + | print x.copiepile() # affiche [[' |
z=x.depile() | z=x.depile() | ||
print z # affiche A | print z # affiche A | ||
- | print x.pile() # affiche [[' | + | print x.copiepile() # affiche [[' |
print x.taille() | print x.taille() | ||
print x.element() | print x.element() | ||
Ligne 151: | Ligne 207: | ||
__**Commentaires sur ce code:**__ | __**Commentaires sur ce code:**__ | ||
- | **A l' | + | **x=PileFifo(maxpile=None):** |
* créé une instance de la classe PileFifo() et l' | * créé une instance de la classe PileFifo() et l' | ||
- | * la pile créée appartient à l' | + | * la pile créée appartient à l' |
+ | * en mentionnant un paramètre, on peut fixer une taille maxi de la pile. Sans ce maxi, il n'y a pas de limite supérieure, | ||
- | **x.empile(element): | + | **x.empile(element,idx=None):** |
- | * insère | + | * ajoute |
- | * on peut empiler | + | * en ajoutant un index comme paramètre supplémentaire, |
- | * il n' | + | * génère une exception si on a précisé une taille maxi de la pile et si elle est déjà pleine |
- | **x.depile() ou z=x.depile() :** | + | **x.depile(idx=-1):** |
- | * retire de la pile l' | + | * sans paramètre, |
* on peut dépiler sans récupérer l' | * on peut dépiler sans récupérer l' | ||
- | * une tentative | + | * avec un index comme paramètre, on peut retirer un élément |
+ | * génère | ||
- | **x.element() ou x.element(i):** | + | **x.element(idx=-1):** |
- | * sans argument, renvoie | + | * sans paramètre, renvoie |
- | * avec un argument, renvoie l' | + | * avec un index comme paramètre, renvoie l' |
- | * si l' | + | * si l' |
- | **x.pile() ou x.pile(imin, | + | **x.copiepile() ou x.copiepile(imin, |
- | * sans argument, renvoie la pile complète sous forme d'une liste. Vous noterez la présente de list() dans le code: sans cela, une modification de la liste renvoyée modifierait la pile. | + | * sans paramètre, renvoie |
- | * avec argument(s), vous pouvez préciser l' | + | * avec un ou deux paramètres, vous pouvez préciser l' |
- | * attention: les index d'une liste de longueur lg vont de 0 à lg-1 | + | * rappel: les index d'une liste de longueur lg vont de 0 à lg-1 |
* x.pile(2) ou x.pile(imin=2) renvoie comme liste la pile à partir de l' | * x.pile(2) ou x.pile(imin=2) renvoie comme liste la pile à partir de l' | ||
* x.pile(2,5) ou x.pile(2, | * x.pile(2,5) ou x.pile(2, | ||
* x.pile(imax=5): | * x.pile(imax=5): | ||
- | * NB: le syntaxe x.pile(imin=2, | + | * NB: le syntaxe x.pile(imin=2, |
- | * si l'un des index fournis n'est pas valide | + | * si l'un des index fournis n'est pas valide, génère une exception |
- | **x.estvide():** | + | **x.pilevide():** |
* renvoie True si la pile est vide, et False si elle ne l'est pas. | * renvoie True si la pile est vide, et False si elle ne l'est pas. | ||
+ | |||
+ | **x.pilepleine(): | ||
+ | * renvoie True si la pile est limitée en taille et si elle est pleine, et False si elle ne l'est pas. | ||
**x.taille(): | **x.taille(): | ||
* renvoie le nombre d' | * renvoie le nombre d' | ||
+ | \\ | ||
+ | Amusez-vous bien! | ||
+ | |||
+ | < | ||
+ | < | ||
+ | <style type=" | ||
+ | <!-- | ||
+ | body {background-image: | ||
+ | --> | ||
+ | </ | ||
+ | </ | ||
+ | < | ||
+ | </ | ||
+ | </ | ||