The basic stack algorithm

clipped from www.yucs.org Here is a simple C implementation of the multi-stack algorithm. unsigned int f(unsigned int); const int K=10; /* The number of stacks */ const int stackSize=50; int multiStack(unsigned int x0) { struct { unsigned int val; int t; } stack[K][stackSize]; unsigned int x=x0; int h[K]; /* The stack sizes */ int i, k, time=0; for (i=0; i<K; i++) h[i]=0; while(1) { k = x % K; for (i=h[k]-1; i>=0; i--) if (stack[k][i].val<=x) break; if (i>=0 && stack[k][i].val==x) return time - stack[k][i].t; stack[k][i+1].val=x; stack[k][i+1].t=time; h[k]=i+2; assert(h[k]<stackSize); x=f(x); time++; } }