麻烦各位来看下斐波那契算法（使用栈，非递归）解决方法

麻烦各位来看下斐波那契算法（使用栈，非递归）
代码如下 

是用栈帮助求解斐波那契数的非递归算法

哪位高手能帮我简单解释下该算法的意图 感激不尽

struct Node
{
 long n; //记忆走过的n
 int tag; //区分左右递归的标志，向左递归 tag=1；向右递归 tag=2；
};

long Fibnacci(long n) //用栈求解Fib(n)的值
{
 Stack<Node>S;Node *w;long sum=0;
 do
 {
  while (n>1){w->n=n;w->tag=1;S.push(w);n--;} //push()函数表示压栈操作
  sum = sum+n;
  while(S.IsEmpty()==false)
  {
  S.Pop(w);
  if (w->tag == 1)
  {w->tag=2;S.push(w);n=w->n-2;break;}
  }
 }while (S.IsEmpty()==false);
 return sum;
}


[解决办法]
不知道你的Stack类是怎么写的，反正看着你这句就有问题了
Stack<Node>S;Node *w;long sum=0;
 do
 {
while (n>1){w->n=n;w->tag=1;S.push(w);n--;}
w 没有初始化，然后压入了w是什么意思呢？
其实这个栈实现很简单，就是f(n) = f(n-1)+f(n-2);
分别对f(n-1)和f(n-2)进行栈操作一直到f(0),f(1)的时候就开始弹出，弹一个就累加1，效率低到死了
据不完全统计应该是3/2的N次方

C/C++ code

#include <iostream>#include <vector>using namespace std;long fibnacci(long n){    vector<int> ivec(n+1);    ivec[0] = 1;    ivec[1] = 1;    for(int i = 2;i <= n;i++)        ivec[i] = ivec[i - 1] + ivec[i - 2];    return ivec[n];}int main(){    long sum = fibnacci(5);    cout << sum << endl;}