單片機的FIFO(先入先出)循環(huán)隊列實現(xiàn)

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

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

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

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

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

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

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