PARTIE 4 : PILES (STACKS)

Concepts (LIFO)

Une Pile (Stack) fonctionne sur le principe LIFO (Last In, First Out) : Dernier arrivé, premier sorti. C’est comme une pile d’assiettes.

Opérations :

• Push (Empiler) : Ajouter au sommet (top).
• Pop (Dépiler) : Retirer du sommet.
• Peek : Voir le sommet.

Schéma :

TP 14 : Implémentation

C’est simplement une Liste Chaînée où on insère et supprime toujours à la même extrémité (head qu’on appelle top).

void push(Node** top, int val) {
    insertAtHead(top, val); // On réutilise notre fonction !
}

int pop(Node** top) {
    // Supprimer le premier et retourner sa valeur
}

TP 15 : Parenthèses Équilibrées

C’est l’application classique des piles. Exemple : ( ( [ ] ) ) est valide. ( [ ) ] est invalide.

Algorithme :

1. Parcourir la chaîne.
2. Si Ouvrante (, [, { : Push sur la pile.
3. Si Fermante ), ], } :
   • Si pile vide -> Erreur (trop de fermantes).
   • Sinon Pop. Vérifier si le caractère dépilé correspond (ex: si j’ai }, je dois avoir dépilé {).
4. À la fin, si pile vide -> Valide. Sinon -> Erreur (trop d’ouvrantes).