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'importe quel objet Python (y compris une autre pile!), et pas simplement les types de base,

• on peut fixer une taille maxi,

• on peut insérer ou retirer un élément à n'importe quel niveau de la pile,

• on peut lire un élément de n'importe quel niveau de la pile sans le retirer de la pile,

• 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'objet géré.

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:

• quand on ajoute un élément (=empile), on le met au dessus de la pile.

• quand on retire un élément (=dépile), c'est l'élément du dessus de la pile qu'on retire (=le dernier arrivé).

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):

• créé une instance de la classe PileLifo() et l'affecte à la variable x
• la pile créée appartient à l'instance de classe, c'est à dire que x=PileLifo() et y=PileLifo() vont créer 2 piles indépendantes
• 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, à part la mémoire de l'ordinateur

x.empile(element,idx=None):

• ajoute l'élément en dessus de la pile
• en ajoutant un index comme paramètre supplémentaire, on peut insérer un nouvel élément à n'importe quel niveau de la pile
• 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(idx=-1):

• sans paramètre, retire de la pile l'élément qui est au dessus de la pile (=le plus récent) et le renvoie
• on peut dépiler sans récupérer l'élément (x.depile()) ou en le récupérant (z = x.depile())
• avec un index comme paramètre, on peut retirer un élément de n'importe quel niveau de la pile
• 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

x.element(idx=-1):

• sans paramètre, renvoie l'élément situé au dessus de la pile (=le candidat à être dépilé) sans le dépiler
• avec un index comme paramètre, renvoie l'élément d'index idx.
• si l'index idx n'est pas valide, déclenche une exception

x.copiepile() ou x.copiepile(imin,imax):

• sans paramètre, renvoie une copie de la pile complète sous forme d'une liste.
• avec un ou deux paramètres, vous pouvez préciser l'index de départ (0 par défaut) et l'index de fin+1 (=x.taille() par défaut):
  • 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'index 2 (=3ème élément) jusqu'à la fin
  • x.pile(2,5) ou x.pile(2,imax=5) ou x.pile(imin=2,imax=5): renvoie comme liste la pile entre les index 2 et 4 compris (5 exclu)
  • x.pile(imax=5): renvoie comme liste la pile entre les index 0 et 4 compris (5 exclu)
  • NB: le syntaxe x.pile(imin=2,5) est interdite avec Python (pas d'argument simple après un argument nommé)
  • 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'éléments de la pile

Une pile FIFO est assimilable à une file d'attente ou une pile de dossier à traiter:

• quand on ajoute un élément (=empile), on l'ajoute en dessous de la pile.

• quand on retire un élément (=dépile), on retire l'élément qui est au dessus de la pile (=le plus ancien dans la pile).

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):

• créé une instance de la classe PileFifo() et l'affecte à la variable x
• la pile créée appartient à l'instance de classe, c'est à dire que x=PileFifo() et y=PileFifo() vont créer 2 piles indépendantes
• 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, à part la mémoire de l'ordinateur

x.empile(element,idx=None):

• ajoute l'élément en dessous de la pile
• en ajoutant un index comme paramètre supplémentaire, on peut insérer un nouvel élément à n'importe quel niveau de la pile
• 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(idx=-1):

• sans paramètre, retire de la pile l'élément qui est au dessus de la pile (=le plus ancient) et le renvoie
• on peut dépiler sans récupérer l'élément (x.depile()) ou en le récupérant (z = x.depile())
• avec un index comme paramètre, on peut retirer un élément de n'importe quel niveau de la pile
• 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

x.element(idx=-1):

• sans paramètre, renvoie l'élément situé au dessus de la pile (=le candidat à être dépilé) sans le dépiler
• avec un index comme paramètre, renvoie l'élément d'index idx.
• si l'index idx n'est pas valide, déclenche une exception

x.copiepile() ou x.copiepile(imin,imax):

• sans paramètre, renvoie une copie de la pile complète sous forme d'une liste.
• avec un ou deux paramètres, vous pouvez préciser l'index de départ (0 par défaut) et l'index de fin+1 (=x.taille() par défaut):
  • 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'index 2 (=3ème élément) jusqu'à la fin
  • x.pile(2,5) ou x.pile(2,imax=5) ou x.pile(imin=2,imax=5): renvoie comme liste la pile entre les index 2 et 4 compris (5 exclu)
  • x.pile(imax=5): renvoie comme liste la pile entre les index 0 et 4 compris (5 exclu)
  • NB: le syntaxe x.pile(imin=2,5) est interdite avec Python (pas d'argument simple après un argument nommé)
  • 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'éléments de la pile

Amusez-vous bien!