Liste
Collection ordonnée d'éléments. On peut parcourir les éléments et, selon l'implémentation, accéder directement à un indice.
Terminale NSI • Structures de données • QCM /20
Listes, piles et files
Comprendre les structures linéaires, leurs opérations, leurs implémentations en Python et leurs coûts.
[ 3 | 7 | 12 ]
1. Trois structures linéaires à connaître
Les données sont organisées en séquence, mais les accès autorisés diffèrent.
Pile — LIFO
Last In, First Out : le dernier arrivé est le premier sorti. Exemple : historique d'annulation.
File — FIFO
First In, First Out : le premier arrivé est le premier sorti. Exemple : file d'attente d'impression.
Attention : une liste Python (
list) est un tableau dynamique. Une liste chaînée est une autre implémentation, constituée de maillons reliés entre eux. Ne pas confondre les deux.2. La pile : empiler et dépiler
On ne manipule que le sommet.
def creer_pile():
return []
def empiler(pile, valeur):
pile.append(valeur)
def depiler(pile):
assert len(pile) > 0, "Pile vide"
return pile.pop()
pile = creer_pile()
empiler(pile, 3)
empiler(pile, 7)
print(depiler(pile)) # 7Avec une liste Python, append et pop() sont respectivement en temps amorti O(1) et en temps O(1).
3. La file : enfiler et défiler
Insertion à l'arrière, retrait à l'avant.
from collections import deque
file = deque()
file.append(3) # Enfiler 3
file.append(7) # Enfiler 7
print(file.popleft()) # 3collections.deque permet append et popleft en O(1). À l'inverse, pop(0) sur une liste Python coûte O(n), car les éléments restants sont décalés.
4. Listes chaînées et maillons
Chaque maillon contient une valeur et une référence au suivant.
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
tete = Maillon(3, Maillon(7, Maillon(12)))
print(tete.suivant.valeur) # 7Insertion en tête : O(1). Recherche d'une valeur : O(n) au pire. Accès au maillon d'indice i : O(i), car il faut suivre les références successives.
5. Animation : manipule une pile ou une file
Ajoute des valeurs puis compare l'ordre des retraits.
Laboratoire interactif
Pile : sommet à droite. Le retrait se fait à droite.
Ajoute une première valeur.
6. Tableau des complexités
n représente le nombre d'éléments.
| Opération | Liste Python | Liste chaînée (tête connue) | deque Python |
|---|---|---|---|
| Accès par indice | O(1) | O(n) au pire | O(n) au pire |
| Ajouter en fin | O(1) amorti | O(n) sans référence à la queue | O(1) |
| Ajouter en tête | O(n) | O(1) | O(1) |
| Retirer en tête | O(n) | O(1) | O(1) |
| Rechercher une valeur | O(n) | O(n) | O(n) |
À retenir : le coût dépend de l'implémentation et des opérations demandées. Une pile et une file sont des types abstraits ; une liste Python, une liste chaînée ou une
deque peuvent servir à les réaliser.7. Exercices d'application
Réfléchis avant de regarder les réponses.
Exercice 1 — Pile : empiler 2, 5, 9 puis dépiler deux fois. Quelles valeurs sortent ?
9 puis 5. La pile contient encore [2].
Exercice 2 — File : enfiler A, B, C puis défiler deux fois. Quelles valeurs sortent ?
A puis B. Il reste C.
Exercice 3 — Choisir une structure : historique « Annuler » et traitement des clients par ordre d'arrivée.
Annuler : pile (LIFO). Clients : file (FIFO).
8. QCM de révision — 20 questions
Une seule bonne réponse par question. Note sur 20 et correction détaillée.