用栈实现斐波那契数列

栈是一种后进先出的数据结构，可以用来实现递归函数的非递归计算。下面是用栈实现斐波那契数列的方法：
1. 定义一个结构体node，包含两个成员变量value和dir，分别表示当前计算的斐波那契数列的项数和计算方向（向左或向右）。
2. 定义一个栈s，用来存储node结构体。
3. 初始化栈s，将第n项的node结构体压入栈中。
4. 当栈不为空时，取出栈顶元素w，如果w.value等于0，则将0加入sum中；如果w.value等于1，则将1加入sum中；否则，如果w.dir等于1，则将w.dir改为2，将w结构体重新压入栈中，并将n设为w.value-2；如果w.dir等于2，则将sum加上前两项的和，并弹出栈顶元素。
5. 当栈为空时，返回sum。

代码如下：

int StackFib(int n) {
    struct node {
        int value;
        int dir;
    };
    stack<node> s;
    int sum = 0;
    while (1) {
        while (1) {
            node w;
            w.value = n;
            w.dir = 1;
            s.push(w);
            n--;
            if (n < 0) break;
        }
        while (!s.empty()) {
            node w = s.top();
            s.pop();
            if (w.value == 0) sum += 0;
            else if (w.value == 1) sum += 1;
            else if (w.value != 0 && w.value != 1 && w.dir == 1) {
                w.dir = 2;
                s.push(w);
                n = w.value-2;
                break;
            }
        }
        if (s.empty()) break;
    }
    return sum;
}