Au programme de ce chapitre
- I. La liste Python : indexation et coût des opérations
- II. La pile : principe LIFO et utilisations
- III. La file : principe FIFO et implémentation avec deque
- Méthodes et pièges à éviter
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
La définition à retenir
Définition Une liste est une séquence ordonnée et modifiable d'éléments, numérotés à partir de 0. En Python, une liste est représentée en mémoire par un tableau de références contiguës : connaître l'indice d'un élément suffit pour y accéder directement, sans parcourir les éléments qui le précèdent.
🔒 Infographie récapitulative du chapitreIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3 :
>>> pile = []
>>> pile.append("a")
>>> pile.append("b")
>>> pile.append("c")
>>> pile
['a', 'b', 'c']
>>> pile.pop()
'c'
>>> pile
['a', 'b']pop() ne demande aucun décalage : c'est une opération en O(1). Retirer le premier élément avec pop(0) obligerait au contraire à décaler tous les éléments restants d'un rang vers la gauche, en O(n).L'essentiel à retenir
- Pile : LIFO (empiler / dépiler au sommet).
- File : FIFO (enfiler en queue / défiler en tête).
- Pile pour revenir en arrière ; file pour traiter dans l'ordre d'arrivée.
- Les indices d'une liste commencent à 0 (de 0 à n−1).
Les erreurs fréquentes à éviter
Piège — confondre pile et file. Pile = LIFO (dernier arrivé servi en premier) ; file = FIFO (premier arrivé servi en premier). Une image : pile d'assiettes vs file d'attente.
Piège — les indices commencent à 0. Le premier élément d'une liste est à l'indice 0 ; une liste de n éléments va de l'indice 0 à n−1.
Attention Une liste Python n'est pas une bonne représentation d'une file : défiler avec
t.pop(0) coûte O(n), car tous les éléments restants doivent être décalés. On utilise plutôt une file double du module collections, la classe deque, dont les opérations append (enfiler à droite) et popleft (défiler à gauche) coûtent toutes deux O(1).L'astuce du prof
Astuce Pour une file efficace, évite pop(0) sur une liste : utilise
collections.deque (retrait en tête en O(1)).Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1 — Résultat d'une pile
On empile 1, puis 2, puis 3, puis on dépile une fois. Quel élément sort ? Que reste-t-il au sommet ?
Voir la correction
Il sort 3 (dernier entré). Au sommet il reste 2.
Exercice 2 — Résultat d'une file
On enfile A, B, C puis on défile une fois. Quel élément sort ?
Voir la correction
Il sort A (premier entré, premier sorti).