單片機(jī)的FIFO(先入先出)循環(huán)隊(duì)列實(shí)現(xiàn)

圖6 循環(huán)隊(duì)列的頭尾指針 (a)一般情況；(b)隊(duì)列滿時(shí)；(c)空隊(duì)列；

從上述分析可見(jiàn)，在C語(yǔ)言中不能用動(dòng)態(tài)分配的一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列。如果用戶(hù)的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度；若用戶(hù)無(wú)法預(yù)估所用隊(duì)列的最大長(zhǎng)度，則宜采用鏈隊(duì)列。循環(huán)隊(duì)列類(lèi)型的模塊說(shuō)明如下：

//-----循環(huán)隊(duì)列———隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)-----
#define MAXQSIZE 100//最大隊(duì)列長(zhǎng)度
typedef struct{
QElemType *base;//初始化的動(dòng)態(tài)非配存儲(chǔ)空間
int front;//頭指針，若隊(duì)列不空，指向隊(duì)列的頭元素
int rear;//尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置
}SqQueue;

//-----循環(huán)隊(duì)列的基本操作的算法描述-----
Status InitQueue(SqQueue &Q){
//構(gòu)造一個(gè)空隊(duì)列Q
Q.base=(ElemType *)malloc(MAXQSIZE*sizeof(ElemType));
if(!Q.base) exit (OVERFLOW);// 存儲(chǔ)分配失敗
Q.front=Q.rear=0;
return OK;
}

int QueueLength(SqQueue Q){
//返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度
return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;
}

Status EnQueue(SqQueue &Q, QElemType e){
//插入元素e為Q的新的隊(duì)尾元素
if((Q.rear+1) % MAXQSIZE == Q.front) return ERROR;// 隊(duì)列滿
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1) % MAXQSIZE;
return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e){
//若隊(duì)列不空，則刪除Q的對(duì)頭元素，用e返回其值，并返回OK；
//否則返回ERROR
if(Q.front==Q.rear)return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1) % MAXQSIZE;
return OK;
}