Piles

     

On a vu au § 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  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 :

#define MAX 100
typedef struct {
  int height;
  stack_data content[MAX];
} stack;

  
Figure: Fonctionnement et représentation d'une pile

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, par référence :

void mk_empty_stack(stack *p) {
  p->height = 0;
}

int 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.