Aller au contenu

File avec deux piles⚓︎

On choisit d'implémenter une file à l'aide d'un couple [p1,p2] où p1 et p2 sont des piles. Ainsi file[0] et file[1] sont respectivement les piles p1 et p2.

Pour enfiler un nouvel élément valeur dans file, on l'empile dans p1.

enfiler

Pour défiler file, deux cas se présentent :

  • La pile p2 n'est pas vide : on dépile p2.

enfiler

  • La pile p2 est vide : on dépile les éléments de p1 en les empilant dans p2 jusqu'à ce que p1 soit vide, puis on dépile p2.

enfiler

La structure de pile est utilisable au travers de leur interface constituée des fonctions suivantes :

  • cree_pile_vider : renvoie une pile vide
  • depiler : prend en paramètre une pile et renvoie une nouvelle pile où on a supprimé l'ancien sommet
  • empiler : prend un element quelconque et une pile et renvoie une nouvelle pile où element est le sommet.
  • est_pile_vide : prend en paramètre une pile et renvoie True si la pile est vide
  • lire_sommet : prend en paramètre une pile et renvoie la valeur stockée au sommet d'une pile NON VIDE
Python Console Session
1
2
3
4
5
6
7
8
>>> ma_pile = creer_pile_vide()
>>> est_pile_vide(ma_pile)
True
>>> empiler(5, ma_pile)
>>> empiler(4, ma_pile)
>>> lire_sommet(ma_pile)
4
>>> depiler(ma_pile)

A partir des opérations sur les piles fournis dans le module, écrire en Python les fonctions suivantes :

  • une fonction creer_file_vide() qui renvoie une file vide de tout élément.
  • une fonction est_vide(file) qui prend en argument une file et qui renvoie True si la file est vide, False sinon.
  • une fonction enfiler(file, valeur) qui prend en arguments une file et un élément valeur et qui ajoute valeur en queue de la file.
  • une fonction defiler(file) qui prend en argument une file et qui renvoie l'élément en tête de la file en le retirant.

On doit utiliser exclusivement les fonctions fournies. Aucune connaissance de la manière dont sont stockées les valeurs de la pile n'est nécessaire.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013oPf 8lkg5:j,bry2a1Ahé3tvwT=u6e[(Sàn9]_s-c)7imR./4Dp0d050#0E0x0r0S0g0N0e0P0g0r0N0N0B010x0S0Z010406050N0C0T0T0r0o0p040H0b0g0C0_0b0J050W101214160~0Z04051m1f1p0W1m0~0#0S0y0.0:0=0@0:0J0i0C0r0i0E0O0Z0p0x0u1d0e0u0S0i0u0g1R0u0x0|050)0n0g0E1y0;0?011Q1S1U1S0x1!1$1Y0x0o1n1M0.190N0Z0r0J0@0q011(1A010d0+0E0J0r0T0E1Y1}1 241*271$2a2c0|0a0e0c0o0b0Z0b0N0S1c0J0e0%1{0o0o0E0P2x1f2f0J1n0W1M2K1@1_1^1Z0#2h1B0S0J292u1Y1v1x0/1)2U2W0J0b2!1Y0Z2D1n2I2K2;0 1~2y2$252*0o130g1Y0r1P2D0d0@030M0M0P2+0E1U2)0b0O0s3f0|0e0s1f0r2=2^0}2@2g2`1*2|2~30320E340136383a3c2X3f0O22040e0q3l3n1 3p2I2T013u0r2 1n310u333537390%3E2*3G0w3i0w3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0X3i0X3.1g3:3q2_1z3t0b2}3U3w3Y3y3!3C3%403)3g0j3i0j462;3;2^3R3^4g3|3B3$3b4m3e3g0D3i0D4s483=4b3@4d3v3W3x3z4A3 3d3G0R3i0R4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0f3i0f4!2J4$4a2%4)4e3_3{4i3}4k4C4;0O0K3i0K4_3P4v3?4~4P3`4R4j4B3(4E3f0!0|0s0!5b4{4w4*505i535k4D3G0s0s5p3k0W3m3/4#495u4 4y524T4:413f3I0s3L5G3N4`5K5e4x4,4z4/555R0s3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560s4G5-4I6c4t5:626h5$5O5(673g0s4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560q5o046;5/6f4c6,645^5Q6Z0q5D6?5F5H6d6)4%6U5g6|5y6Y5m0q3I7e6^6*6`795x5P5)6 5,0q3-6(5c776+7k5@7b6~7d5{0q5}746r6_4N6{7l6x6M3H690q6b7E3o1q2/1f2!2N0#1_2S5e4B2Z1w1n2.0E2:7R751n4B7+2g0S0#0@372I5B3w7=7@6/5*232l0E7}6k7 2K5H7G010h0|0%0d5 7:4|250z3i8e6s2{0d0|0P2D0E0o0M2j0E0M0y7=0E8k880{040G0Q0k8e0~7-5K7|017^2^3G3I5h8L7K6:802b828M7~6 1Y5~888i3J0e8*8A7i0@0N0#0|008=0U290y0b0S1%0C2W0e8u0e8x0%8=008H8,7;7?8Y7_3g5,8R998T5R3+0e81837c3*8#3m8*8+888a042D0x0C0o1e7-0e8l1*8C0F978g3t8o8q8s0Z288w8y9G3R8C8E0m8e9B880J9J0E8r0M9M1$9O0%9Q5e9S0Q0L968J3Q8S0M9b0O5{9e9l7z3G439j8W9|7n5m9`5W8I2?9=9f9@8O4o7{aa846Z4pa02ca26y0O693.9s8b3y9+4(8(9B9;8-3S8n040E0N0x8t9N928zax7u9D0|0Gat620|8uaO258C8F9:a84v9?9^6n9{8Yag5m4Gaj8X9g6Za#8$ayav9qaS1*8/8;8?8^8`1%0A0o0C1%2v0e0:8 280eaC0x918y94aW7Ra97}9^6Ba$a-5m4Xa+al7Lbj5W9q9Way9t9v9x9z2;buaK3@0|b99$aG9PaJ9H0@9Sa@bD04aRbJ9R0|9FbR5e0T0S0|5rbV4(8C0L0Q9V9C0@0b8(1 0#b*9XbEaDbG9(aHbN01bMb#aPbP28b{9Eb{bX5pc20|b(be3O8Kaa9^6Obk8Z5m4?boa%9m4=9o3pbRaZac57aebp5658ckbl3G6#apbvar8db~8h8jcG3taA298u0oc78Db{9Yc01$cP9U9Ab+3S0|0y3U0E9xcPaV7-a7bfaYcdcs5qcucl9}6z5ocych5B6=cCbC01a=8+cJ8.8:04940t0l0b1b1%0g000v0g0v2c0Jbac#1$9x0e0Ib4318ubdc+9Qcr1 5B71cga(dy8Vakc?a3dC868)9raycSbQaXc c3d301c504b!dObKb|c8b;ay0b0|0Bd!c cS0Zb{d$040VcRbE0T9%8rcPaNdRcSdlc%cOdR8CcWbAcYdMc1e0bTc4bYdUcPc9ducqc/dx6z8Q319?dBeidDa,c{endIc,cbbg9ac:9dekafcm3f9i9kdFam5+cocY9t8cb{avcRaA8c28d dWbScQd{aQe6eT9,0|c*6refbhc:9`ezcv5`eoe-6Z0sa587a;3ia?dRa_d68=ca2Jcce)eh3faoe,eF7L0saieEcz6zaoa:c e|bt0Y0v908}0edfdh29ba2Ab5dN48e(ewf36mc=fc3fa*fbeqfCeI88fh9q8@0J8_8{0.0(fndgdi0xe 8f0edw0J5Bbjf6fB6Ae/f76lbre@fgd5btdte%eTfY5Bcff$fF0scjfEem3fcfbsa?aq040ScFe3b=04d,dRd.d:eWaBb@d@9)aIeZb$aMd;cTgkc-dPe8dRdT5Fgl4}b%e$fvf?egfZ6zcBf`f 0scxf~eBgJcobtbteJ0|0z1QcUcX88b-0|2*fUgWdL0|gbgx25gdgobFgib`e7eVg*9IgpcPbUg?0@dTdVgrdXgz8GeegCf2gE3Hc}gHeB6;f)fBhbdIgPhgbBdXd|c$c(g$c d.d(hnhjg(d-0|geg{cZ041U2D9@0b120(d_gofueuaydQhxg}ecb)h3g fXgD8Pdzh9c@3H5Dc`f 70gOhhgQg9hIf08BgthMeag~hJgs049/hr3Rhpd)hsgahud/go0%d@eShRe!g=i55;eXgVhxhLi84}hNg;edf=hRf@3g7efAfFinh!ha8Qg2h(dKd*iagqh=h0h.ie25gvech|h`d%iH5!htgchvg-d?eRhGgfd}hmic0|e23ohi4wiyg_e9c6ihhPijiAhSh58Peyi.f*5R7qhcip9diui!iL040rc#djiK4(h{h_i~g)iD1*g,gfhA8v0NhD2cg#iWi7i-i~h+fWi6g`j9g|eagwjrdYh@i+gBikhTime+i=hd9 gLhX7Ch%iwh}jncYidjl4(iFihj34}j5g8g%h~iNi0gfi2iRg;d`hxe5ibjvjPh,ayjSjjiijzi-il7Mioh#faa1i?6 fe9pg3cD9u0(byjU2{0|j01 jij^f00W7/7S7*7U7%1f0x7Xkn2Q2L0r1#kk0W7V8I0%0)0+0N04.