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

用链表表示的队列称为链队列，如图2所示。一个链队列显然需要两个分别指向对头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里，和线性表的单链表一样，为了操作方便起见，我们先给链队列添加一个头结点，并令头指针和尾指针均指向头结点，如图3(a)所示。链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针，图3(b)~(d)展示了这两种操作进行时指针变化的情况。下面给出链队列类型的模块说明。

图２ 链队列示意图图３ 队列运算指针变化情况 (a)空队列；(b)元素x入队；(c)元素y入队；(d)元素x出队

//=====ADT Queue的表示与实现=====
//-----单链队列——队列的链式存储结构-----
typedef struct QNode{
QElemTypedata;
struct QNode*next;
}QNode, *QueuePtr;

typedef struct{
QueuePtr front;//对头指针
QueuePtr rear;//队尾指针
}LinkQueue；

//-----基本操作的函数原型说明（几个易错常考的）-----
Status GetHead(LinkQueue Q, QElemType &e)
//若队列不空，则用e返回Q的对头元素，并返回OK；否则返回ERROR
Status EnQueue(LinkQueue &Q, QElemType e)
//插入元素e为Q的新的队尾元素
Status DeQueue(LinkQueue &Q, QElemType &e)
//若队列不空，则删除Q的对头元素，用e返回其值，并返回OK；
//否则返回ERROR

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别之时队列头元素和队列尾元素的位置。为了在C语言中描述方便起见，在此我们约定：初始化建空队列时，令front=rear=0，每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。如图4所示。

图4 头、尾指针和队列中元素之间的关系

(a)空队列；(b)J1、J2和J3相继入队列；(c)J1和J2相继被删除；(d)J4、J5和J6相继插入队列之后J3及J4被删除

假设当前为队列分配的最大空间为6，则当队列处于图4(d)的状态时不可再继续插入新的队尾元素，否则会因数组越界而遭致程序代码被破坏。然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列臆造为一个环状的空间，如图5所示，称之为循环队列。指针和队列元素之间关系不变，如图6(a)所示循环队列中，队列头元素时J3，队列尾元素是J5，之后J6、J7和J8相继插入，则队列空间均被占满，如图6(b)所示，此时Q.front=Q.rear；反之，若J3、J4和J5相继从图6(a)的队列中删除，使队列呈“空”的状态，如图6(c)所示。此时亦存在关系式Q.front=Q.rear，由此可见，只凭等式Q.front=Q.rear无法判别队列空间是“空”还是“满”。可由两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈“满”状态的标志。

图5 循环队列示意图