Différences

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

--- gestion_piles [2008/04/18 17:51]
tyrtamos
+++ gestion_piles [2008/05/02 07:32]
tyrtamos
@@ Ligne 1: / Ligne 1: @@
 ====== 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) =====
@@ 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)
-# exemple d'utilisation:
+# 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 60: / Ligne 96: @@
 **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 le dernier élément de la pile sans le dépiler
+  * 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
@@ Ligne 82: / Ligne 121: @@
     * 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 (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
@@ Ligne 95: / Ligne 134: @@
 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 au **dessous** de la pile.
+  * 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).
+  * 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é:
@@ Ligne 106: / Ligne 145: @@
 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)
-# exemple d'utilisation:
+# 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 183: / Ligne 237: @@
   * renvoie le nombre d'éléments de la pile
+<html>
+<head>
+<style type="text/css">
+<!--
+body {background-image:url(fondcorps.jpg);}
+-->
+</style>
+</head>
+<body>
+</body>
+</html>

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page