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

// 文件：config.h

//////////////////////////////////////////////////////////

#ifndef __CONFIG_H
#define __CONFIG_H
//这一段无需改动
//This segmentshould not be modified
#ifndef TRUE
#define TRUE1
#endif

#ifndef FALSE
#define FALSE 0
#endif

typedef unsigned charuint8;
typedef signedcharint8;
typedef unsigned short uint16;
typedef signedshort int16;
typedef unsigned intuint32;
typedef signedintint32;
typedef floatfp32;

＃i nclude "FIFOQUEUE.h"

#endif

//////////////////////////////////////////////////////////

// 文件：FIFOQUEUE.h

//////////////////////////////////////////////////////////

#ifndef _FIFOQUEUE_H
#define _FIFOQUEUE_H

#define ElemTypeuint8

#define QueueSize20 //fifo队列的大小
#define QueueFull0 //fifo满置0
#define QueueEmpty1 //FIFO空置1
#define QueueOperateOk 2 //队列操作完成 赋值为2

struct FifoQueue
{
uint16 front; //队列头
uint16 rear; //队列尾
uint16 count; //队列计数
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

//////////////////////////////////////////////////////////

＃i nclude "config.h"

//Queue Init
void QueueInit(struct FifoQueue *Queue)
{
Queue->front = Queue->rear;//初始化时队列头队列首相连
Queue->count = 0; //队列计数为0
}

// Queue In
uint8 QueueIn(struct FifoQueue *Queue,ElemType sdat) //数据进入队列
{
if((Queue->front == Queue->rear) && (Queue->count == QueueSize))
{// full //判断如果队列满了
return QueueFull; //返回队列满的标志
}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

//////////////////////////////////////////////////////////

＃i nclude
＃i nclude "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);
}

队列是一种先进先出（first infirst out，缩写为FIFO）的线性表。它只允许在标的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端则称为对头（front）（排队买票，窗口一端叫对头，末尾进队叫队尾）。

用链表表示的队列称为链队列，如图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