///////////////////
//FIB数列的栈实现//
///////////////////
#include"LinkedStack.h"
#include<stdlib.h>
struct Node
{
    long n;
    int tag;
};

long Fibnacci(long n)                           
{                                           
    LinkedStack<Node> S;                   
    Node *w=new Node;    //分配动态内存,如果不分配则程序错误                   
    if(w==NULL)                               
    {                                       
        cerr<<"分配内存失误!"<<endl;   
        exit(1);                           
    }                                       
    long sum=0;                               
    do
    {
        while(n>1)          //不断的将结构体压入栈
        {
            w->n=n;
            w->tag=1;
            S.Push(*w);
            n--;
        }
        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;
}