Piles, files et tables de hachage

Cours · OCaml (option informatique), chapitre 8 · prépas MPSI et MP, option informatique · le début du chapitre, la suite sur Adloun

Une pile, où le dernier arrivé sort le premier, et une file, où le premier arrivé sort le premier.

8.1 Introduction et motivation

On a souvent besoin de structures mutables prêtes à l'emploi pour stocker des éléments et les retrouver selon une discipline précise : « le dernier arrivé d'abord » (une pile), « le premier arrivé d'abord » (une file), ou « par clé » (une table de hachage). OCaml les fournit dans sa bibliothèque standard, via les modules Stack, Queue et Hashtbl. Ce chapitre en présente l'interface — la dernière brique du sous-ensemble du programme.

iRemarqueNiveau A.2

Ces modules sont utilisables après rappel ; on en donne les signatures. On pourrait réimplémenter une pile à la main (un enregistrement à champ mutable contenu : 'a list, cf. chapitre 7) ; l'intérêt des modules est de fournir ces structures efficaces et testées, sans réinventer la roue.

8.2 Les piles : dernier entré, premier sorti (LIFO)

Une pile (stack) fonctionne comme une pile d'assiettes : on ajoute et on retire par le même bout (le sommet). Le dernier élément empilé est le premier dépilé — discipline LIFO (Last In, First Out).

iRemarqueRappel du module Stack (A.2)

Stack.create () : unit -> 'a Stack.t — une pile vide ;
Stack.is_empty p : 'a Stack.t -> bool ;
Stack.push x p : 'a -> 'a Stack.t -> unit — empile x au sommet ;
Stack.pop p : 'a Stack.t -> 'a — retire et renvoie le sommet (lève Stack.Empty si vide).

Exercices du chapitre

La suite du cours · Tous les exercices du chapitre