Ceci est une ancienne révision du document !

Table des matières

Gestion de piles lifo et fifo
- Gestion de piles lifo (dernier entré, premier sorti)
- Gestion de piles fifo (premier entré, premier sorti)

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, 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 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.

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

A l'initialisation, par exemple x=PileLifo() :

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.

x.empile(element):

insère l'élément en dessus de la pile
on peut empiler n'importe quel objet Python: nombre, chaîne, liste, tuple, dictionnaire, …, y compris une autre pile!
il n'y a pas de limite supérieure à la quantité d'éléments qu'on peut empiler, à part celle de la mémoire de l'ordinateur.

x.depile() ou z=x.depile() :

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())
une tentative de dépiler une pile vide produit une exception “IndexError” qu'il faudra gérer dans le code utilisateur

x.element() ou x.element(i):

sans argument, renvoie l'élément situé au dessus de la pile (=le candidat à être dépilé) sans le dépiler
avec un argument, renvoie l'élément d'index i. Pour être valide, cet indice doit être: -x.taille() <= i < +x.taille()
si l'index i n'est pas valide, déclenche une exception “IndexError” qu'il faudra gérer dans le code utilisateur

x.pile() 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.
avec argument(s), vous pouvez préciser l'index de départ (0 par défaut) et l'index de fin+1 (=x.taille() par défaut):
- attention: 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 (pas d'argument simple après un argument nommé)
- si l'un des index fournis n'est pas valide (hors de -x.taille() <= i < +x.taille()), génère une exception “IndexError” qu'il faudra gérer dans le code utilisateur

x.estvide():

renvoie True si la pile est vide, et False si elle ne l'est pas.

x.taille():

renvoie le nombre d'éléments de la pile

Gestion de piles fifo (premier entré, premier sorti)

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