Qu'est-ce qu'une pile et à quoi sert-elle ?

Question

Accepted Answer

Une **pile** est une collection **LIFO** (Last-In, First-Out) : le dernier élément ajouté est le premier retiré. Vous ne touchez jamais que le **haut**.

## Opérations

```text
push(3)   push(7)   pop()->7   peek()->3
 [ 3 ]     [ 7 ]      [ 3 ]      [ 3 ]
           [ 3 ]                 top
            top
```

## Exemple

```python
stack = []
stack.append('a')   # push
stack.append('b')   # push
top = stack[-1]     # peek -> 'b'
stack.pop()         # pop  -> 'b'
```

Toutes les opérations sont **O(1)** quand elles sont soutenues par un tableau dynamique ou une liste chaînée.

| Opération | Temps |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Utilisations courantes

- **Call stack** — suit les appels actifs et les variables locales.
- **Annuler/Rétablir** — ajoutez chaque action ; retirez pour annuler.
- **Évaluation / analyse d'expressions** — appariement de parenthèses, conversion infix vers postfix.
- **Retour en arrière et DFS** — mémoriser où revenir.

## Pourquoi c'est important

La pile modélise « faire la chose la plus récente en premier », ce qui apparaît partout, de la récursion aux boutons de retour du navigateur.

Reconnaître un motif LIFO suggère immédiatement une pile, transformant souvent un problème embrouillé en quelques lignes push/pop propres.