#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
typedef struct { int *t, n, nmax; } pile;
enum {egale,plus1,fois2} meth=egale;
pile *creation_pile()
{ pile *p=malloc(sizeof(*p));
  p->t=0;
  p->n=p->nmax=0;
  return p;
}
void destruction_pile(pile *p)
{ free(p->t); free(p);
}
void empile(pile *p, int x)
{ if(p->n==p->nmax)
  { switch(meth)
    { case egale:
      case plus1: p->nmax++; break;
      case fois2: p->nmax+=p->nmax?:100;
    }
    p->t=realloc(p->t,p->nmax*sizeof(int));
  }
  p->t[p->n++]=x;
}
int depile(pile *p)
{ if(!p->n) return 0;  // pile vide
  int x=p->t[--p->n];
  if(meth==egale) p->t=realloc(p->t,--p->nmax*sizeof(int));
  return x;
}
void tache()
{ pile *p=creation_pile();
  for(int i=0;i<1000;i++) if(rand()%2) empile(p,i); else depile(p);
  destruction_pile(p);
}
void moyenne(int n)
{ double s=0,ss=0;
  for(int i=0;i<n;i++)
  { int a=clock();
    tache();
    double d=clock()-a;  // durée=heure de fin - heure de début
    s+=d;
    ss+=d*d;
  }
  s/=n;
  ss/=n;
  ss-=s*s;
  ss=ss*n/(n-1);
  printf("meth=%d n=%d moyenne=%f variance=%e\n",meth,n,s,sqrt(ss));
}
int main()
{ srand(time(0));
  for(meth=0;meth<3;meth++) moyenne(20);
  return 0;
}