Différences

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

--- gestion_piles [2008/04/18 13:45]
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:
-  * quand on ajoute un élément (=empile), c'est sur le dessus de la pile qu'on le met.
+  * on peut empiler n'importe quel objet Python (y compris une autre pile!), et pas simplement les types de base,
-  * quand on retire un élément (=dépile), c'est l'élément du dessus de la pile qu'on retire (=le dernier arrivé).
+  * on peut fixer une taille maxi,
-Voilà le code proposé:
+  * on peut insérer ou retirer un élément à n'importe quel niveau de la pile,
-<code python>
+  * on peut lire un élément de n'importe quel niveau de la pile sans le retirer de la pile,
-#!/usr/bin/python
-# -*- coding: utf-8 -*-
-# pile lifo (last in first out): on dépile le dernier élément empilé
+  * on peut obtenir une copie de tout ou partie de la pile,
-class Pile(object):
-    def __init__(self):
-        self._pile=[]
-    def empile(self,element):
+  * 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é.
-        self._pile.append(element)
-    def depile(self):
-        return self._pile.pop()
-    def element(self,i=-1):
+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.
-        return self._pile[i]
-    def pile(self,imin=0,imax=None):
+===== Gestion de piles LIFO (dernier entré, premier sorti) =====
-        if imax=None:
-            imax=len(self._pile)
-        return list(self._pile[imin:imax])
-    def estvide(self):
+Une pile LIFO est assimilable à un tas:
-        return len(self._pile)==0
+  * 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é:
+<code python>
+#!/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)
+        return len(self.pile)
-# exemple d'utilisation:
+# exemples d'utilisation:
-x=Pile()
+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=Pile() :**
+**x=PileLifo(maxpile=None):**
-  * la pile créée appartient à l'instance de classe, c'est à dire que x=Pile() et y=Pile() vont créer 2 piles indépendantes.
+  * 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):**
+**x.empile(element,idx=None):**
-  * on peut empiler n'importe quel objet Python: nombre, chaîne, liste, tuple, dictionnaire, ...
+  * ajoute l'élément en dessus 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.
+  * 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() ou z=x.depile() :**
+**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())
-  * 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 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
-===== Gestion de piles fifo (premier entré, premier sorti) =====
+===== Gestion de piles FIFO (premier entré, premier sorti) =====
-Une pile lifo est assimilable à file d'attente:
+Une pile FIFO est assimilable à une file d'attente ou une pile de dossier à traiter:
-  * quand on ajoute un élément (=empile), c'est sur le dessus de la pile qu'on le met.
+  * quand on ajoute un élément (=empile), on l'ajoute en **dessous** de la pile.
-  * quand on retire un élément (=dépile), c'est l'élément du **dessous** de la pile qu'on retire (=le plus ancien arrivé).
+  * 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é:
+<code python>
+#!/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
+</code>
+\\
+__**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 i 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!
+<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