單片機(jī)的FIFO(先入先出)循環(huán)隊(duì)列實(shí)現(xiàn)
掃描二維碼
隨時(shí)隨地手機(jī)看文章
//////////////////////////////////////////////////////////
// 文件：config.h
//////////////////////////////////////////////////////////
#ifndef __CONFIG_H
#define __CONFIG_H
//這一段無(wú)需改動(dòng)
//This segment should not be modified
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
typedef unsigned char uint8;
typedef signed char int8;
typedef unsigned short uint16;
typedef signed short int16;
typedef unsigned int uint32;
typedef signed int int32;
typedef float fp32;
#include "FIFOQUEUE.h"
#endif
//////////////////////////////////////////////////////////
// 文件：FIFOQUEUE.h
//////////////////////////////////////////////////////////
#ifndef _FIFOQUEUE_H
#define _FIFOQUEUE_H
#define ElemType uint8
#define QueueSize 20 //fifo隊(duì)列的大小
#define QueueFull 0 //fifo滿置0
#define QueueEmpty 1 //FIFO空置1
#define QueueOperateOk 2 //隊(duì)列操作完成 賦值為2
struct FifoQueue
{
uint16 front; //隊(duì)列頭
uint16 rear; //隊(duì)列尾
uint16 count; //隊(duì)列計(jì)數(shù)
ElemType dat[QueueSize];
};
//Queue Initalize
extern void QueueInit(struct FifoQueue *Queue);
// Queue In
extern uint8 QueueIn(struct FifoQueue *Queue,ElemType sdat);
// Queue Out
extern uint8 QueueOut(struct FifoQueue *Queue,ElemType *sdat);
#endif
//////////////////////////////////////////////////////////
// 文件：FIFOQUEUE.C
//////////////////////////////////////////////////////////
#include "config.h"
//Queue Init
void QueueInit(struct FifoQueue *Queue)
{
Queue->front = Queue->rear;//初始化時(shí)隊(duì)列頭隊(duì)列首相連
Queue->count = 0; //隊(duì)列計(jì)數(shù)為0
}
// Queue In
uint8 QueueIn(struct FifoQueue *Queue,ElemType sdat) //數(shù)據(jù)進(jìn)入隊(duì)列
{
if((Queue->front == Queue->rear) && (Queue->count == QueueSize))
{ // full //判斷如果隊(duì)列滿了
return QueueFull; //返回隊(duì)列滿的標(biāo)志
}else
{ // in
Queue->dat[Queue->rear] = sdat;
Queue->rear = (Queue->rear + 1) % QueueSize;
Queue->count = Queue->count + 1;
return QueueOperateOk;
}
}
// Queue Out
uint8 QueueOut(struct FifoQueue *Queue,ElemType *sdat)
{
if((Queue->front == Queue->rear) && (Queue->count == 0))
{ // empty
return QueueEmpty;
}else
{ // out
*sdat = Queue->dat[Queue->front];
Queue->front = (Queue->front + 1) % QueueSize;
Queue->count = Queue->count - 1;
return QueueOperateOk;
}
}
//////////////////////////////////////////////////////////
// 文件：Main.C
//////////////////////////////////////////////////////////
#include
#include "config.h"
void main(void)
{
struct FifoQueue MyQueue;
ElemType sh;
uint8 i;
QueueInit(&MyQueue);
while(1)
{
for(i = 0;i < 30;i++)
{
if(QueueIn(&MyQueue,i) == QueueFull) break;
}
for(i = 0;i < 30;i++)
{
if(QueueOut(&MyQueue,&sh) == QueueEmpty) break;
}
}
while(1);
}
隊(duì)列是一種先進(jìn)先出（first infirst out，縮寫(xiě)為FIFO）的線性表。它只允許在標(biāo)的一端進(jìn)行插入，而在另一端刪除元素。這和我們?nèi)粘Ｉ钪械呐抨?duì)是一致的，最早進(jìn)入隊(duì)列的元素最早離開(kāi)。在隊(duì)列中，允許插入的一端叫做隊(duì)尾（rear），允許刪除的一端則稱(chēng)為對(duì)頭（front）（排隊(duì)買(mǎi)票，窗口一端叫對(duì)頭，末尾進(jìn)隊(duì)叫隊(duì)尾）。
用鏈表表示的隊(duì)列稱(chēng)為鏈隊(duì)列，如圖2所示。一個(gè)鏈隊(duì)列顯然需要兩個(gè)分別指向?qū)︻^和隊(duì)尾的指針（分別稱(chēng)為頭指針和尾指針）才能唯一確定。這里，和線性表的單鏈表一樣，為了操作方便起見(jiàn)，我們先給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，并令頭指針和尾指針均指向頭結(jié)點(diǎn)，如圖3(a)所示。鏈隊(duì)列的操作即為單鏈表的插入和刪除操作的特殊情況，只是尚需修改尾指針或頭指針，圖3(b)~(d)展示了這兩種操作進(jìn)行時(shí)指針變化的情況。下面給出鏈隊(duì)列類(lèi)型的模塊說(shuō)明。
圖２ 鏈隊(duì)列示意圖
圖３ 隊(duì)列運(yùn)算指針變化情況 (a)空隊(duì)列；(b)元素x入隊(duì)；(c)元素y入隊(duì)；(d)元素x出隊(duì)
//=====ADT Queue的表示與實(shí)現(xiàn)=====
//-----單鏈隊(duì)列——隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-----
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front; //對(duì)頭指針
QueuePtr rear; //隊(duì)尾指針
}LinkQueue；
//-----基本操作的函數(shù)原型說(shuō)明（幾個(gè)易錯(cuò)?？嫉模?----
Status GetHead(LinkQueue Q, QElemType &e)
//若隊(duì)列不空，則用e返回Q的對(duì)頭元素，并返回OK；否則返回ERROR
Status EnQueue(LinkQueue &Q, QElemType e)
//插入元素e為Q的新的隊(duì)尾元素
Status DeQueue(LinkQueue &Q, QElemType &e)
//若隊(duì)列不空，則刪除Q的對(duì)頭元素，用e返回其值，并返回OK；
//否則返回ERROR
和順序棧相類(lèi)似，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個(gè)指針front和rear分別之時(shí)隊(duì)列頭元素和隊(duì)列尾元素的位置。為了在C語(yǔ)言中描述方便起見(jiàn)，在此我們約定：初始化建空隊(duì)列時(shí)，令front=rear=0，每當(dāng)插入新的隊(duì)列尾元素時(shí)，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時(shí)，“頭指針增1”。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置。如圖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)時(shí)不可再繼續(xù)插入新的隊(duì)尾元素，否則會(huì)因數(shù)組越界而遭致程序代碼被破壞。然而此時(shí)又不宜如順序棧那樣，進(jìn)行存儲(chǔ)再分配擴(kuò)大數(shù)組空間，因?yàn)殛?duì)列的實(shí)際可用空間并未占滿。一個(gè)較巧妙的辦法是將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，如圖5所示，稱(chēng)之為循環(huán)隊(duì)列。指針和隊(duì)列元素之間關(guān)系不變，如圖6(a)所示循環(huán)隊(duì)列中，隊(duì)列頭元素時(shí)J3，隊(duì)列尾元素是J5，之后J6、J7和J8相繼插入，則隊(duì)列空間均被占滿，如圖6(b)所示，此時(shí)Q.front=Q.rear；反之，若J3、J4和J5相繼從圖6(a)的隊(duì)列中刪除，使隊(duì)列呈“空”的狀態(tài)，如圖6(c)所示。此時(shí)亦存在關(guān)系式Q.front=Q.rear，由此可見(jiàn)，只憑等式Q.front=Q.rear無(wú)法判別隊(duì)列空間是“空”還是“滿”?？捎蓛煞N處理方法：其一是另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是“空”還是“滿”；其二是少用一個(gè)元素空間，約定以“隊(duì)列頭指針在隊(duì)列尾指針的下一位置（指環(huán)狀的下一位置）上”作為隊(duì)列呈“滿”狀態(tài)的標(biāo)志。
圖5 循環(huán)隊(duì)列示意圖
圖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ì)列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度；若用戶無(wú)法預(yù)估所用隊(duì)列的最大長(zhǎng)度，則宜采用鏈隊(duì)列。循環(huán)隊(duì)列類(lèi)型的模塊說(shuō)明如下：
//-----循環(huán)隊(duì)列———隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)-----
#define MAXQSIZE 100
下載文檔
