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 »).
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 ... 
Image crée par Gilles Lassus
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
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Imaginez vos propres tests
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
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
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Solution
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
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Test du code d'Alice
Tester
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
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 ...
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
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
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Source : Stéphan Van Zuijlen
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)