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 Prochaine révision Les deux révisions suivantes | ||
gestion_piles [2008/04/18 18:34] tyrtamos |
gestion_piles [2008/05/02 07:32] 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) | ||
+ | |||
+ | On rencontre souvent ces problèmes de gestion de piles: pile LIFO (last in first out) et pile FIFO (first in first out). | ||
+ | |||
+ | 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 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) ===== | ===== Gestion de piles lifo (dernier entré, premier sorti) ===== | ||
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) |
- | # exemple | + | # exemples |
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 85: | Ligne 121: | ||
* 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 (hors de %%-x.taille() <= i < +x.taille()%%), | * si l'un des index fournis n'est pas valide (hors de %%-x.taille() <= i < +x.taille()%%), | ||
Ligne 109: | Ligne 145: | ||
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) |
| | ||
- | # exemple | + | # exemples |
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 186: | Ligne 237: | ||
* renvoie le nombre d' | * renvoie le nombre d' | ||
+ | |||
+ | < | ||
+ | < | ||
+ | <style type=" | ||
+ | <!-- | ||
+ | body {background-image: | ||
+ | --> | ||
+ | </ | ||
+ | </ | ||
+ | < | ||
+ | </ | ||
+ | </ | ||