cours sur les structures de données

INF 421 Luc MarangetUn peu de listesPiles, FilesLuc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/1D´etour : les sacsLes piles et les files sont des cas particuliers des sacs.Les op´erations suivantes sont d´efinies sur les sacs◮ Le sac est-il vide ?◮ Ranger dans le sac,◮ Sortir un ´el´ement du sac (un des ´el´ements rang´es au pr´ealable).Le sac typique (en style objet) :class Bag {...Bag () { ... }boolean isEmpty() { ... }void put(Object o) { ... }Object get() { ... }}Remarquer : Le sac est une structure mutable.2Les piles et les filesPiles et files sont des sacs munis de r`egles suppl´ementaires reliantles sorties et les entr´ees :◮ Les piles sont des sacs ( ´evang´eliques ) : dernier entr´e, premiersorti (ou LIFO : Last In, First Out).⊲ En ce cas, put se dit souvent push (empiler) et get se ditsouvent pop (d´epiler).◮ Les files sont des sacs ´egalitaires : premier entr´e, premier sorti(ou FIFO : First In, First Out).⊲ En ce cas, put peut se dire enfiler et get peut se dire d´efiler.3La pile4La pile5La file6La file7`A quoi c¸a sert ?La file est la structure la plus intuitive.La file sert par exemple, dans un syst`eme d’exploitation, a` servirdes demandes d’impression dans l’ordre.◮ Il y a une file spool des fichiers `a imprimer.◮ Chaque utilisateur demande l’impression d’un fichier f par :...spool.put(f)...◮ Tandis qu’un acteur quelconque du syst`eme d’exploitationex´ecute ...