Définitions, contrats et coûts
Choisir une organisation selon les accès et les retraits.
| Notion | À retenir |
|---|---|
| Tableau dynamique | Accès indicé Θ(1) ; insertion initiale Θ(n) ; ajout final amorti Θ(1). |
| Liste chaînée | Accès au rang O(n) ; modifier un lien connu Θ(1), hors allocation. |
| Pile / file | LIFO / FIFO ; préciser structure de stockage et comportement à vide. |
Vérifier sur un exemple
Une file FIFO
Importez deque avant de l’utiliser pour retirer en tête sans décaler toute une liste.
Python
Python # fifo_queue.py
from collections import deque
queue = deque(["first", "second"])
queue.append("third")
print(queue.popleft())
print(list(queue))
# Expected output:
# first
# ['second', 'third']Résultat expliqué. popleft retire le plus ancien élément ; les accès aux extrémités de deque sont O(1) dans le modèle usuel.
Erreur à éviter. list.pop(0) décale les autres éléments : Θ(n). Un deque ne fournit pas un accès indicé uniforme Θ(1).
Faut-il une pile ou une file pour annuler la dernière action ?
Une pile : l’ordre LIFO retire d’abord la dernière action ajoutée.