Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Les structures linéaires organisent les données en séquence. Trois sont au programme.
La liste (séquence) est une suite ordonnée d'éléments accessibles par leur position. En Python, le type list offre l'accès indexé en temps constant et l'ajout en fin amorti O(1).
La pile fonctionne en LIFO (Last In First Out) : on n'ajoute (empiler) et ne retire (depiler) qu'au sommet. Le dernier élément entré est le premier à sortir. C'est le modèle de la pile d'assiettes : on prend toujours celle du dessus.
La file fonctionne en FIFO (First In First Out) : on ajoute en queue (enfiler) et on retire en tête (defiler). Le premier entré est le premier sorti. C'est le modèle de la file d'attente à un guichet.
Pile et file partagent un point commun : ce sont des structures d'accès restreint, on ne lit ni ne modifie un élément au milieu. Elles ne se distinguent pas par leur interface mais par leur politique de sortie. Le choix entre les deux dépend donc du sens dans lequel on veut retraiter les données : la pile inverse l'ordre d'arrivée, la file le conserve.
Implémentation d'une pile avec une liste Python :
pile = [] pile.append(x) # empiler -> O(1) amorti pile.pop() # depiler -> O(1), renvoie le sommet pile[-1] # sommet pile == [] # est_vide
Implémentation efficace d'une file :
from collections import deque f = deque() f.append(x) # enfiler -> O(1) f.popleft() # defiler -> O(1)
1. Identifier la politique : « dernier arrivé d'abord » = pile ; « premier arrivé d'abord » = file. 2. Pour tracer l'exécution, dessiner la structure après chaque opération. 3. Choisir l'implémentation (liste pour une pile, deque pour une file). 4. Toujours tester le cas vide avant de dépiler/défiler.
list.pop(0) pour une file : c'est O(n), on préfère deque.popleft().liste[-1], pas liste[0].L'exercice du parenthésage équilibré (avec une pile) revient très souvent : empiler à l'ouverture, dépiler à la fermeture, vérifier que la pile finit vide. Sachez tracer l'état d'une pile ou d'une file après une suite d'opérations, en dessinant la structure après chaque empiler/depiler. À l'épreuve pratique, on vous demande souvent d'implémenter ces structures comme classes : respectez l'interface (noms des méthodes imposés) et gérez le cas vide en levant une erreur ou en renvoyant la valeur convenue. Pensez aussi aux applications classiques que le correcteur apprécie de voir citées : pile pour la récursivité et l'annulation (Ctrl+Z), file pour les files d'attente et le parcours en largeur.