%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Piles et Files/Piles et Files|Accueil · Piles et Files]]
>
> | | [[Code et Développement/Programmation/Piles et Files/02_Les files\|Les files →]] |
> |:---|---:|
%% nav-fin %%
# Les piles
Une pile (en anglais *stack*) est une structure de données où l'on ajoute et retire les éléments au même endroit, appelé le sommet.
Le dernier élément ajouté est le premier retiré. Ce principe s'appelle **LIFO**, pour *Last In, First Out*.
Une pile offre quatre opérations :
- **empiler** : ajouter un élément au sommet ;
- **dépiler** : retirer l'élément du sommet et le renvoyer ;
- **sommet** : lire l'élément du sommet sans le retirer ;
- **taille** : compter les éléments.
Les piles servent par exemple à gérer les appels de fonctions, à annuler une action dans un éditeur ou à parcourir un graphe en profondeur.
---
## Implémenter une pile en Python
La classe `Pile` stocke ses éléments dans une liste Python. Le sommet est la fin de la liste.
```python
class Pile:
def __init__(self):
self.elements = []
def empile(self, element):
self.elements.append(element)
def depile(self):
if self.elements:
return self.elements.pop()
def taille(self):
return len(self.elements)
def sommet(self):
if len(self.elements) == 0:
raise Exception("La pile est vide")
return self.elements[-1]
def __str__(self):
if not self.elements:
return "Pile vide"
return "Pile : " + " -> ".join(str(x) for x in reversed(self.elements))
```
Chaque méthode correspond à une opération de liste :
| Méthode | Opération de liste | Effet |
|---|---|---|
| `empile(x)` | `append(x)` | ajoute `x` à la fin de la liste, donc au sommet |
| `depile()` | `pop()` | retire et renvoie le dernier élément |
| `sommet()` | `elements[-1]` | lit le dernier élément |
| `taille()` | `len(elements)` | compte les éléments |
Sur une pile vide, `depile()` ne retire rien et renvoie `None`. `sommet()` lève une exception, car il n'y a aucun élément à lire.
La méthode `__str__` affiche le sommet en premier. Elle traite le cas de la pile vide.
**À manipuler :** créez la pile du programme suivant, puis appelez ses méthodes. Chaque bouton affiche l'appel Python équivalent.
```python
stack = Pile()
stack.empile(4)
stack.empile(9)
stack.empile(1)
print(stack) # Pile : 1 -> 9 -> 4
stack.depile()
print(stack) # Pile : 9 -> 4
stack.empile(3)
print(stack) # Pile : 3 -> 9 -> 4
```
```sq-pile
initial: 4, 9, 1
nom: stack
```
---
## Application : la gare de triage
Un train est une liste de wagons numérotés. On veut un train de sortie où les wagons impairs passent en premier, dans leur ordre d'arrivée. Les wagons pairs suivent.
Une voie d'attente sert de pile :
1. un wagon impair part directement en sortie ;
2. un wagon pair est empilé sur la voie d'attente ;
3. une fois le train d'entrée vide, on dépile la voie d'attente vers la sortie.
```python
train = [7, 16, 4, 3, 9, 6, 11]
def tri_wagons(t):
sortie = []
attente = Pile()
for i in t:
if i % 2 == 0:
attente.empile(i)
else:
sortie.append(i)
while attente.taille() != 0:
sortie.append(attente.depile())
return sortie
print(tri_wagons(train)) # [7, 3, 9, 11, 6, 4, 16]
```
Les wagons pairs sortent dans l'ordre inverse de leur arrivée : 16 est arrivé en premier, il sort en dernier.
**À manipuler :** suivez chaque wagon jusqu'au train de sortie.
```sq-triage
train: 7, 16, 4, 3, 9, 6, 11
```
---
## Application : vérifier les parenthèses
Une expression est bien parenthésée si chaque symbole fermant correspond au dernier symbole ouvrant encore ouvert.
Une pile garde les symboles ouverts :
1. un symbole ouvrant `(`, `[` ou `{` est empilé ;
2. un symbole fermant doit correspondre au sommet, qui est alors dépilé ;
3. à la fin, la pile doit être vide.
**À manipuler :** modifiez l'expression et suivez la pile.
```sq-parentheses
expression: (a + [b * c]) - {d / e}
```
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Piles et Files/Piles et Files|Accueil · Piles et Files]]
>
> | | [[Code et Développement/Programmation/Piles et Files/02_Les files\|Les files →]] |
> |:---|---:|
%% nav-fin %%