Piles

On a vu au §10 que les blocs d'activation des fonctions étaient des blocs de mémoire << empilés >> les uns sur les autres, le dernier empilé étant le premier retiré (en anglais last in, first out ou LIFO), comme une vulgaire pile d'assiettes. La figure 12 montre le fonctionnement d'une pile ainsi que sa représentation.

Les quatre opérations sur une pile sont : ajouter un élément au sommet de la pile (ou empiler), lire la valeur se trouvant au sommet d'une pile non-vide, tester si une pile est vide, retirer l'élément au sommet de la pile (ou dépiler).

En anglais, << pile >> se dit stack et les opérations portent respectivement les noms push, top, is_empty_stack, pop.

On va représenter les piles à l'aide de la structure suivante, le type stack_data étant le type des éléments, que l'on ne spécifie pas ici :

typedef ... stack_data;
const int MAX=100;
struct stack {
  int height;
  stack_data content[MAX];
};

Si p est une pile, son contenu est donné par

p.content[0], ..., p.content[$h-1$],

quand p.height vaut $h>0$ ; $h=0$ caractérise la pile vide. Les opérations sont implémentées facilement, les paramètres étant passés par référence :

void mk_empty_stack(stack& p) {
  p.height = 0;
}

bool is_empty_stack(const stack& p) {
  return p.height == 0;
}

void push(const stack_data& x, stack& p) {
  p.content[p.height] = x;
  ++ p.height;
}

stack_data top(const stack& p) {
  return p.content[p.height - 1];
}

stack_data pop(stack& p) {
  -- p.height;
  return p.content[p.height];
}

Ces fonctions ne sont pas entièrement satisfaisantes, car elles ne traitent pas des cas d'erreur.