Différences

Ci-dessous, les différences entre deux révisions de la page.

--- gestion_piles [2008/04/27 07:28]
tyrtamos
+++ gestion_piles [2008/05/02 08:18]
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 de piles lifo (dernier entré, premier sorti) =====
+On rencontre souvent ces problèmes de gestion de piles: pile LIFO (Last In First Out) et pile FIFO (First In First Out).
-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:
+  * 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.
+===== 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.
@@ Ligne 17: / Ligne 36: @@
 class PileLifo(object):
-    """PileLifo(object): pile Lifo (last in first out): on peut dépiler le dernier élément qui a été empilé (le plus récent dans la pile)"""
+    """PileLifo(object): pile LIFO: objet de type tas => on dépile l'élément le plus récent empilé"""
-    def __init__(self):
-        self._pile=[]
+    def __init__(self,maxpile=None):
+        self.pile=[]
-    def empile(self,element):
+        self.maxpile = maxpile
-        self._pile.append(element)
+    def empile(self,element,idx=None):
-    def depile(self):
+        if (self.maxpile!=None) and (len(self.pile)==self.maxpile):
-        return self._pile.pop()
+            raise ValueError ("erreur: tentative d'empiler dans une pile pleine")
+        if idx==None:
-    def element(self,i=-1):
+            idx=len(self.pile)
-        return self._pile[i]
+        self.pile.insert(idx,element)
-    def pile(self,imin=0,imax=None):
+    def depile(self,idx=-1):
-        if imax=None:
+        if len(self.pile)==0:
-            imax=len(self._pile)
+            raise ValueError ("erreur: tentative de depiler une pile vide")
-        return list(self._pile[imin:imax])
+        if idx<-len(self.pile) or idx>=len(self.pile):
+            raise ValueError ("erreur: element de pile à depiler n'existe pas")
-    def estvide(self):
+        return self.pile.pop(idx)
-        return len(self._pile)==0
+    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)
+        return len(self.pile)
 # exemples d'utilisation:
 x=PileLifo()
-print x.pile()  # affiche []
+print x.copiepile()  # affiche []
-print x.estvide()  # affiche True
+print x.pilevide()  # affiche True
 x.empile('A')
 x.empile(5)
 x.empile(['toto','titi','tata'])
-print x.pile()  # affiche ['A', 5, ['toto', 'titi', 'tata']]
+print x.copiepile()  # affiche [['toto', 'titi', 'tata'], 5, 'A']
 z=x.depile()
-print z  # affiche ['toto', 'titi', 'tata']
+print z  # affiche A
-print x.pile()  # affiche ['A', 5]
+print x.copiepile()  # affiche [['toto', 'titi', 'tata'], 5]
 print x.taille()  # affiche 2
 print x.element()  # affiche 5
@@ Ligne 59: / Ligne 95: @@
 __**Commentaires sur ce code:**__
-**A l'initialisation, par exemple x=PileLifo() :**
+**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.
+  * 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):**
+**x.empile(element,idx=None):**
-  * insère l'élément en dessus de la pile
+  * ajoute 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!
+  * en ajoutant un index comme paramètre supplémentaire, on peut insérer un nouvel élément à n'importe quel niveau de la 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.
+  * 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):**
-  * retire de la pile l'élément qui est au dessus de la pile (=le plus récent) et le renvoie
+  * 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())
-  * une tentative de dépiler une pile vide produit une exception "IndexError" qu'il faudra gérer dans le code utilisateur
+  * 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() ou x.element(i):**
+**x.element(idx=-1):**
-  * sans argument, renvoie l'élément situé au dessus de la pile (=le candidat à être dépilé) sans le dépiler
+  * sans paramètre, 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()%%
+  * avec un index comme paramètre, renvoie l'élément d'index idx.
-  * si l'index i n'est pas valide, déclenche une exception "IndexError" qu'il faudra gérer dans le code utilisateur
+  * si l'index i n'est pas valide, déclenche une exception
-**x.pile() ou x.pile(imin,imax):**
+**x.copiepile() ou x.copiepile(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 une copie de la pile complète sous forme d'une liste.
-  * 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):
+  * 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):
-    * attention: les index d'une liste de longueur lg vont de 0 à lg-1
+    * 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 (pas d'argument simple après un argument nommé)
+    * 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 (hors de %%-x.taille() <= i < +x.taille()%%), génère une exception "IndexError" qu'il faudra gérer dans le code utilisateur
+    * 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.
+**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
-===== Gestion de piles fifo (premier entré, premier sorti) =====
+===== Gestion de piles FIFO (premier entré, premier sorti) =====
-Une pile fifo est assimilable à une file d'attente ou une pile de dossier à traiter:
+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.
@@ Ligne 109: / Ligne 150: @@
 class PileFifo(object):
-    """PileFifo(object): pile fifo (first in first out): on peut dépiler le premier élément qui a été empilé (=le plus ancien dans la pile)"""
+    """PileFifo(object): pile FIFO: objet de type file d'attente => on depile l'élément le plus ancien empilé"""
-    def __init__(self):
-        self._pile=[]
+    def __init__(self,maxpile=None):
+        self.pile=[]
-    def empile(self,element):
+        self.maxpile = maxpile
-        self._pile.insert(0,element)
+    def empile(self,element,idx=0):
-    def depile(self):
+        if (self.maxpile!=None) and (len(self.pile)==self.maxpile):
-        return self._pile.pop()
+            raise ValueError ("erreur: tentative d'empiler dans une pile pleine")
+        self.pile.insert(idx,element)
-    def element(self,i=-1):
-        return self._pile[i]
+    def depile(self,idx=-1):
+        if len(self.pile)==0:
-    def pile(self,imin=0,imax=None):
+            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)
+            imax=len(self.pile)
-        return list(self._pile[imin:imax])
+        if imin<0 or imax>len(self.pile) or imin>=imax:
+            raise ValueError ("erreur: mauvais indice(s) pour l'extraction par copiepile")
-    def estvide(self):
+        return list(self.pile[imin:imax])
-        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):
-        return len(self._pile)
+        return len(self.pile)
 # exemples d'utilisation:
 x=PileFifo()
-print x.pile()  # affiche []
+print x.copiepile()  # affiche []
-print x.estvide()  # affiche True
+print x.pilevide()  # affiche True
 x.empile('A')
 x.empile(5)
 x.empile(['toto','titi','tata'])
-print x.pile()  # affiche [['toto', 'titi', 'tata'], 5, 'A']
+print x.copiepile()  # affiche [['toto', 'titi', 'tata'], 5, 'A']
 z=x.depile()
 print z  # affiche A
-print x.pile()  # affiche [['toto', 'titi', 'tata'], 5]
+print x.copiepile()  # affiche [['toto', 'titi', 'tata'], 5]
 print x.taille()  # affiche 2
 print x.element()  # affiche 5
@@ Ligne 151: / Ligne 207: @@
 __**Commentaires sur ce code:**__
-**A l'initialisation, par exemple x=PileFifo() :**
+**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.
+  * 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):**
+**x.empile(element,idx=None):**
-  * insère l'élément en dessous de la pile
+  * ajoute l'élément en dessous de la pile
-  * on peut empiler n'importe quel objet Python: nombre, chaîne, liste, tuple, dictionnaire, ... y compris une autre 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
-  * 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.
+  * 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):**
-  * retire de la pile l'élément qui est au dessus de la pile (=le plus ancien) et le renvoie
+  * 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())
-  * une tentative de dépiler une pile vide produit une exception "IndexError" qu'il faudra gérer dans le code utilisateur
+  * 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() ou x.element(i):**
+**x.element(idx=-1):**
-  * sans argument, renvoie le dernier élément de la pile (le candidat à être dépilé) sans le dépiler
+  * sans paramètre, 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()%%
+  * avec un index comme paramètre, renvoie l'élément d'index idx.
-  * si l'index i n'est pas valide, déclenche une exception "IndexError" qu'il faudra gérer dans le code utilisateur
+  * si l'index i n'est pas valide, déclenche une exception
-**x.pile() ou x.pile(imin,imax):**
+**x.copiepile() ou x.copiepile(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 une copie de la pile complète sous forme d'une liste.
-  * 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):
+  * 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):
-    * attention: les index d'une liste de longueur lg vont de 0 à lg-1
+    * 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 (par d'argument simple après un argument nommé)
+    * 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 (hors de %%-x.taille() <= i < +x.taille()%%), génère une exception "IndexError" qu'il faudra gérer dans le code utilisateur
+    * 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.
+**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!
 <html>

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page