使用循环队列求斐波那契数列的前n+1项

使用循环队列求斐波那契数列的前n+1项
另一篇“k阶斐波那契数列的非递归算法”使用栈求斐波那契数列的第n项。本篇也是处于练习的目的，使用循环队列求斐波那契数列的前n+1项，算法结束时队列中保存了数列的最后k+1项。下贴出实现，读者可参照“k阶斐波那契数列的非递归算法”，自行对比。
//cyclequeue.h
typedef struct CYCLEQUEUE{
int *pEle;
int front;
int rear;
int size;
}Queue;
void initQueue(Queue &q, int size);
int enQueue(Queue &q, int num);
int deQueue(Queue &q);
int getFront(const Queue &q);
int getRear(const Queue &q);
void calc(int n, int k);
void destroy(Queue &q);
//cyclequeue.cpp
#include
#include "cyclequeue.h"
using namespace std;
void initQueue(Queue &q, int size){
q.pEle = (int*)malloc(sizeof(int)*(size+1));
//空余一个空间用于判定队列满
if(q.pEle == NULL){
cout<<"Malloc failed!\n";
exit(-1);
}
q.front = q.rear =0;
q.size = size+1;
}

//入队
int enQueue(Queue &q, int num){
if((q.rear+1)%q.size == q.front){
cout<<"Queue overflow!\n";
return -1;
}
q.pEle[q.rear] = num;
q.rear = (q.rear+1)%q.size;
return 1;
}
//出队
int deQueue(Queue &q){
if(q.front == q.rear){
cout<<"Queue empty!\n";
return -1;
}
int ret = q.pEle[q.front];
q.front = (q.front+1)%q.size;
return ret;
}
int getFront(const Queue &q){
if(q.front == q.rear)
return -1;
return q.pEle[q.front];
}
int getRear(const Queue &q){
if(q.front == q.rear)
return -1;
return q.pEle[(q.rear-1+q.size)%q.size];
}
void destroy(Queue &q){
free(q.pEle);
q.pEle=NULL;
q.size=0;
cout<<"Queue destroyed!\n";
}
void calc(int n, int k){
if(k<2){
cout<<"k<2 unexpected!\n";
return;
}
int i, tmp;
Queue q;
initQueue(q, k+1);//循环数列中最多保留最后k+1项(0到k)

for(i=0; i<=k-2 && i<=n; ++i){
cout<<"0 ";
enQueue(q, 0);
}
for(i=k-1; i<=k && i<=n; ++i){
cout<<"1 ";
enQueue(q, 1);
}
for(i=k+1; i<=n; ++i){
tmp = 2*getRear(q)-getFront(q);//f(m+1)=2f(m)-f(m-k);
cout<deQueue(q);
enQueue(q, tmp);
}
cout<<"\n";
destroy(q);
}
//main.cpp
#include
using namespace std;
#include "cyclequeue.h"
int main(int argc, char *argv[])
{
calc(20, 4);
system("PAUSE");
return true;
}