Contraintes

Une pile est une structure de données récursive sur laquelle on peut faire deux choses : empiler et dépiler. Empiler ajouter un élément en haut de la pile, dépiler, prend l’élément en haut de la pile (principe LIFO : Last In, First Out)

Une file fonctionne sur le principe FIFO (First In, First Out). On peut enfiler un élément à la fin de la file, et “défiler” une élément au début.

Exercices

  1. Écrire une fonction calculant la hauteur d’une pile.

  2. La pile est utile pour parcourir des données sous forme arborescente, par exemple les expressions arithmétiques. Par exemple, supposons que l’on dispose d’une expression bien parenthésée, si on parcourt l’expression, en empilant quand on rencontre une parenthèse ouvrante et dépilant quand on rencontre une parenthèse fermante, à la fin, la pile sera vide et à aucun moment, on aura essayé de dépiler une pile vide.

    Écrire une fonction qui étant donnée une liste de 0 et de 1 (représentant respectivement les parenthèses ouvrantes et fermantes) dit si l’expression est bien parenthésée.