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

用鏈表表示的隊(duì)列稱為鏈隊(duì)列，如圖2所示。一個鏈隊(duì)列顯然需要兩個分別指向?qū)︻^和隊(duì)尾的指針（分別稱為頭指針和尾指針）才能唯一確定。這里，和線性表的單鏈表一樣，為了操作方便起見，我們先給鏈隊(duì)列添加一個頭結(jié)點(diǎn)，并令頭指針和尾指針均指向頭結(jié)點(diǎn)，如圖3(a)所示。鏈隊(duì)列的操作即為單鏈表的插入和刪除操作的特殊情況，只是尚需修改尾指針或頭指針，圖3(b)~(d)展示了這兩種操作進(jìn)行時指針變化的情況。下面給出鏈隊(duì)列類型的模塊說明。

圖２ 鏈隊(duì)列示意圖圖３ 隊(duì)列運(yùn)算指針變化情況 (a)空隊(duì)列；(b)元素x入隊(duì)；(c)元素y入隊(duì)；(d)元素x出隊(duì)

//=====ADT Queue的表示與實(shí)現(xiàn)=====
//-----單鏈隊(duì)列——隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)-----
typedef struct QNode{
QElemTypedata;
struct QNode*next;
}QNode, *QueuePtr;

typedef struct{
QueuePtr front;//對頭指針
QueuePtr rear;//隊(duì)尾指針
}LinkQueue；

//-----基本操作的函數(shù)原型說明（幾個易錯?？嫉模?----
Status GetHead(LinkQueue Q, QElemType &e)
//若隊(duì)列不空，則用e返回Q的對頭元素，并返回OK；否則返回ERROR
Status EnQueue(LinkQueue &Q, QElemType e)
//插入元素e為Q的新的隊(duì)尾元素
Status DeQueue(LinkQueue &Q, QElemType &e)
//若隊(duì)列不空，則刪除Q的對頭元素，用e返回其值，并返回OK；
//否則返回ERROR

和順序棧相類似，在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個指針front和rear分別之時隊(duì)列頭元素和隊(duì)列尾元素的位置。為了在C語言中描述方便起見，在此我們約定：初始化建空隊(duì)列時，令front=rear=0，每當(dāng)插入新的隊(duì)列尾元素時，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時，“頭指針增1”。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個位置。如圖4所示。

圖4 頭、尾指針和隊(duì)列中元素之間的關(guān)系

(a)空隊(duì)列；(b)J1、J2和J3相繼入隊(duì)列；(c)J1和J2相繼被刪除；(d)J4、J5和J6相繼插入隊(duì)列之后J3及J4被刪除

假設(shè)當(dāng)前為隊(duì)列分配的最大空間為6，則當(dāng)隊(duì)列處于圖4(d)的狀態(tài)時不可再繼續(xù)插入新的隊(duì)尾元素，否則會因數(shù)組越界而遭致程序代碼被破壞。然而此時又不宜如順序棧那樣，進(jìn)行存儲再分配擴(kuò)大數(shù)組空間，因?yàn)殛?duì)列的實(shí)際可用空間并未占滿。一個較巧妙的辦法是將順序隊(duì)列臆造為一個環(huán)狀的空間，如圖5所示，稱之為循環(huán)隊(duì)列。指針和隊(duì)列元素之間關(guān)系不變，如圖6(a)所示循環(huán)隊(duì)列中，隊(duì)列頭元素時J3，隊(duì)列尾元素是J5，之后J6、J7和J8相繼插入，則隊(duì)列空間均被占滿，如圖6(b)所示，此時Q.front=Q.rear；反之，若J3、J4和J5相繼從圖6(a)的隊(duì)列中刪除，使隊(duì)列呈“空”的狀態(tài)，如圖6(c)所示。此時亦存在關(guān)系式Q.front=Q.rear，由此可見，只憑等式Q.front=Q.rear無法判別隊(duì)列空間是“空”還是“滿”?？捎蓛煞N處理方法：其一是另設(shè)一個標(biāo)志位以區(qū)別隊(duì)列是“空”還是“滿”；其二是少用一個元素空間，約定以“隊(duì)列頭指針在隊(duì)列尾指針的下一位置（指環(huán)狀的下一位置）上”作為隊(duì)列呈“滿”狀態(tài)的標(biāo)志。

圖5 循環(huán)隊(duì)列示意圖