Chapitre 3 - Révision : Structures de données linéaires

---

1. Interface vs implémentation

• Interface : ensemble des opérations offertes (le « quoi »)
• Implémentation : réalisation concrète en mémoire (le « comment »)
• Plusieurs implémentations peuvent offrir la même interface avec des performances différentes

---

2. Structures linéaires

Structure	Principe	Ajout	Retrait	Accès
Liste chaînée	Maillons chaînés par des références	O(1) en tête	O(1) en tête	O(n) par index
Pile (LIFO)	Dernier entré, premier sorti	O(1) empiler	O(1) dépiler	O(1) sommet
File (FIFO)	Premier entré, premier sorti	O(1) enfiler	O(1) défiler (amorti)	-
Dictionnaire	Clé → valeur	O(1)	O(1)	O(1) par clé

Pile : historique, Ctrl+Z, appels de fonctions, parenthèses.

File : impression, ordonnancement, parcours en largeur.