Loading
Loading
Listes, piles, files et dictionnaires forment la boîte à outils du programmeur pour organiser des données. Cette fiche distingue rigoureusement l'interface d'une structure (le contrat des opérations) de son implémentation (sa représentation interne en Python), puis spécifie et implémente piles (LIFO), files (FIFO) et dictionnaires, et apprend à choisir la structure adaptée à un problème en justifiant le choix par le coût des opérations.
5sectionsca. 19min de lecture4compétencesNiveauBase 1 · Standard 3 · Approfondissement 1Vérifié · 06/2026
Lesetiefe: Approfondi
Schriftgröße: Standard
Type abstrait « Pile » : une interface, plusieurs implémentations
Rédigez l'interface (le contrat) d'une pile d'entiers : pour chaque opération, donnez sa signature, son effet et, le cas échéant, sa précondition. N'écrivez aucun code de représentation interne.
Signature : creer_pile() → Pile. Effet : renvoie une nouvelle pile vide. Précondition : aucune.
Signature : est_vide(p) → bool. Effet : renvoie True si la pile p ne contient aucun élément, False sinon. Précondition : aucune.
Signature : empiler(p, x) → None. Effet : ajoute x au sommet de p ; après l'appel, sommet(p) vaut x. Précondition : aucune.
Signature : depiler(p) → élément. Effet : retire et renvoie l'élément situé au sommet de p. Précondition : p ne doit pas être vide (sinon l'opération est indéfinie).
Signature : sommet(p) → élément. Effet : renvoie l'élément au sommet SANS le retirer. Précondition : p ne doit pas être vide.
Résultat : L'interface décrit entièrement le comportement attendu de la pile (le contrat) sans rien dire de sa représentation : on peut maintenant l'implémenter de plusieurs façons.
Erreurs fréquentes
Révision active
On donne l'interface d'une file : creer_file(), enfiler(f, x), defiler(f), est_vide(f). Sans choisir d'implémentation, écrivez en français le contrat (effet attendu, valeur renvoyée, précondition) de chacune des quatre opérations.
Rappel actif
Rappelle-toi les points clés — puis révèle.
Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Numérique et sciences informatiques (voie générale) — programmes et ressources (Éduscol — Ministère de l'Éducation nationale)
Liste chaînée : maillons valeur / suivant et coûts des opérations
Coûts dans un tableau dynamique (list Python)
L'accès direct par indice est immédiat, mais insérer en tête décale les n éléments suivants.
Coûts dans une liste chaînée
Le compromis est inversé : l'accès devient linéaire, mais l'insertion en tête est immédiate car on ne déplace aucun élément.
On modélise une liste chaînée par une classe Maillon (attributs valeur et suivant). Écrivez la fonction inserer_en_tete(tete, x) qui insère x au début et renvoie la nouvelle tête, et justifiez son coût.
Un maillon a deux champs : valeur (l'entier stocké) et suivant (le maillon d'après, ou None). La liste est désignée par son premier maillon, la tête.
On crée m = Maillon(x). On veut que m précède l'ancienne tête : on règle donc m.suivant sur l'ancienne tête.
Le nouveau premier maillon est m : on le renvoie. Aucun autre maillon n'a été déplacé ni modifié.
On a effectué un nombre constant d'opérations (création d'un maillon + une affectation), indépendant de la longueur de la liste.
Résultat : inserer_en_tete s'écrit en trois lignes (m = Maillon(x) ; m.suivant = tete ; return m) et s'exécute en temps constant O(1), là où l'insertion en tête d'un tableau dynamique serait en O(n).
Erreurs fréquentes
Révision active
Implémentez une liste chaînée d'entiers (classe Maillon avec attributs valeur et suivant). Écrivez une fonction longueur(tete) qui renvoie le nombre de maillons, et une fonction inserer_en_tete(tete, x) qui renvoie la nouvelle tête après insertion de x.
Rappel actif
Rappelle-toi les points clés — puis révèle.
Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Numérique et sciences informatiques (voie générale) — programmes et ressources (Éduscol — Ministère de l'Éducation nationale)
Pile (LIFO) : empiler et dépiler au sommet
Discipline LIFO de la pile
Last In, First Out : la dernière valeur empilée est la première dépilée.
Discipline FIFO de la file
First In, First Out : la file préserve l'ordre d'arrivée des éléments.
File (FIFO) : enfiler en queue, défiler en tête
Application : une pile vérifie le bon parenthésage de « ([]) »
On part d'une structure vide et on exécute la suite d'opérations : ajouter 3, ajouter 7, ajouter 8, puis retirer, retirer. Donnez la valeur renvoyée par chaque retrait et l'état final (a) si la structure est une pile, (b) si c'est une file.
On empile 3, 7, 8 dans cet ordre. De bas en haut, la pile contient [3, 7, 8] ; le sommet est 8.
Le premier depiler() retire le sommet 8 et le renvoie. Le second retire le nouveau sommet 7 et le renvoie (LIFO). Il reste [3].
On enfile 3, 7, 8 ; de la tête vers la queue : [3, 7, 8]. La tête est 3.
Le premier defiler() retire la tête 3 et le renvoie. Le second retire la nouvelle tête 7 et le renvoie (FIFO). Il reste [8].
Résultat : Pile : les retraits renvoient 8 puis 7, état final [3]. File : les retraits renvoient 3 puis 7, état final [8]. Même suite d'entrées, ordres de sortie opposés : c'est toute la différence LIFO / FIFO.
À l'aide d'une pile, écrivez l'algorithme bien_parenthesee(ch) qui renvoie True si la chaîne ch, composée des symboles ( ) [ ], est correctement parenthésée (chaque fermante correspond à la dernière ouvrante non encore fermée). Déroulez-le sur « ([]) » puis sur « ([)] ».
On parcourt ch de gauche à droite. À chaque ouvrante ( ou [, on l'empile. À chaque fermante, on dépile : la pile doit être non vide et son sommet doit être l'ouvrante correspondante, sinon la chaîne est mal parenthésée.
Après lecture complète, la chaîne est bien parenthésée si et seulement si la pile est vide (toutes les ouvrantes ont été refermées).
( → empile ( ; [ → empile [ ; ] → sommet [ correspond, on dépile ; ) → sommet ( correspond, on dépile. Pile vide à la fin → True.
( → empile ( ; [ → empile [ ; ) → sommet est [ mais on attend [ ↔ ], incompatibilité → False (les paires se croisent).
Résultat : L'algorithme renvoie True pour « ([]) » (pile vide à la fin) et False pour « ([)] » (sommet incompatible à la fermeture). La discipline LIFO de la pile capture exactement l'imbrication correcte des parenthèses.
Erreurs fréquentes
Révision active
Implémentez une pile à l'aide d'une liste Python : écrivez les fonctions creer_pile(), est_vide(p), empiler(p, x), depiler(p) et sommet(p). Puis utilisez votre pile pour écrire bien_parenthesee(ch) qui teste si une chaîne formée de ( ) [ ] est correctement parenthésée.
Rappel actif
Rappelle-toi les points clés — puis révèle.
Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Numérique et sciences informatiques (voie générale) — programmes et ressources (Éduscol — Ministère de l'Éducation nationale)
Dictionnaire (table de hachage) : la clé est transformée en indice d'alvéole
Principe de la table de hachage
La fonction de hachage h calcule directement l'indice où ranger (ou retrouver) la valeur, d'où un accès quasi instantané.
Dictionnaire contre liste de couples
Chercher une clé dans une liste de n couples exige de la parcourir (O(n)) ; la table de hachage évite ce parcours.
Écrivez compter_lettres(mot) qui renvoie un dictionnaire {lettre : nombre d'occurrences}, et déroulez-le sur « banane ».
On part d'un dictionnaire vide d = {}. Il associera chaque lettre rencontrée à son compteur.
Pour chaque lettre du mot : si la lettre est déjà une clé de d (lettre in d), on incrémente d[lettre] ; sinon on crée le couple d[lettre] = 1. Le test in s'appuie sur le hachage, en O(1) moyen.
b → {b:1} ; a → {b:1, a:1} ; n → {b:1, a:1, n:1} ; a → a déjà présent, {b:1, a:2, n:1} ; n → {b:1, a:2, n:2} ; e → {b:1, a:2, n:2, e:1}.
Chaque lettre déclenche un test d'appartenance et une mise à jour en O(1) moyen ; pour un mot de longueur n, le total est O(n).
Résultat : compter_lettres('banane') renvoie {'b': 1, 'a': 2, 'n': 2, 'e': 1}. Le dictionnaire permet un comptage direct par clé, là où une liste de couples imposerait une recherche séquentielle à chaque lettre.
Erreurs fréquentes
Révision active
Écrivez compter_lettres(mot) qui renvoie un dictionnaire associant à chaque lettre de mot son nombre d'occurrences. Par exemple, compter_lettres('banane') doit donner {'b': 1, 'a': 2, 'n': 2, 'e': 1}.
Rappel actif
Rappelle-toi les points clés — puis révèle.
Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Numérique et sciences informatiques (voie générale) — programmes et ressources (Éduscol — Ministère de l'Éducation nationale)
Croissance du coût : accès par clé en O(1) (dictionnaire) contre O(n) (liste de couples)
Principe du choix par le coût
Le bon choix de structure minimise le coût unitaire de l'opération répétée le plus souvent.
Un logiciel gère les travaux envoyés à une imprimante : ils doivent être imprimés dans l'ordre d'arrivée, et l'on veut pouvoir retrouver instantanément le propriétaire d'un travail à partir de son identifiant. Choisissez les structures adaptées et justifiez par le coût des opérations.
Besoin 1 : traiter les travaux dans l'ordre d'arrivée (on ajoute à la fin, on retire au début). Besoin 2 : retrouver un propriétaire à partir d'un identifiant (accès par clé, répété).
L'ordre d'arrivée doit être respecté : c'est exactement la discipline FIFO d'une file. Enfiler en queue et défiler en tête (avec collections.deque) coûtent O(1).
On veut un accès direct par identifiant : un dictionnaire identifiant → propriétaire donne cet accès en O(1) en moyenne. Une liste de couples imposerait une recherche séquentielle en O(n) à chaque requête.
Pour q requêtes sur n travaux, la liste de couples coûte O(q·n) tandis que le dictionnaire coûte O(q) en moyenne : le gain est décisif quand n grandit.
Résultat : On choisit une file (FIFO) pour l'ordre d'impression — enfiler/défiler en O(1) — et un dictionnaire identifiant → propriétaire pour l'accès par clé en O(1) moyen, là où une liste de couples donnerait O(n) par requête. Le choix est justifié par le coût des opérations dominantes.
Tout part d'une question : quelle est l'opération que mon programme va répéter le plus souvent ?
Si je dois respecter l'ordre d'arrivée — imprimer les documents dans l'ordre où ils ont été envoyés — la discipline est FIFO : je choisis une file.
Si au contraire je veux retrouver une valeur à partir d'une clé symbolique, par exemple le propriétaire d'un travail à partir de son identifiant, je choisis un dictionnaire.
La justification est toujours chiffrée : recherche par clé dans une liste de couples, O(n) par requête ; dans un dictionnaire, O(1) en moyenne. L'écart se creuse vite.
Bien choisir sa structure de données, ce n'est donc pas un détail : cela peut faire passer un algorithme de O(n carré) à O(n).
Erreurs fréquentes
Révision active
Un logiciel doit gérer les travaux envoyés à une imprimante (traités dans l'ordre d'arrivée) et retrouver instantanément, à partir d'un identifiant de travail, son propriétaire. Quelles structures de données choisissez-vous pour chaque besoin ? Justifiez par le coût des opérations.
Rappel actif
Rappelle-toi les points clés — puis révèle.
Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Numérique et sciences informatiques (voie générale) — programmes et ressources (Éduscol — Ministère de l'Éducation nationale)
Références et sources
Ministère de l'Éducation nationale
Éduscol — Ministère de l'Éducation nationale