Piles (Stacks)

1. Définition et principe fondamental

Une pile (ou stack en anglais) est une structure de données linéaire, dynamique et ordonnée, dans laquelle les éléments sont manipulés selon une stratégie stricte :

LIFO → Last In, First Out
Cela signifie que le dernier élément ajouté est le premier à être retiré.

C’est une organisation très courante dans les systèmes où l’ordre de traitement est inverse à l’ordre d’arrivée.

2. Structure logique d’une pile

Une pile peut être vue comme une colonne verticale d’objets empilés.

On ne peut y faire qu'une seule chose : empiler au sommet (ajouter) ou dépiler du sommet (retirer).

Contrairement aux listes classiques :

On ne parcourt pas la pile de façon libre.

On ne lit pas directement l’intérieur : pas de pile[i].

On modifie que le sommet.

3. Opérations fondamentales

Voici les trois opérations élémentaires associées à une pile :

Opération	Description	Python
`empiler(x)`	ajoute un élément au sommet	`pile.append(x)`
`dépiler()`	retire et retourne le sommet	`pile.pop()`
`est_vide()`	teste si la pile est vide	`len(pile) == 0`

Ces trois opérations forment le comportement minimal attendu d’une pile, quel que soit le langage ou le contexte.

En Python, on utilise naturellement une liste pour simuler une pile car elle permet append() et pop() efficacement en fin de liste.

4. Implémentation en Python

Création

pile = []

Empiler un élément

pile.append("élément")

Ajoute au sommet. C’est l’équivalent logique d’empiler une assiette sur une pile.

Dépiler un élément

dernier = pile.pop()

Retire et retourne l’élément au sommet de la pile.

❗ Si la pile est vide, pop() déclenche une erreur (IndexError), il faut donc toujours tester est_vide() avant.

Tester si pile vide

if len(pile) == 0:
    print("pile vide")

5. Contraintes importantes

Une pile est une structure fermée : on ne manipule pas ses éléments internes.
Pas de pile[2], pile.insert(0, x) ou pile.sort().

Toute tentative de modification "directe" de la pile viole son principe fondamental (LIFO).

Une pile n’est pas triée, et on ne cherche pas à l’ordonner.

6. Avantages et intérêt algorithmique

Gestion automatique des priorités inversées (le dernier arrivé est prioritaire).

Optimisation de la mémoire : la pile est souvent utilisée pour remplacer la récursivité ou simuler des appels de fonction.

Sécurité du traitement : l’ordre LIFO permet de contrôler très précisément la gestion d’états successifs.

7. Complexité algorithmique

Toutes les opérations de pile en Python avec une liste sont en temps constant (𝑂(1)) :

Opération	Complexité
`append()`	𝑂(1)
`pop()` (sur le dernier élément)	𝑂(1)
`len()`	𝑂(1)

✅ Cela en fait une structure extrêmement rapide et adaptée aux algorithmes exigeants.

8. Cas d’usage généraux

Les piles interviennent dans :

Le stockage temporaire d'informations dans un ordre inversé

Le suivi des appels de fonction (pile d’exécution)

Les annulations (undo/redo) dans les logiciels

Le parcours en profondeur (DFS) de structures arborescentes ou de graphes

La traduction d'expressions (infixe/postfixe)

Dans tous ces cas, l’ordre d’arrivée des éléments est crucial, et la pile permet de les traiter à rebours.

9. Bonnes pratiques pour le bac

Toujours tester si la pile est vide avant d’utiliser pop().

Ne jamais manipuler les éléments internes.

Comprendre que append() et pop() agissent au sommet uniquement.

Être capable de traduire un algorithme en pseudo-code utilisant une pile vers du code Python.

📌 En résumé

Une pile suit le modèle LIFO : on traite les éléments dans l’ordre inverse de leur arrivée.

En Python, une liste avec append() et pop() suffit pour implémenter une pile.

Elle est utilisée dès que l’on veut mémoriser un historique, revenir en arrière, ou simuler des appels récursifs.

Elle fait partie des structures fondamentales à maîtriser pour l’épreuve de NSI, avec une forte composante algorithmique.