Piles et Files


Parmi les très nombreuses structures de données utilisées par les informaticiens, nous avons étudié auparavant les tableaux/listes, les dictionnaires et les tuples. Plus récemment, la structure de liste chaînée nous a montré comment implémenter une structure plus exotique à laide dune interface fonctionnelle ou bien par lintermédiaire de la POO.

À présent, nous allons étudier deux structures de données dont lusage en algorithme est extrêmement fréquent: il sagit des piles et des files.

Nous nous pencherons sur différentes implémentations possibles de ces deux structures (à la fois en cours et en TP), tout en étudiant les coûts en exécution (complexité) des choix effectués. Enfin, nous verrons en TP quelques algorithmes utilisant ces structures (et la liste est loin dêtre exhaustive).