#include #include #include "pile.h" #include "buffer.h" #define TAILLE_MIN 1024 #define AGRANDISSEMENT 1 #define PERTE_MAXI 2 /* On utilise ici le type buffer (tableau de taille variable). Pour conserver une bonne complexite (amortie) il ne faut pas utiliser realloc trop souvent. Aussi on choisit d'utiliser une suite de taille croissant exponentiellement. On reduit la taille du tableau lorsque le rapport entre cette taille et nb_elements parait trop important : ici 2 puissance PERTE_MAXI. Afin de conserver une bonne complexite il est imperatif que PERTE_MAXI > AGRANDISSEMENT */ struct pile { size_t nb_elements; buffer zone; }; pile pil_creer (void) { pile p = (pile) malloc (sizeof (struct pile)); p->nb_elements = 0; p->zone = buf_create (TAILLE_MIN); return p; } void pil_detruire (pile p) { assert (pil_est_vide (p)); buf_free (p->zone); free (p); } int pil_est_vide (pile p) { return (p->nb_elements == 0); } void pil_empiler (pile p, void *info) { if (p->nb_elements == p->zone->size) buf_resize (p->zone, p->zone->size << AGRANDISSEMENT); p->zone->elements[p->nb_elements++] = info; } void * pil_depiler (pile p) { void *valeur; size_t seuil = p->zone->size >> PERTE_MAXI; assert (!pil_est_vide (p)); valeur = p->zone->elements[--p->nb_elements]; if (p->nb_elements > TAILLE_MIN && p->nb_elements < seuil) buf_resize (p->zone, (TAILLE_MIN > seuil) ? TAILLE_MIN : seuil); return valeur; } void * pil_valeur_sommet (pile p) { assert (!pil_est_vide (p)); return p->zone->elements[p->nb_elements-1]; }