(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:
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.
Une pile LIFO est assimilable à un tas:
Voilà le code proposé:
#!/usr/bin/python # -*- coding: utf-8 -*- class PileLifo(object): """PileLifo(object): pile LIFO: objet de type tas => on dépile l'élément le plus récent empilé""" def __init__(self,maxpile=None): self.pile=[] self.maxpile = maxpile def empile(self,element,idx=None): if (self.maxpile!=None) and (len(self.pile)==self.maxpile): raise ValueError ("erreur: tentative d'empiler dans une pile pleine") if idx==None: idx=len(self.pile) self.pile.insert(idx,element) def depile(self,idx=-1): if len(self.pile)==0: raise ValueError ("erreur: tentative de depiler une pile vide") if idx<-len(self.pile) or idx>=len(self.pile): raise ValueError ("erreur: element de pile à depiler n'existe pas") return self.pile.pop(idx) def element(self,idx=-1): if idx<-len(self.pile) or idx>=len(self.pile): raise ValueError ("erreur: element de pile n'existe pas") return self.pile[idx] def copiepile(self,imin=0,imax=None): if imax==None: imax=len(self.pile) if imin<0 or imax>len(self.pile) or imin>=imax: raise ValueError ("erreur: mauvais indice(s) pour l'extraction par copiepile") return list(self.pile[imin:imax]) 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 d'utilisation: x=PileLifo() print x.copiepile() # affiche [] print x.pilevide() # affiche True x.empile('A') x.empile(5) x.empile(['toto','titi','tata']) print x.copiepile() # affiche [['toto', 'titi', 'tata'], 5, 'A'] z=x.depile() print z # affiche A print x.copiepile() # affiche [['toto', 'titi', 'tata'], 5] print x.taille() # affiche 2 print x.element() # affiche 5
Commentaires sur ce code:
x=PileLifo(maxpile=None):
x.empile(element,idx=None):
x.depile(idx=-1):
x.element(idx=-1):
x.copiepile() ou x.copiepile(imin,imax):
x.pilevide():
x.pilepleine():
x.taille():
Une pile FIFO est assimilable à une file d'attente ou une pile de dossier à traiter:
Voilà le code proposé:
#!/usr/bin/python # -*- coding: utf-8 -*- class PileFifo(object): """PileFifo(object): pile FIFO: objet de type file d'attente => on depile l'élément le plus ancien empilé""" def __init__(self,maxpile=None): self.pile=[] self.maxpile = maxpile def empile(self,element,idx=0): if (self.maxpile!=None) and (len(self.pile)==self.maxpile): raise ValueError ("erreur: tentative d'empiler dans une pile pleine") self.pile.insert(idx,element) def depile(self,idx=-1): if len(self.pile)==0: raise ValueError ("erreur: tentative de depiler une pile vide") if idx<-len(self.pile) or idx>=len(self.pile): raise ValueError ("erreur: element de pile à depiler n'existe pas") return self.pile.pop(idx) def element(self,idx=-1): if idx<-len(self.pile) or idx>=len(self.pile): raise ValueError ("erreur: element de pile à lire n'existe pas") return self.pile[idx] def copiepile(self,imin=0,imax=None): if imax==None: imax=len(self.pile) if imin<0 or imax>len(self.pile) or imin>=imax: raise ValueError ("erreur: mauvais indice(s) pour l'extraction par copiepile") return list(self.pile[imin:imax]) 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 d'utilisation: x=PileFifo() print x.copiepile() # affiche [] print x.pilevide() # affiche True x.empile('A') x.empile(5) x.empile(['toto','titi','tata']) print x.copiepile() # affiche [['toto', 'titi', 'tata'], 5, 'A'] z=x.depile() print z # affiche A print x.copiepile() # affiche [['toto', 'titi', 'tata'], 5] print x.taille() # affiche 2 print x.element() # affiche 5
Commentaires sur ce code:
x=PileFifo(maxpile=None):
x.empile(element,idx=None):
x.depile(idx=-1):
x.element(idx=-1):
x.copiepile() ou x.copiepile(imin,imax):
x.pilevide():
x.pilepleine():
x.taille():
Amusez-vous bien!