Structures de données linéaires - les piles

I. Introduction⚓︎

Il faut se représenter une pile comme... une pile de livres ! Seul le livre disposé sur le dessus est accessible : l'ajout et le retrait d'un livre ne peut donc se faire que sur le sommet de la pile.

LIFO

On dit que les piles sont en mode LIFO (Last In, First Out qui signifie « dernier entré, premier sorti »).

pile LIFO

On ajoute des livres sur la pile, et on les récupère en commençant par le dernier ajouté

Usage courant d'une pile

😊 Les piles sont très utilisées en informatique, en voici quelques usages caractéristiques :

Les algorithmes récursifs utilisent une pile d'appel pour mémoriser les contextes d'exécution de chaque appel.
La fonction «Annuler la frappe» (en anglais «Undo») d'un traitement de texte mémorise les modifications apportées au texte dans une pile.
Comme nous le verrons plus tard dans l'année, on peut aussi utiliser une pile pour parcourir (en profondeur) un graphe et mémoriser les sommets visités.
La vérification du bon parenthésage d'une expression peut également se faire à l'aide d'une pile.

Les fonctions primitives pour les PILES sont les suivantes

création d'une pile vide (oublié sur l'illustration),
tester si une pile est vide,
empiler,
dépiler.

😊 Et rien de plus ... Pile Gilles

Image crée par Gilles Lassus

Un jeu sérieux

Pour comprendre le principe, vous pouvez jouer à ce jeu :

OCTAVES FLUSH

Représentation possible d'une pile et exemple

🌵🌵 Il n'existe pas une façon "universelle" de représenter les piles. dans cet exemple le sommet sera indiqué avec le symbole > et le fond avec le symbole ]

Une pile contenant les éléments 'a', 'b' et 'c' ('a' étant le sommet et donc 'c' le fond de la pile) sera représentée ici de la façon suivante :

>'a', 'b', 'c']

Exemple : On considère la pile P : >'a', 'b', 'c']. Voici comment la manipuler :

Opération	Contenu de la pile
empiler(P, 'e')	`>'e', 'a', 'b', 'c']`
depiler(P)	`>'a', 'b', 'c']`
depiler(P)	`>'b', 'c']`
depiler(P)	`>'c']`
empiler(P, 'm')	`>'m', 'c']`

II. Une implémentation possible des piles⚓︎

Mon info

On donne ci-dessous une possible implémentation de ces fonctions primaires, en utilisant le vocabulaire de la programmation orientée objet que nous avons déjà abordée.

Il existe bien d'autres possibilités pour implémenter ces fonctions primaires.

Dans toute la suite les piles seront affichées entre crochets, comme des list python. Le sommet de la pile est l'élément écrit le plus à droite. Ainsi, si l'on part d'une pile vide, et que l'on empile successivement les entiers 1, puis 2, puis 3, on obtiendra une pile qui s'affichera de la façon suivante : [1, 2, 3]. Le sommet de cette pile est l'entier 3.

La classe Pile

Exécuter absolument le code ci-dessous pour pouvoir continuer.

Tester ci-dessous ces primitives

Imaginez vos propres tests

A vous de jouer

Ecrire ci dessous les instructions qui permettent d'obtenir successivement les affichages suivants :

[12] <- sommet
[12, 14] <- sommet
[12, 14, 8] <- sommet
[12, 14] <- sommet
[12] <- sommet
[] <- sommet

Solution

Python

pile_1 = Pile()
pile_1.empiler(12)
print(pile_1)
pile_1.empiler(14)
print(pile_1)
pile_1.empiler(8)
print(pile_1)
pile_1.depiler()
print(pile_1)
pile_1.depiler()
print(pile_1)
pile_1.depiler()
print(pile_1)

La taille d'une pile

Alice désire écrire une fonction, qui doit retourner la taille de la pile.
Attention, une fois que sa taille a été déterminée, la pile ne doit pas avoir été modifiée...
Elle propose le code suivant. L'exécuter absolument

Test du code d'Alice

Tester

Quel est le problème ?

Pourquoi cette solution ne convient-elle pas ?

Solution

On a bien déterminé la taille de la pile, mais on l'a détruite 😰

Une nouvelle fonction

Ecrire ci-dessous une fonction taille qui remédie à ce problème

Astuce à lire en désespoir de cause ...

Vous pouvez utiliser une deuxième pile ...

Évaluations restantes : 5/5

.128013/=d(l+s30v29t_f-S.rig857baeP:u)yon4hk6 cwpm1050d0B0n0A0u0f0h0N0O0f0A0h0h0c010n0u0Q010406050h0E0R0R0A0t0G040r0H0f0E0-0H0I050b0@0_0{0}0=0Q04051d161g0b1d0=0d0u0k0#0%0)0+0%0I0v0E0A0v0B0q0Q0G0n0K140N0K0u0v0K0f1I0K0n0:050W0z0f0B1p0(0*011H1J1L1J0n1R1T1P0n0t1e1D0#100h0Q0A0I0+0l011V1r010p0Y0B0I0A0R0B1P1;1?1{1X1~1T21230:0a0N0C0t0H0Q0H0h0u130I0N0U1/0t0t0B0O2o16260I1e0b1D2B1+1-1,1Q0d281s0u0I202l1P1m1o0$1W2L2N0I0H2R1P0Q2u1e2z2B2(0?1=2p2T1|2X0t0`0f1P0A1G2u0p0+030o0o0O2Y0B1L2W0H0q0S360:0S160A2)2,0;2+272.1X2:2=2@2_0B2{012}2 31332O360q1_040l3b3d1?3f2z2K013k0A2?1e2^0K2`2|2~300U3u2X3w0i0:0i3B2y3e0=3F3i0+3I3K053M3O3q3Q3t2M3v370J0:0J3Z173#3g2-1q3j0H2;3J3m3N3o3P3s3S3=3U370x0:0x3{2(3$2,3G3*453.3r3R324b35370M0:0M4h3}3%403)423l3L3n3p4p3;343w0y0:0y4y3D4j3h4B3H4D444F464H3:4a4K370w0:0w4P2A4R3 2U4U433+3-473/494r4$0q0m0:0m4+2B2#0B2B2R2E0d1-2J3(014q2Q1n1e522%3e3!3D054q5h270u0d0+2~2z3w0S3m5p5r4_3T4t380N2c0B5y4q5A5u1P0b3c3~3G0L0:0U0p5j2A0N5N5a0I0p0:0W0Y1T5T5n4.1|0/040e5(5W4T0I0:0Q1 5/4A4/5,0F0D5(0=3|5k3F5x015s2,3w3y3,0N644!4`3?3x1`5E5G4J6f695L040N6p5V5`2/5?1 0o3A615U5:4/0H0:0c5(6r4k5X0:0C5^6y5)3G5,0e0F5 5_4k6c0o5t373W4F6V5H4s3V6h225F655z6%6Y5K3c6q6G4S4/5=042u0@0f0W0n6F6A1|6C046E6M6?5*1X0R0u0:0j6S6M5N6V6X0q3^6!5q6,6$4{3^5D6*6j4#6f7k3B6=711X5P040P1H5%767z0+0H0P0:2X6 7G6s3j6u7F2*7P7I0:0s6T6@6t040B0h0n0o0k5p0B0o5@7S5i7U016P5}7e7T6U7m661?3w4e7l7t6e4c0q4e7r23815I4d6:6o6=6q7H3H7R7,6x7_7Z1X737X7f7;6_0B0R7.0B0t7Y780+6P8x4l8h8B5a8n8E5;5Q0B8u8w8p6H4T7?6R6M608k2p7h674u5w7{6-4{4v866+6d890q4v2B6;8d6p8f6_6{0E6}0A7N2(773G73758|8=0:8@8_8{3e8}8F0:0g707;7a397^7:7`5y7i4M807n6k834M8(886.0q9l7x8e7;7B7D6L917;7J7L0H963D988I048u6w8H6B7W9O7!7$7(7*0U7-9B9h8l8z0:6Q5~8S8B8W7}4%8Z9s4{4(9r9n7u834(8.8c8:929L9Y628O9P048o8U8C7#8t1 8Ma55a8A8N9!8g9~1T9Nae8y018Gaka60U8L9R1X8Q9ga05o8!7i4}9m8*9t4}9=aC4{aA9w8;9y930V0E0t157Oa17!946~av2A165m1h2$1655160n57a(2H2C0A1S53a$5e600U5#0Z04.

III. Vérifier les parenthèses d'une expression mathématique⚓︎

Le but de cet exercice est d'écrire une fonction qui contrôle si une expression mathématique, donnée sous forme d'une chaîne de caractères, est bien parenthésée, c'est-à-dire s'il y a autant de parenthèses ouvrantes que de fermantes. On s'interdit d'utiliser des variables qui "comptent" les parenthèses ouvrantes ou fermantes.

Par exemple

(..(..)..) est bien parenthésée.
(...(..(..)...) ne l'est pas .

Indication à ne pas dévoiler trop vite ...

On crée une pile. On parcourt l'expression de gauche à droite.
Si on rencontre une parenthèse fermante ")", alors :

Si la pile n'est pas vide, on dépile
Sinon on renvoie False

À la fin la pile doit être vide...

Implémentation du type Pile

Nous allons utiliser l'implémentation vue au II.
Pour qu'elle soit active, ne pas oublier d'exécuter "la classe Pile"

Les parenthèses

Compléter ci-dessous

Évaluations restantes : 5/5

.128013/;=d(èl+s3x0v29Fét_f-S.rig85îT7baeP:u*)yonq4hk6 cwpCm1050e0I0s0H0z0h0j0W0X0h0H0j0j0d010s0z0Z010406050j0L0#0#0H0y0O040w0P0h0L0`0P0Q050b111315170 0Z04051n1g1q0b1n0 0e0z0n0/0;0?0^0;0Q0A0L0H0A0I0v0Z0O0s0T1e0W0T0z0A0T0h1S0T0s0}050*0G0h0I1z0=0@011R1T1V1T0s1#1%1Z0s0y1o1N0/1a0j0Z0H0Q0^0o011)1B010u0,0I0Q0H0#0I1Z1~20251+281%2b2d0}0a0W0J0y0P0Z0P0j0z1d0Q0W0(1|0y0y0I0X2y1g2g0Q1o0b1N2L1^1`1_1!0e2i1C0z0Q2a2v1Z1w1y0:1*2V2X0Q0P2#1Z0Z2E1o2J2L2=101 2z2%262+0y140h1Z0H1Q2E0u0^030t0t0X2,0I1V2*0P0v0o0v0$0}0W0$1g0H2?2_0~2^2h2{1+2}2 31330I350137393b3d2Y3g3g3k0o3n3p203r2J2U013w0H301o320T3436383a0(3G2+3I0k3k0k3M2I3q0 3Q3u0^3T3V053X3Z3C3#3F2W3H3h0S3k0S3.1h3:3s2`1A3v0P2~3U3y3Y3A3!3E3%403)3h0C3k0C462=3;2_3R3^4g3|3D3$3c4m3f3h0V3k0V4s483=4b3@4d3x3W3z3B4A3 3e3I0F3k0F4J3O4u3t4M3S4O4f4Q4h4S3~4l4V3h0B3k0B4!2K4$4a2(4)4e3_3{4i3}4k4C4;0v0p3k0p4_3P4v3?4~4P3`4R4j4B3(4E3i0m0}0$0m5b4{4w4*505i535k4D3I0$3j045C5s495u4 4y524T4:413i235E3L0b3o3/4#5H5e4x4,4z4/555O0$3+5E3-5T3N4`5X4(5Z5h4-5j4U5(435E455-5V5/4L4}5=514.545l5B4p5E4r5~475W612|5v5K655z560$4G5E4I6c4t5:626h5!5L5$673h0$4X5E4Z6q4K5d5;6u5?5#665A6z4?5E4^6E6e6G6t5J6v6j5_4n3i585E5a6R606T6g6V6J6w6L560o5o046;5G6f4c6,645^5N6Z0o5D706^6*6`5g6|5y6Y5m0o5Q7b734%6U765x5M5%6 5*0o5,5U6d6)7f6+7h5@786~7a5{0o5}7p6r6_4N6{7i6x6M3g690o6b7C6F7s754+6-6X7x3I0o6n7X5b1r2:1g2#2O0e1`2T5e4B2!1x1o2/0I2;3q5 1o4B7@2h0z0e0^382J5B3y7~806/5(242m0I866k882L5U7E010U0}0(0u7_0W6s2|0u0}0n0I0y0z280X0H2H7q7|4|260|040f7_8p3v0}0I0l2/0t141N8I8h8F0N0K7_0 8B5H8501812_7W847 8$876 892c8b8,8d8.8f8C3R0Y3k0W8}8S740^0j0e0}020R0L0P0s0c9597999b980c8X8 7}8+8%203*8*8c799n0W8a9p7V3h5*3.8h928|8}0!0)0s1(0u1e2G0z1P2E0Q0n0P0z1(0E0y0L1(2w0W0L2X0W8M7=0?9K2z8Q0T0r8Q0z961(320H1c200s2A0I9h8Z3Q8#9l0Q3I5{5h9~8-5m439s8:9u7ka61Z5~9z93048}8}1 9M1N0g0j0I0.0P0L0n0y9@ap0W9/9_0Wak2aamao0.0u8u140Q9F0j0x9{2@9}9k0t824o9o8=9qaTa82daa6y0v699y90019Aahai2r0r3a0Q1w2y0W0K9!8N0y8P8z0T9!0j9^2B0s0O0Z1(0X0T0H0D9Z2B8yau2G0g2EaLaN7^aP86aS0v6na3aQ8?5m4GaY8;7I56bpaea)a+ai2q2v0sa:a=9(a@0W0;0W0n3U0I0L0y0W9M9O0O0r1(apb11(b3b50W0G0P1abX0QaM8B8YaO4va4bn6Bbqa!7J4Xbvb`56b^bA7Q91agbD8M0I0#0Z1%0.8Wb/9i2zb?8(4=aUbx5O4?b}aV9v0v6O3Mb:bkb=aQbn6#b_coab3I58cnck6Zcyc18D1+bCai020A9dcO9acQbN8u8w0z8y2y0f9e990f0k0M0f4o0l0N0i0k0Nc!0c0Nbj3O8!cwch5ncja55B5ocEc}6z6=a(c2a*c4ai9S9Uc?2Kc^bmc`5Cc|bs5B3jd0di6z5Dd4cJc39B0WcNcPdv0ccT8v8x8z9(cZ969fc$c(c*c,0kc:c=cd9|cvde9m6z5QczcF5m0$23dlaW5Pad8gbBd78}0q3Uaodb8_cgdR3i9x32a4dmd=8/aZcAa#5)d$8_5ecL8}ducRdwdycVcXdCc:dLd.dd8,bn0$a2d@brd!eid{bwd13ia2cI3Re30Wd99`dNb;9jdQa06za%ekb~5(4pdZcp0$a%5-ctc@blegdfbpeGd}7J6meoeH6ZeY8^8Jdra,e4dE9de,9ae.eeeR9 5Bb^eVdVe@eZeW6lc03obDe(3S0}0Z8nf20P0}0df68h0Q0}0J29ce3R8F0fdM6rdOeBeSd;0$cre_eqfre|e`6Ne0f18h8j049H0yfba)fd04bdfGd50P8{042WfLdqf3049#a{9*fh5e8FccfmeAcfc_fqcyftd_0$cD9te}5(cHf0bDaif2fC8wfR4w0}fK8B8o8hf8040dfag1f20j5D02030k0p0ccZgdgffY4(f!e;dPfpeD3gd3f,d!6;fweqgv8^f^gAg2fHf4gk4}g4b.f%f~fUc829fFfnfSfjgF2|f 15gS1+8Ugnfoe?3h70dhgudkf:fx3gdo5-gBgCd5f{8mg8fcgUgO2=g;fSg4g6f}e2gbgic;gcge9ggPfi0}f#48h9d:gq7bg(cphheKcBg$dTg/g:f_fB0}f|g^gD04f5h95egHgW3@8Lb00t0n7~0I0t0Zfghzgl0}fkhc5Whef)hgd?0Wd^gu3+hla#7nfzhqgAf`0}2E0sbR1fhvg=0X0}d+0-eyf$cug!aRc`7Ahihm3ga7g+gxesf@h)h+fUh_hC01gmezh|f(eC7WeFhXelhjeJi5d_7Mh(h)fAhwhygJhA0}gIihgK0(hL1%g{iCfZhPflhdgJhf7WeUime!7abuiqgubzi8g}3RfCh-h/h15;gEhNgGiAidfIbZhGhIhKhMiyhO8GiLhS2@0b7{7#7?7%7:1g0s7*j42R2M0H1$j10b7(8Y0(0*0,0j04.

Source : Stéphan Van Zuijlen