Listes, piles et files

Dans ce chapitre, nous parlerons des listes des piles et des files. Nous verrons leurs interfaces et leurs implémentations. Ce sont des structures de données linéaires. Nous reparlerons également des dictionnaires afin de les comparer aux structures linéaires.

Parties du programme abordées

Contenus	Capacités attendues	Commentaires
Structures de données interface et implémentation.	Spécifier une structure de données par son interface. Distinguer interface et implémentation. Écrire plusieurs implémentations d’une même structure de données.	L’abstraction des structures de données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles).
Listes, piles, files : structures linéaires. Dictionnaires, index et clé.	Distinguer des structures par le jeu des méthodes qui les caractérisent. Choisir une structure de données adaptée à la situation à modéliser. Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire.	On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files.