Pile et file
NSI Terminale
Définition
Une pile (*stack*) et une file (*queue*) sont deux structures de données linéaires qui se distinguent par leur ordre d'accès aux éléments. La pile fonctionne en LIFO (*Last In, First Out*) : le dernier élément ajouté est le premier retiré, comme une pile d'assiettes. La file fonctionne en FIFO (*First In, First Out*) : le premier élément ajouté est le premier retiré, comme une file d'attente. On y accède uniquement par les opérations `empiler`/`dépiler` (pile) et `enfiler`/`défiler` (file).
Formule
$$\text{Pile : LIFO} \qquad \text{File : FIFO}$$
Exemple corrigé
Énoncé
On empile successivement 1, 2 puis 3 dans une pile vide, puis on dépile un élément. Quel élément est retiré et que contient ensuite la pile ?
Solution
On applique le principe LIFO : le dernier élément empilé est le premier dépilé.
Après avoir empilé 1, 2 puis 3, le sommet de la pile est 3 :
- Pile : `[1, 2, 3]` (3 au sommet)
- `dépiler()` retire le sommet, soit 3
- Pile restante : `[1, 2]`
```python
pile = []
pile.append(1) # empiler 1
pile.append(2) # empiler 2
pile.append(3) # empiler 3
sommet = pile.pop() # dépiler -> 3 (LIFO)
print(sommet) # 3
print(pile) # [1, 2]
```
À titre de comparaison, avec une file (FIFO), `défiler()` aurait retiré le premier entré, soit 1.
$$\boxed{\text{Élément retiré} = 3,\quad \text{pile} = [1, 2]}$$
Erreurs classiques
- Confondre LIFO (pile) et FIFO (file) et retirer le mauvais élément.
- Accéder à un élément au milieu de la structure : pile et file n'autorisent l'accès qu'à une seule extrémité (sommet ou tête).
Pour aller plus loin : le chapitre « Structures de données » (cours et exercices corrigés).