单片机的FIFO(先入先出)循环队列实现

图6 循环队列的头尾指针 (a)一般情况；(b)队列满时；(c)空队列；

从上述分析可见，在C语言中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。循环队列类型的模块说明如下：

//-----循环队列———队列的顺序存储结构-----
#define MAXQSIZE 100//最大队列长度
typedef struct{
QElemType *base;//初始化的动态非配存储空间
int front;//头指针，若队列不空，指向队列的头元素
int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

//-----循环队列的基本操作的算法描述-----
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的元素个数，即队列的长度
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;
}