Listes, piles et files
Terminale · NSI · Structures de données
Structures de données
Types abstraits : listes, piles et files
En Terminale, on ne se contente plus d'utiliser les listes Python : on apprend à raisonner sur des structures de données abstraites. L'idée est puissante et très simple : on décrit une structure par ce qu'elle sait faire (son interface), pas par la façon dont elle est rangée en mémoire. Deux programmeurs peuvent alors implémenter la même structure de deux manières différentes sans que le code qui l'utilise ait à changer d'une ligne.
La liste : le type abstrait de base
Une liste est une séquence finie et ordonnée d'éléments. Son interface minimale comporte : créer une liste vide, tester si une liste est vide, ajouter un élément en tête, récupérer la tête (le premier élément), récupérer la queue (la liste privée de sa tête), connaître la longueur.
Attention : la liste au sens du type abstrait n'est pas exactement le type list de Python, qui est en réalité un tableau dynamique (accès direct par indice, en temps constant). C'est une confusion classique.
Image mentale : une pile d'assiettes. On pose l'assiette sur le dessus, on reprend celle du dessus. Impossible d'attraper celle du fond sans enlever toutes les autres — et c'est volontaire : une pile n'offre pas d'accès par indice.
| Pile | File | |
|---|---|---|
| Principe | LIFO — dernier entré, premier sorti | FIFO — premier entré, premier sorti |
| Ajouter | empiler : au sommet | enfiler : en queue |
| Retirer | dépiler : au sommet | défiler : en tête |
| Extrémités utilisées | une seule | deux (une pour entrer, une pour sortir) |
| Image | pile d'assiettes | file d'attente à la boulangerie |
| Usages typiques | annuler une action (Ctrl+Z), pile d'appels de fonctions, vérifier un parenthésage, parcours en profondeur | file d'impression, tampon clavier, gestion de tâches, parcours en largeur |
Structures de données
Implémentations et coûts
Le même type abstrait peut être implémenté de plusieurs façons. Ce choix ne change pas ce que le programme fait, mais il change beaucoup ce qu'il coûte. Savoir comparer ces coûts est un attendu central du programme de Terminale.
Implémentation par tableau dynamique (list Python)
Pour une pile, c'est idéal : on représente la pile par une liste Python, le sommet est la fin de la liste. Empiler devient p.append(x) et dépiler devient p.pop(). Ces deux opérations coûtent un temps constant, noté O(1) : on n'a rien à décaler.
| Opération | Tableau dynamique (list) | Liste chaînée |
|---|---|---|
| Accès au k-ième élément | O(1) | O(k) : il faut parcourir le chaînage |
| Ajout / retrait en tête | O(n) : décalage de tous les éléments | O(1) |
| Ajout / retrait en fin | O(1) (append / pop) | O(n) sans pointeur de queue, O(1) avec |
| Longueur | O(1) (Python la mémorise) | O(n) si aucun compteur n'est maintenu |
| Mémoire | compacte | un surcoût par maillon (la référence suivant) |
Une file avec deux piles
C'est un grand classique de l'épreuve. On utilise deux piles : E (entrée) et S (sortie).
— enfiler(x) : on empile x dans E.
— defiler() : si S est vide, on transvase tout E dans S (on dépile E et on empile dans S), puis on dépile S.
Pourquoi cela marche ? Parce que transvaser une pile dans une autre inverse l'ordre : l'élément qui était au fond de E se retrouve au sommet de S. Le LIFO appliqué deux fois redonne un FIFO.
Exercices corrigés
Selon quel principe fonctionne une pile ?
- A.LIFO : le dernier élément empilé est le premier dépiléBonne réponse
- B.FIFO : le premier élément empilé est le premier dépilé
- C.Accès direct par indice, comme un tableau
- D.Les éléments sont maintenus triés par ordre croissant
Réponse : A — LIFO : le dernier élément empilé est le premier dépilé
Une pile n'a qu'une seule extrémité utilisable, le sommet : on empile dessus, on dépile dessus. Le dernier arrivé est donc forcément le premier à repartir, c'est le principe LIFO (Last In, First Out). Le FIFO, c'est la file. Et une pile n'offre ni accès par indice ni tri : ce sont justement les opérations que son interface interdit.
Selon quel principe fonctionne une file ?
- A.LIFO : le dernier entré sort le premier
- B.Les éléments sortent dans un ordre aléatoire
- C.FIFO : le premier entré est le premier sortiBonne réponse
- D.Les éléments sortent dans l'ordre croissant de leur valeur
Réponse : C — FIFO : le premier entré est le premier sorti
Dans une file, on entre par la queue et on sort par la tête : les deux extrémités sont différentes. Le premier arrivé attend devant tout le monde et sort donc en premier — FIFO, exactement comme une file d'attente à la boulangerie. Le LIFO correspond à la pile. Aucune structure du programme ne fait sortir les éléments au hasard, et le tri n'est jamais automatique.
On implémente une file avec une liste Python : enfiler = append(x) et defiler = pop(0). Quel est le coût de defiler ?
- A.Constant, O(1) : sans aucun décalage des autres éléments
- B.Linéaire, O(n) : retirer l'élément d'indice 0 oblige à décaler tous les autresBonne réponse
- C.Logarithmique, O(log n) : comme pour une recherche dans un arbre équilibré
- D.O(n log n), comme pour un tri par fusion ou un tri rapide efficace
Réponse : B — Linéaire, O(n) : retirer l'élément d'indice 0 oblige à décaler tous les autres
C'est LE piège de la file en Python. Une liste Python est un tableau dynamique : les éléments occupent des cases consécutives. Retirer celui d'indice 0 force donc à décaler d'un cran les n − 1 éléments restants, d'où un coût linéaire O(n). Le code fonctionne, mais devient très lent sur de grandes files. Les bonnes solutions : une liste chaînée avec pointeur de queue, ou la technique des deux piles.
On vérifie le parenthésage de « ( ( ) ( ) ) » avec une pile : on empile à chaque '(' et on dépile à chaque ')'. Combien d'éléments la pile contient-elle au maximum pendant le traitement ?
- A.1
- B.2Bonne réponse
- C.3
- D.6
Réponse : B — 2
Déroulons la hauteur de la pile caractère par caractère : '(' → 1, '(' → 2, ')' → 1, '(' → 2, ')' → 1, ')' → 0. Le maximum atteint est donc 2, et la pile finit vide : l'expression est bien parenthésée. Répondre 6 revient à compter tous les caractères, mais chaque ')' dépile immédiatement. Le maximum correspond en réalité à la profondeur d'imbrication des parenthèses.
Une liste chaînée de n maillons ne maintient aucun compteur d'éléments. Quel est le coût du calcul de sa longueur ?
- A.O(1), comme pour la taille d'une liste Python classique
- B.O(n) : il faut parcourir tout le chaînage jusqu'à rencontrer NoneBonne réponse
- C.O(log n), comme pour une recherche dans un arbre équilibré
- D.O(n²), comme pour un tri par comparaison peu efficace
Réponse : B — O(n) : il faut parcourir tout le chaînage jusqu'à rencontrer None
Sans compteur, la seule information disponible est la tête. Il faut donc partir de là et suivre les références suivant en incrémentant un compteur jusqu'à tomber sur None : n étapes, donc O(n). C'est une différence nette avec la liste Python, dont len() est en O(1) car la taille est mémorisée. Remède classique : ajouter un attribut taille à la structure et le mettre à jour à chaque ajout ou retrait — la longueur redevient alors en O(1).
Une file est implémentée par deux piles E et S, le transvasement n'ayant lieu que lorsque S est vide. On exécute : enfiler(1), enfiler(2), enfiler(3), defiler(), enfiler(4), defiler(), defiler(). Quelles valeurs sont renvoyées par les trois defiler(), dans l'ordre ?
- A.1, 3, 2
- B.1, 4, 2
- C.3, 2, 1
- D.1, 2, 3Bonne réponse
Réponse : D — 1, 2, 3
Déroulons. Après les trois enfilements : E = fond [1, 2, 3] sommet, S vide. Premier defiler() : S est vide, on transvase → on dépile 3, 2, 1 de E et on les empile dans S, donc S = fond [3, 2, 1] sommet ; on dépile S et on obtient 1. Puis enfiler(4) place 4 dans E, sans toucher à S. Deuxième defiler() : S contient encore [3, 2], non vide, donc pas de transvasement — on dépile 2. Troisième defiler() : on dépile 3. Ordre obtenu : 1, 2, 3, soit l'ordre d'arrivée. Le 4 n'est pas encore ressorti, ce qui est normal : il est arrivé en dernier.
Quelle opération ne fait PAS partie de l'interface d'une pile ?
- A.Empiler un élément
- B.Accéder directement à l'élément d'indice iBonne réponse
- C.Dépiler l'élément du sommet
- D.Tester si la pile est vide
Réponse : B — Accéder directement à l'élément d'indice i
L'interface d'une pile se limite à : créer, tester si vide, empiler, dépiler (et parfois lire le sommet). L'accès direct par indice n'en fait pas partie — c'est précisément ce qui distingue une pile d'un tableau. Si un exercice te demande d'accéder au i-ème élément, c'est le signe que la pile n'est pas la bonne structure, ou qu'il faut dépiler jusque-là (et donc détruire la pile).
Qu'appelle-t-on une structure de données abstraite ?
- A.Un type prédéfini du langage Python
- B.Un fichier contenant des données
- C.Un algorithme de tri appliqué à des données
- D.Un ensemble de valeurs muni d'opérations, décrit indépendamment de son implémentationBonne réponse
Réponse : D — Un ensemble de valeurs muni d'opérations, décrit indépendamment de son implémentation
Une structure de données abstraite se définit par son INTERFACE : quelles valeurs elle contient et quelles opérations on peut faire dessus, avec leur signification. La façon dont c'est rangé en mémoire (tableau, liste chaînée…) relève de l'IMPLÉMENTATION, et n'entre pas dans la définition. C'est tout l'intérêt : on peut changer l'implémentation sans toucher au code qui utilise la structure.
Dans une liste chaînée, que contient chaque maillon ?
- A.Uniquement une valeur
- B.Une valeur et l'indice de cette valeur dans la liste
- C.Une valeur et une référence vers le maillon suivantBonne réponse
- D.Une valeur et le nombre total d'éléments de la liste
Réponse : C — Une valeur et une référence vers le maillon suivant
Un maillon (ou cellule) porte deux informations : la valeur stockée, et une référence vers le maillon suivant — None pour le dernier maillon. C'est ce chaînage qui remplace la contiguïté du tableau. Les maillons ne connaissent ni leur indice ni la longueur totale : c'est pour cela que calculer la longueur d'une liste chaînée sans compteur oblige à la parcourir entièrement.
On part d'une pile vide et on exécute empiler(3), empiler(7), empiler(5). Que renvoie ensuite depiler() ?
- A.5Bonne réponse
- B.3
- C.7
- D.Rien, la pile est vide
Réponse : A — 5
Après les trois empilements, la pile vaut fond [3, 7, 5] sommet : 5 est le dernier arrivé, il est donc au sommet. depiler() retire et renvoie toujours le sommet, donc 5. Répondre 3 serait appliquer le comportement d'une file (le premier entré). Et la pile n'est évidemment pas vide : elle contient trois éléments.
On part d'une file vide et on exécute enfiler(3), enfiler(7), enfiler(5). Que renvoie ensuite defiler() ?
- A.5
- B.7
- C.Une erreur : la file est vide
- D.3Bonne réponse
Réponse : D — 3
Une file respecte le FIFO : le premier entré est le premier sorti. Ici 3 est entré en premier, il se trouve donc en tête de file et c'est lui que defiler() renvoie. Répondre 5 serait confondre avec une pile (5 est le dernier arrivé). Compare bien avec la question précédente : mêmes valeurs, mêmes opérations, mais résultat opposé — c'est exactement ce qui distingue les deux structures.
Sur une pile vide, on exécute dans l'ordre : empiler(2), empiler(4), depiler(), empiler(6), depiler(). Quel est le contenu final de la pile ?
- A.La pile contient 2 puis 4
- B.La pile contient un seul élément : 2Bonne réponse
- C.La pile contient 2 puis 6
- D.La pile est vide
Réponse : B — La pile contient un seul élément : 2
Déroulons la trace : empiler(2) → [2] ; empiler(4) → [2, 4] ; depiler() retire 4 → [2] ; empiler(6) → [2, 6] ; depiler() retire 6 → [2]. Il reste donc un seul élément, la valeur 2. Le réflexe utile : écrire la pile après CHAQUE opération plutôt que de tenter de deviner. Chaque depiler() enlève le dernier élément écrit à droite.
S'entraîner sur ce chapitre
Ce chapitre compte 37 exercices corrigés dans l'application, avec le suivi de ta progression.
Commencer les exercices