Piles et files : LIFO contre FIFO

Une pile (stack) est LIFO — dernier entré, premier sorti : on empile (`push`) et on dépile (`pop`) toujours du même côté, en O(1). Une file (queue) est FIFO — premier entré, premier sorti : on ajoute (`enqueue`) d'un côté et on retire (`dequeue`) de l'autre, en O(1) si bien implémentée.

Signal pour reconnaître une pile : l'énoncé implique un ordre « le dernier ouvert est le premier fermé » — parenthèses/crochets valides, annuler la dernière action, parcours en profondeur (DFS) itératif, évaluation d'expression.

Signal pour reconnaître une file : un traitement dans l'ordre d'arrivée — parcours en largeur (BFS), files d'attente, ordonnancement de tâches.

Pattern avancé : la pile monotone (monotonic stack), où on maintient une pile toujours croissante ou décroissante en dépilant les éléments qui violent l'ordre avant d'empiler le nouveau. Utile pour « trouver le prochain élément plus grand » ou calculer des plages, en O(n) au lieu de O(n²).

En JavaScript, un tableau fait très bien l'affaire comme pile (`push`/`pop` en fin de tableau, O(1)). Pour une file efficace, évite `shift()` sur un tableau (O(n) car il faut décaler tous les éléments) — préfère une liste chaînée ou une structure de deque dédiée.

Vidéo

Quiz