Discussion :

[john491]

Salut;
Comment declare-t-on une pile et une file sous python
comment empiler et depiler ? enfiler et defiler ?
merci d'avance

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

[tyrtamos]

Bonjour,

Simulation d'une pile avec une liste:

Déclaration:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

pile=[]

Empilage de 'toto':

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

pile.append('toto')

Dépilage:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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

[john491]

merci tyrtamos de ta reponse

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)

[john491]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

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

Sélectionner tout - Visualiser dans une fenêtre à part

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

[john491]

on peut aussi definir les deux classes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[john491]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
class Truc():
    p = None
    q = None

A partir de là, si

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

f = Truc()

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Tyrtamos

[john491]

merci de ta reponse tyrtamos
voici le code complet :


contenu du fichier ListesChainees

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 .

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

Sélectionner tout - Visualiser dans une fenêtre à part

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

[pacificator]

Bonjour,

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

[dividee]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[john491]

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 )

[john491]

Bonjour,

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

merci !

[john491]

Ca ne devrait pas plutôt être quelque chose comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[dividee]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[john491]

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