Stack Algorithm

Suppose we are given a function f that maps some domain D into itself. Given an initial element x0 from D, define the infinite sequence x1=f(x0), x2=f(x1), etc. Our basic algorithm is as follows: Keep a stack of pairs (xi, i), where, at all times, both the i's and the xi's in the stack form strictly increasing sequences. The stack is initially empty. At each step j, pop from the stack all entries (xi, i) where xi>xj. If an xi=xj is found in the stack, we are done; then the cycle length is equal to j-i. Otherwise, push (xj, j) on top of the stack and continue. This algorithm always halts on the smallest value of the sequence's cycle xmin, on the second occurrence of this value: Once xmin is added to the stack the first time it appears, it is never removed. Therefore, the algorithm will halt when it encounters xmin for the second time. On the other hand, any other cycle value is greater than xmin, so it will be removed by xmin before it has a chance to appear again. Implement this Stack Algorithm using C++ ## Deliverables Include a makefile ## Platform Windows or UNIX