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 13:35] tyrtamos |
gestion_piles [2008/05/02 08:09] 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: |
- | * quand on ajoute un élément (=empile), | + | |
+ | |||
+ | * 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 retire un élément (=dépile), c'est l' | * quand on retire un élément (=dépile), c'est l' | ||
Ligne 16: | Ligne 35: | ||
# -*- coding: utf-8 -*- | # -*- coding: utf-8 -*- | ||
- | # pile lifo (last in first out): on dépile | + | class PileLifo(object): |
- | class Pile(object): | + | """ |
- | def __init__(self): | + | |
- | self._pile=[] | + | def __init__(self, |
+ | self.pile=[] | ||
+ | self.maxpile = maxpile | ||
+ | |||
+ | def empile(self, | ||
+ | | ||
+ | raise ValueError (" | ||
+ | if idx==None: | ||
+ | idx=len(self.pile) | ||
+ | self.pile.insert(idx, | ||
+ | |||
+ | def depile(self, | ||
+ | if len(self.pile)==0: | ||
+ | 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: | ||
+ | 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): | ||
+ | return len(self.pile) | ||
- | def empile(self, | + | # exemples d' |
- | self._pile.append(element) | + | x=PileLifo() |
- | + | print x.copiepile() | |
- | | + | print x.pilevide() |
- | | + | x.empile(' |
+ | x.empile(5) | ||
+ | x.empile([' | ||
+ | print x.copiepile() | ||
+ | z=x.depile() | ||
+ | print z # affiche A | ||
+ | print x.copiepile() | ||
+ | print x.taille() # affiche 2 | ||
+ | print x.element() | ||
+ | </ | ||
- | def element(self, | + | \\ |
- | | + | __**Commentaires sur ce code:**__ |
- | def pile(self,imin=0,imax=None): | + | **A l' |
- | if imax=None: | + | * créé une instance de la classe PileLifo() et l' |
- | imax=len(self._pile) | + | * la pile créée appartient à l' |
- | return list(self._pile[imin: | + | * on peut fixer une taille maxi de la pile. Sans ce maxi, il n'y a pas de limite supérieure, |
- | def estvide(self): | + | **x.empile(element, |
- | | + | * ajoute l' |
+ | * en ajoutant un index comme paramètre supplémentaire, | ||
+ | * génère une exception si on a précisé une taille maxi de la pile et si elle est déjà pleine | ||
- | def taille(self): | + | **x.depile(idx=-1):** |
- | | + | * sans paramètre, retire de la pile l' |
+ | * on peut dépiler sans récupérer l' | ||
+ | * avec un index comme paramètre, on peut retirer un élément de n' | ||
+ | * génère une exception si la pile est déjà vide ou si on tente de retirer un élément avec un mauvais index | ||
- | # exemple | + | **x.element(idx=-1): |
- | x=Pile() | + | * sans paramètre, renvoie l' |
- | print x.pile() # affiche [] | + | * avec un index comme paramètre, renvoie l' |
- | print x.estvide() # affiche True | + | * si l' |
+ | |||
+ | **x.copiepile() ou x.pile(imin, | ||
+ | * sans paramètre, renvoie une copie de la pile complète sous forme d'une liste. | ||
+ | * avec un ou deux paramètres, | ||
+ | * 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,5) ou x.pile(2, | ||
+ | * x.pile(imax=5): | ||
+ | * NB: le syntaxe x.pile(imin=2, | ||
+ | * si l'un des index fournis n'est pas valide, génère une exception | ||
+ | |||
+ | **x.pilevide(): | ||
+ | * 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(): | ||
+ | * renvoie le nombre d' | ||
+ | |||
+ | ===== Gestion de piles FIFO (premier entré, premier sorti) ===== | ||
+ | |||
+ | Une pile FIFO est assimilable à une file d' | ||
+ | |||
+ | * quand on ajoute un élément (=empile), on l' | ||
+ | |||
+ | * quand on retire un élément (=dépile), on retire l' | ||
+ | |||
+ | Voilà le code proposé: | ||
+ | |||
+ | <code python> | ||
+ | #!/ | ||
+ | # -*- coding: utf-8 -*- | ||
+ | |||
+ | class PileFifo(object): | ||
+ | """ | ||
+ | |||
+ | def __init__(self, | ||
+ | self.pile=[] | ||
+ | self.maxpile = maxpile | ||
+ | |||
+ | def empile(self, | ||
+ | if (self.maxpile!=None) and (len(self.pile)==self.maxpile): | ||
+ | raise ValueError (" | ||
+ | self.pile.insert(idx, | ||
+ | |||
+ | def depile(self, | ||
+ | if len(self.pile)==0: | ||
+ | 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: | ||
+ | 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): | ||
+ | return len(self.pile) | ||
+ | |||
+ | # exemples | ||
+ | x=PileFifo() | ||
+ | print x.copiepile() # affiche [] | ||
+ | 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() | ||
- | </ | + | </ |
- | Commentaires sur ce code: | + | \\ |
+ | __**Commentaires sur ce code:**__ | ||
- | **A l' | + | **A l' |
- | * la pile créée appartient à l' | + | * créé une instance de la classe PileFifo() et l' |
+ | * la pile créée appartient à l' | ||
+ | * 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):** |
- | * on peut empiler | + | * ajoute l' |
- | * il n' | + | * en ajoutant un index comme paramètre supplémentaire, |
+ | * 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):** |
+ | * sans paramètre, retire de la pile l' | ||
* 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(): | + | **x.copiepile() ou x.pile(imin,imax):** |
- | * 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' |
+ | * 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: | ||
+ | --> | ||
+ | </ | ||
+ | </ | ||
+ | < | ||
+ | </ | ||
+ | </ | ||