#include<stdio.h>
#include<stdlib.h>
#if 0
#define nmax 1024
typedef struct { int t[nmax]; unsigned deb, fin, n; } pile;

#if 0

#if 0
#define modnmax %nmax
#else
#define modnmax &(nmax-1)
#endif

void init(pile *p)
{ if(nmax&(nmax-1)) printf("nmax n'est pas une puissance de 2\n"), exit(1);
  p->deb=p->fin=p->n=0;
}
void empile(pile *p, int x)
{ p->t[p->fin++ modnmax]=x;
  if(++p->n>nmax) printf("débordement de la pile\n"), exit(1);
}
void enfile(pile *p, int x)
{ p->t[--p->deb modnmax]=x;
  if(++p->n>nmax) printf("débordement de la pile\n"), exit(1);
}
int depile(pile *p)
{ if(!p->n--) printf("pile vide\n"), exit(1);
  return p->t[--p->fin modnmax];
}

#else

void init(pile *p)
{ p->deb=p->fin=p->n=0;
}
void empile(pile *p, int x)
{ p->t[p->fin++]=x;
  if(p->fin==nmax) p->fin=0;
  if(++p->n>nmax) printf("débordement de la pile\n"), exit(1);
}
void enfile(pile *p, int x)
{ if(!p->deb) p->deb=nmax;
  p->t[--p->deb]=x;
  if(++p->n>nmax) printf("débordement de la pile\n"), exit(1);
}
int depile(pile *p)
{ if(!p->n--) printf("pile vide\n"), exit(1);
  if(!p->fin) p->fin=nmax;
  return p->t[--p->fin];
}

#endif

void vide(pile *p) { init(p); }

#else

typedef struct maillon *liste;
struct maillon { int clef; liste next; } ;
typedef struct { liste deb, fin; unsigned n; } pile;

liste libre=0;

void init(pile *p)
{ p->deb=0;
  p->n=0;
}
#if 1
liste nouv(int clef, liste next)
{ liste l=malloc(sizeof(*l));
  l->clef=clef;
  l->next=next;
  return l;
}
int depile(pile *p)
{ if(!p->n--) printf("pile vide\n"), exit(1);
  liste l=p->deb;
  int x=l->clef;
  p->deb=l->next;
  free(l);
  return x;
}
#else
liste nouv(int clef, liste next)
{ liste l=libre;
  if(l) libre=l->next;
  else  l=malloc(sizeof(*l));
  l->clef=clef;
  l->next=next;
  return l;
}
int depile(pile *p)
{ if(!p->n--) printf("pile vide\n"), exit(1);
  liste l=p->deb; p->deb=l->next;  // on détache le premier maillon de la pile
  l->next=libre; libre=l;            // pour le dans la liste LIBRE
  return l->clef;
}
#endif
void empile(pile *p, int x)
{ p->deb=nouv(x,p->deb);
  if(!p->n++) p->fin=p->deb;
}
void enfile(pile *p, int x)
{ liste q=nouv(x,0);
  if(p->n++) p->fin->next=q;
  else       p->deb      =q;
  p->fin=q;
}
void vide(pile *p) { while(p->n) depile(p); }
void libere(liste l) { if(l) libere(l->next), free(l); }
void libereite(liste l)
{ while(l)
  { liste a=l;
    l=a->next;
    free(a);
  }
}
void videlibre() { libere(libre), libre=0; }

#endif

int main()
{ pile p;
  init(&p);
  int i, j;

  for(i=0;i<100;i++) enfile(&p,i*i*i);
  while(p.n>1) i=depile(&p), j=depile(&p), enfile(&p,i>j?i-j:j-i);
  printf("%d\n",depile(&p));

  for(i=0;i<100;i++) empile(&p,i*i*i);
  while(p.n>1) i=depile(&p), j=depile(&p), empile(&p,i>j?i-j:j-i);
  printf("%d\n",depile(&p));

  return 0;
}