Sur cette page
Un exemple concret
Le bouton « Retour » d'un navigateur utilise une pile : la dernière page visitée est la première rappelée. Une imprimante partagée utilise une file : si trois élèves envoient leur document à 10 h 01, 10 h 02 et 10 h 03, ils sont imprimés exactement dans cet ordre.
Le piège à éviter
Ne confonds pas l'interface (les opérations empiler, dépiler, enfiler, défiler, est_vide) avec l'implémentation. Une liste Python peut servir aux deux, mais retirer le premier élément d'une liste coûte un temps proportionnel à sa taille.
Pour aller plus loin
Une structure de données abstraite se définit par ses opérations, pas par sa représentation en mémoire. Pour une pile, on dispose de creer_pile, est_vide, empiler et depiler ; seul le sommet est accessible. Pour une file, on dispose de creer_file, est_vide, enfiler et defiler ; on ajoute en queue et on retire en tête. Dans les deux cas, on n'accède jamais directement à un élément situé au milieu.
Côté implémentation, une liste Python fait une très bonne pile : append ajoute au sommet et pop retire le sommet, en temps constant. Pour une file, pop(0) décale tous les autres éléments, donc le coût est linéaire. On préfère alors deux piles, une classe avec une liste chaînée, ou l'objet deque du module collections, qui ajoute et retire aux deux bouts en temps constant.
Ces structures apparaissent partout dans le programme de Terminale. La pile d'appels gère les fonctions récursives : chaque appel est empilé, puis dépilé quand il renvoie son résultat. La vérification des parenthèses d'une expression se fait avec une pile. Le parcours en largeur d'un graphe ou d'un arbre utilise une file, alors que le parcours en profondeur utilise une pile. Au bac, on te demande souvent d'écrire les méthodes d'une classe Pile ou File, ou de simuler l'état de la structure après une suite d'opérations.
Ne pas confondre
- Liste : Une liste permet d'accéder à n'importe quel élément par son indice. Une pile ou une file n'autorise l'accès qu'à une extrémité.
- Tableau : Le tableau est une représentation en mémoire. La pile et la file sont des interfaces qu'on peut implémenter avec un tableau ou une liste chaînée.
Dans ta copie
Une pile est une structure de données linéaire qui fonctionne selon le principe LIFO : le dernier élément ajouté est le premier retiré, et seul le sommet est accessible. À l'inverse, une file fonctionne selon le principe FIFO : les éléments sont retirés dans leur ordre d'arrivée. Par exemple, l'historique d'un navigateur se comporte comme une pile, tandis qu'une file d'impression traite les documents dans l'ordre d'envoi. Le choix entre les deux dépend donc de l'ordre de traitement voulu.
À retenir
- La pile suit le principe LIFO : dernier entré, premier sorti.
- La file suit le principe FIFO : premier entré, premier sorti.
- La pile d'appels gère l'exécution des fonctions récursives.
- Le parcours en largeur utilise une file, le parcours en profondeur une pile.
Teste-toi
NSI · question corrigée
Dans une pile vide, on empile 4, puis 7, puis 2, puis on dépile une fois. Quel élément est retiré ?
Voir la réponse
Réponse C. Une pile est LIFO : le dernier élément empilé, ici 2, est le premier dépilé.
NSI · question corrigée
Quelle structure convient le mieux pour gérer les clients d'un guichet servis dans leur ordre d'arrivée ?
Voir la réponse
Réponse A. Servir dans l'ordre d'arrivée correspond exactement au principe FIFO d'une file.
Questions fréquentes
Que signifient LIFO et FIFO ?
Ce sont des sigles anglais. LIFO veut dire « Last In, First Out » (dernier entré, premier sorti) et FIFO « First In, First Out » (premier entré, premier sorti).
Peut-on faire une file avec deux piles ?
Oui, c'est un exercice classique. On enfile dans une première pile ; pour défiler, on vide la première pile dans la seconde si celle-ci est vide, puis on dépile la seconde, ce qui rétablit l'ordre d'arrivée.
Notions liées
Pour réviser tout le chapitre, va sur la page NSI, ou retrouve toutes les définitions dans le lexique du bac. Dans l'application, les quiz reprennent ces notions sur le programme de ta série.