pile et file sous python

Version imprimable

15/04/2008, 14h23
john491

pile et file sous python

Salut;
Comment declare-t-on une pile et une file sous python
comment empiler et depiler ? enfiler et defiler ?
merci d'avance
15/04/2008, 14h37
dividee

Il n'y a pas de type pile ou file à proprement parler, mais il est facile d'utiliser une liste pour cela.
Par exemple:
pile = [1,2,3]
Empiler x => pile.append(x)
Dépiler => pile.pop()

file = [1,2,3]
Enfiler x => file.append(x)
Défiler => file.pop(0)

Mais il y a d'autres façons de faire.

Il existe bien une classe Queue dans le module du même nom, mais elle sert plutôt à communiquer entre threads...
15/04/2008, 14h41
tyrtamos
Bonjour,

Simulation d'une pile avec une liste:

Déclaration:

Code:

pile=[]

Empilage de 'toto':

Code:

pile.append('toto')

Dépilage:
Code:

1 2 3 x=pile[-1] del pile[-1]
Ça, c'était une pile lifo, pour une pile fifo, il suffit de retirer le 1er élément (indice 0):
Code:

1 2 3 x=pile[0] del pile[0]
Je ne sais pas ce que tu entends par "file": tu pourrais préciser?

Tyrtamos

[edit]: encore grillé... mais c'est lui qui a raison: pop est mieux
15/04/2008, 14h42
john491

merci de ta reponse dividee
dans ton exemple , il n'y a pas de difference entre une pile et une file ?
et aussi comment faire pour respecter les priorités ?
merci
Edit: je pense avoir compris :
c'est dans le depilage :
l.pop() pour une pile
et l.pop(0) pour une file
15/04/2008, 14h44
john491

merci tyrtamos de ta reponse

Citation:

Envoyé par tyrtamos

Bonjour,

Je ne sais pas ce que tu entends par "file": tu pourrais préciser?

Tyrtamos

c'est ce que tu appelles " pile fifo "( comme une file d'attente)

peut on utiliser des listes chainnées ?
j'ai defini la classe suivante :
Code:

1 2 3 4 5 6 7 class Noeud: def __init__(self,valeur,suivant): self.val=valeur self.suiv=suivant def __repr__(self): return "Noeud de Valeur "+str(self.val)
avec ca on peut peut etre creer des files et des piles ?

15/04/2008, 15h11
tyrtamos

Une idée de solution à adapter:

Dans une liste python, chaque élément peut être n'importe quoi, et pourquoi pas une liste.

Si l'élement est une liste, elle peut contenir l'indice de l'élément suivant en plus d'une valeur. On doit donc pouvoir chainer ces sous-listes dans un ordre différent de la liste de base.

Exemple:

Code:

L=[[3,'titi'],[0,'toto'],[None,'tutu'],[2,'tata']]

Dans cet exemple simpliste, le 1er élément est L[1] (il faut le mémoriser dans une autre variable), qui renvoie à L[0], puis à L[3], puis enfin à L[2] qui est le dernier élément à qui on a attribué un suivant "None" qui peut être testé.

Mais, bon, gérer une pile avec cette liste chainée ne sera pas facile à coder...

Tyrtamos

on peut aussi definir les deux classes:

Code:

1
2
3
4
5
 
class noeudPile:
     def __init__(self,arbre,suivant=None)
           self.arbre=arbre
           self.suiv=suivant

et pour les arbres binaires :

Code:

1
2
3
4
5
6
7
8
 
class noeudArbre:
    def __init__(self,valeur,gauche,droite):
        self.val=valeur
        self.filsgauche=gauche
        self.filsdroit=droite
    def __repr__(self):
        return "Noeud de valeur "+str(self.val)

maintenant le plus dur est de definir les operations sur ces nouveaux objets

a suivre ...

Salut;
j'ai finalement pu implementer ces structures sous python , neanmoins j'ai un petit probleme .
voila ce que j'ai fait (en m'inspirant de quelques algo d'un excellent livre !)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
from Piles import *
 
#Soit E un ensemble dynamique.On souhaite representer une file f sur E
#et implementer les operations Enfiler et Defiler a partir de 2 piles
#p et q sur E et des operations d'empilement et de depilement.La file f
#est representee par la paire de piles {p,q}.
#pour enfiler un element e dans f , on l'empile dans p.
#pour defiler f , on considere 2 cas :
#1)si q n'est pas vide , alors on depile q.
#2)sinon , on "vide" p dans q en depilant un a un les elements de p et en
#les empilant au fur et a mesure dans q . Le dernier element depilé n'est
#cependant pas empilé dans q car il s'agit de l'element a supprimer dans f.
 
class File:#"file" avec f minuscule est un mot reservé !
    def __init__(self,pile1,pile2):
        self.p=pile1
        self.q=pile2
 
def afficheFile(f):
    affiche(f.p)
    affiche(f.q)
def enfiler(f,x):
    return File(empiler(f.p,x),f.q)
 
def defiler(f):
    if f.q!=None:
        return depiler(f.q)
    else:
        while f.p!=None:
            z=sommet(f.p)
            f.p=depiler(f.p)
            if f.p!=None:
                f.q=empiler(f.q,z)

les fonctions empiler , depiler et affiche sont des fonctions definies sur les piles

Mon probleme est le suivant :
je souhaite que la fonction defiler(f) me retourne une file !
si je fais :

Code:

1
2
3
4
5
6
7
8
9
10
11
def defiler(f):
    if f.q!=None:
        return depiler(f.q)
    else:
        while f.p!=None:
            z=sommet(f.p)
            f.p=depiler(f.p)
            if f.p!=None:
                f.q=empiler(f.q,z)
    return File(f.p,f.q)

j'obtiens le message d'erreur suivant :

Code:

1
2
3
4
5
6
7
 
Traceback (most recent call last):
  File "/.../Files.py", line 50, in -toplevel-
    afficheFile(s)
  File "/.../Files.py", line 20, in afficheFile
    affiche(f.p)
AttributeError: Noeud instance has no attribute 'p'

pouvez-vous me debloquer svp ?
merci par avance

16/04/2008, 11h22
tyrtamos
Bonjour,

C'est difficile de t'aider, parce qu'on a pas tout ton code.

Mais, a priori, le message d'erreur: "AttributeError: Noeud instance has no attribute 'p'" suggère que f n'est pas reconnu comme un objet ayant un attribut p.

Peut-être suffit-il de créer cet objet comme une classe:
Code:

1 2 3 class Truc(): p = None q = None
A partir de là, si

Code:

f = Truc()

alors, f.p et f.q seront reconnus comme pouvant porter des valeurs. Par exemple:
Code:

1 2 f.p='toto' print f.p # affiche toto
Tyrtamos

merci de ta reponse tyrtamos
voici le code complet :

contenu du fichier ListesChainees

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
class Noeud:
    def __init__(self,valeur,suivant):
        self.val=valeur
        self.suiv=suivant
    def __repr__(self):
        return "Noeud de Valeur "+str(self.val)
 
 
def copieRec(l):
    if l==None:
        return None
    else:
        res=copieRec(l.suiv)
        return Noeud(l.val,res)
 
def affiche(l):#ou parcours
    if l!=None:
        print l.val
        affiche(l.suiv)
 
def afficheBis(l):
    if l!=None:
        afficheBis(l.suiv)
        print l.val
 
def parcoursIteratif(l):
    #cour est une variable qui effectue le parcours
    cour=copieRec(l)
    while cour!=None:
        print cour.val
        cour=cour.suiv
 
 
def parcoursIter2(l):
    #on veut parcourir l jusqu'a l'avant dernier noeud
    #donc l ne doit pas etre vide ni reduite a un seul noeud
    #on a une variable de parcours des noeuds cour et une variable
    #de test d'arret test_courant
    if l==None or l.suiv==None:
        return "Erreur : l doit avoir au moins deux noeuds non vides !"
    else:
        cour=copieRec(l)
        test_courant=cour.suiv
        while test_courant!=None:
            print cour.val
            cour=cour.suiv
            test_courant=test_courant.suiv
 
 
def somme(l):
    #somme des elements d'une liste simplement chainee
    if l==None:
        return 0
    else:
        return l.val+somme(l.suiv)
 
 
 
def produit(l):
    #produit des elements d'une liste simplement chainee
    if l==None:
        return 1
    else:
        return l.val*produit(l.suiv)
 
 
def recherche(l,x):
    #on renvoie l'adresse du premier noeud de la liste l
    #qui contient la valeur x s'il y en a , et None sinon
    if l==None:
        return None
    elif l.val==x:
        return l
    else:
        return recherche(l.suiv,x)
 
def inserFin(l,x):
    if l==None:
        return Noeud(x,None)
    else:
        l.suiv=inserFin(l.suiv,x)
        return l
 
def inserRec(l,x):
    #insertion de x dans l croissante de facon recursive
    if l==None:
        return Noeud(x,None)
    elif x<l.val:
        #insertion en tete
        return Noeud(x,l)
    else:
        l.suiv=inserRec(l.suiv,x)
        return l #l=la variable du parcours recursif
def inserIter(l,x):
    if l==None:
        return Noeud(x,None)
    elif x<l.val:
        #insertion en tete
        return Noeud(x,l)
    else:
        #mise en place d'une variable de parcours insere_apres
        #apres laquelle on inserera
        #mise en place d'une varaible de test ref_test
        insere_apres=l
        ref_test=l.suiv
        fini=(ref_test==None)
        while not fini:
            if x>ref_test.val:
                #on avance
                insere_apres=insere_apres.suiv
                ref_test=ref_test.suiv
                if ref_test==None:
                    fini=True
            else:
                #on vient de depasser l'endroit ou inserer
                fini=True
        #on fait l'insertion
        insere_apres.suiv=Noeud(x,ref_test)
        return l
 
 
 
def fusionIter(l,m):
    #fusion de 2 listes croissantes sans valeur commune
    vl=l
    vm=m
    res=None
    #aucune liste epuisee
    while vl!=None and vm!=None:
        if vl.val<vm.val:
            res=Noeud(vl.val,res)
            #on avance dans l
            vl=vl.suiv
        else:
            res=Noeud(vm.val,res)
            #on avance dans m
            vm=vm.suiv
    #une au moins des 2 listes est epuisee
    while vm!=None or vl!=None:
        if vl!=None:
            res=Noeud(vl.val,res) 
            #on avance
            vl=vl.suiv
        else:
            res=Noeud(vm.val,res)
            #on avance
            vm=vm.suiv
    return res
 
 
def fusionRec(l,m):
    #on parcours les 2 istes de facon recursive
    #les tests d'arret d'abord
    if l==None and m==None:
        return None
    elif l!=None and m==None:
        return Noeud(l.val,fusionRec(l.suiv,m))
    elif l==None and m!=None:
        return Noeud(m.val,fusionRec(l,m.suiv))
    else:#les 2 listes sont non vides
        if l.val>m.val:
            return Noeud(m.val,fusionRec(l,m.suiv))
        else:
            return Noeud(l.val,fusionRec(l.suiv,m))

celui du fichier Piles

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
from ListesChainees import *
 
def acces(l,k):#acces au k-ieme elt de la liste chainee l
    if k==0:
        return l
    else:
        return acces(l.suiv,k-1)
 
def sommet(p):
    return p.val
 
def empiler(p,x):
    return Noeud(x,p)
 
def depiler(p):
    if p==None:
        return None
    else:
        return p.suiv
 
 
 
 
 
#l=Noeud(1,None)
#for i in range(1,10):
#    inserRec(l,2**i)
#m=Noeud(3,None)
#for i in range(2,9):
#    inserRec(m,3**i)
 
#d=fusionRec(l,m)
#affiche(l)

voila pour ce qui est du code
sinon, j'ai pas reussi a surmenter le pb
toute suggestion sera la bienvenue
merci .

16/04/2008, 15h09
tyrtamos
Curieusement, je ne trouve pas d'erreur à l'exécution!

J'ai pris le code de ton dernier message, j'ai tout mis dans la même page (en neutralisant "from ListesChainees import *", et j'ai dé-commenté les dernières lignes. Cela donne:
Code:

1 2 3 4 5 6 7 8 9 10 1 2 4 8 16 32 64 128 256 512
Etait-ce le résultat attendu?

Tyrtamos
16/04/2008, 16h52
pacificator

Bonjour,

Tu peux aussi regarder du côté des deques.

Citation:
Envoyé par john491
Mon probleme est le suivant :
je souhaite que la fonction defiler(f) me retourne une file !
si je fais :
Code:

1 2 3 4 5 6 7 8 9 10 11 def defiler(f): if f.q!=None: return depiler(f.q) else: while f.p!=None: z=sommet(f.p) f.p=depiler(f.p) if f.p!=None: f.q=empiler(f.q,z) return File(f.p,f.q)
Ca ne devrait pas plutôt être quelque chose comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 def defiler(f): if f.q!=None: return File(f.p,depiler(f.q)) else: while f.p!=None: z=sommet(f.p) f.p=depiler(f.p) if f.p!=None: f.q=empiler(f.q,z) return File(f.p,f.q)
?

Sinon une remarque plus générale: ton implémentation ressemble à une file persistante (tu crées une nouvelle file à chaque modification) mais n'en est pas une (tu modifies malgré tout les objets File). De deux choses l'une: soit tu ne cherches pas à implémenter une file persistante, et dans ce cas ta structure de données est inutilement compliquée, soit tu cherches à la faire, mais dans ce cas tu ne devrais jamais modifier l'état de tes objets...

16/04/2008, 21h19
john491

Citation:

Envoyé par tyrtamos

Curieusement, je ne trouve pas d'erreur à l'exécution!
Tyrtamos

seule la fonction defiler me pose pb , les autres marchent tres bien (enfin je crois) (en l'occurence , celles que tu as testées :P )
16/04/2008, 21h23
john491

Citation:

Envoyé par pacificator

Bonjour,

Tu peux aussi regarder du côté des deques.

merci ! :P

Citation:
Envoyé par dividee
Ca ne devrait pas plutôt être quelque chose comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 def defiler(f): if f.q!=None: return File(f.p,depiler(f.q)) else: while f.p!=None: z=sommet(f.p) f.p=depiler(f.p) if f.p!=None: f.q=empiler(f.q,z) return File(f.p,f.q)
?
merci ca marche tres bien :king:

Citation:

Envoyé par dividee

Sinon une remarque plus générale: ton implémentation ressemble à une file persistante (tu crées une nouvelle file à chaque modification) mais n'en est pas une (tu modifies malgré tout les objets File). De deux choses l'une: soit tu ne cherches pas à implémenter une file persistante, et dans ce cas ta structure de données est inutilement compliquée, soit tu cherches à la faire, mais dans ce cas tu ne devrais jamais modifier l'état de tes objets...

la , je me sens un peu perdu ! ( je vois rien de compliqué dans mon code , mais si tu as quelque chose de plus simple , je suis preneur ! )
merci

Par "inutilement compliquée", je voulais dire qu'il est beaucoup plus simple d'utiliser une liste comme on te l'avait suggéré dans les premières réponses:
En style OO, sans doute préférable en Python:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 class File: def __init__(self): self._file = [] def empiler(self, x): self._file.append(x) def tete(self): return self._file[0] def depiler(self): self._file.pop(0)
Ou, si tu y tiens vraiment, en style "type de donnée abstrait":
Code:

1 2 3 4 5 6 7 8 File = list # c'est pas très propre car les méthodes de list seront visibles, # mais c'est l'idée. def enfiler(f,x): f.append(x) def defiler(f): f.pop(0) def tete(f): return f[0]
Remarque qu'ici enfiler et defiler ne renvoient pas de nouvelle file, mais modifie la file existante.
L'intérêt de renvoyer une nouvelle file à chaque fois, comme tu le fais, serait de pouvoir continuer à utiliser les anciennes sans qu'elles soient modifiées par les opérations suivantes. Cela peut être utile dans certains cas, par exemple cela permet de partir de la même file dans plusieurs thread différents sans avoir à craindre qu'un thread modifie une file utilisée par un autre thread (vu qu'une file n'est jamais modifiée, on en retourne toujours une nouvelle).
Le problème, c'est que ça ne fonctionne pas avec ton implémentation:
Code:

1 2 3 4 5 6 7 8 9 >>> f1 = File(None, None) >>> f2 = enfiler(f1,1) >>> f2.p,f2.q (Noeud de Valeur 1, None) >>> f3 = defiler(f2) >>> f3.p, f3.q (None, None) >>> f2.p, f2.q (None, None) <-- le problème est ici; f2 est modifié
Une autre remarque, au passage: ton constructeur de File expose son implémentation; pourquoi devoir créer un file en lui passant deux piles ? Le programmeur qui utilise ta file ne devrait pas avoir à se préoccuper cela.

Il suffit de faire en sorte que defiler ne modifier pas son argument pour obtenir une file persistante:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def defiler(f): if f.q!=None: return File(f.p,depiler(f.q)) else: fp = f.p fq = None while fp != None: z=sommet(fp) fp=depiler(fp) if fp!=None: fq=empiler(fq,z) return File(fp,fq)
Maintenant:
Code:

1 2 3 4 5 6 7 8 9 >>> f1 = File(None, None) >>> f2 = enfiler(f1,1) >>> f2.p,f2.q (Noeud de Valeur 1, None) >>> f3 = defiler(f2) >>> f3.p, f3.q (None, None) >>> f2.p, f2.q (Noeud de Valeur 1, None) <-- ok

20/04/2008, 11h36
john491

merci dividee
merci également a tous ceux qui ont participé :king:
à +