循環(huán)隊列多用于通信數(shù)據(jù)緩存中，尤其是在雙方設(shè)備接收數(shù)據(jù)與處理數(shù)據(jù)不同步的情況下，使用循環(huán)隊列先緩存通信數(shù)據(jù)，然后按照時間戳數(shù)據(jù)出隊作出相應(yīng)的處理，是一種比較合適的做法，在嵌入式編程中亦是如此。使用循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)可以實現(xiàn)上述功能，在一些低端的編程平臺手寫一個循環(huán)隊列既滿足了功能需求又不會開銷太多資源。

實現(xiàn)一個隊列可以使用順序表（數(shù)組）或鏈表實現(xiàn)。前者訪問速度塊，但是要占用連續(xù)的存儲空間，適用于內(nèi)存小但是速度要求較快的存儲場合。后者訪問速度慢但是基于鏈表式的結(jié)構(gòu)，可以使用碎片內(nèi)存，適用內(nèi)存大，速度慢的場合。本文面向的編程平臺是中低端MCU，時鐘主頻、RAM空間有限，因此選用順序表來實現(xiàn)循環(huán)隊列。關(guān)于順序表實現(xiàn)循環(huán)隊列的文章網(wǎng)上又很多，但是大多都基于一個明確的數(shù)據(jù)類型，如果在一個工程中兩種完全不同的數(shù)據(jù)類型都想使用循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)就會使得相同的代碼出現(xiàn)多次，導(dǎo)致代碼冗余。泛類型循環(huán)隊列的思想是將順序表中每個節(jié)點都看作一個uint8_t*類型的指針，在隊列初始化時，要傳入節(jié)點占用空間字節(jié)數(shù)，對每個節(jié)點malloc一個相應(yīng)的存儲空間，當(dāng)數(shù)據(jù)入隊時使用memcpy函數(shù)將源地址字節(jié)數(shù)拷貝到目標(biāo)地址即可，隊列數(shù)據(jù)表的結(jié)構(gòu)有點類似于哈希表，操作與定類型循環(huán)隊列類似。

隊列實現(xiàn)包含兩個文件：queue.h和queue.cqueue.h:使用枚舉自定義BOOL類型，C99標(biāo)準(zhǔn)之后包含stdbool.h可使用標(biāo)準(zhǔn)布爾型

(資料圖)

typedef enum {    FALSE,    TRUE } BOOL;

宏定義順序表中的節(jié)點類型

#define NODTETYPE uint8_t*

定義循環(huán)隊列結(jié)構(gòu)體

typedef struct Queue{uint32_t capacity;     // 隊列總?cè)萘縰int32_t size;         // 當(dāng)前隊列大小uint32_t front;        // 隊列頭節(jié)點uint32_t rear;         // 隊列尾節(jié)點  NODTETYPE* data;         //存儲節(jié)點的順序表} Queue;

接口函數(shù)

/* 初始化一個隊列 */BOOL init_queue(Queue *queue,uint32_t _capacity,uint32_t DataWidth);/* 數(shù)據(jù)入隊 */BOOL en_queue(Queue* _queue, NODTETYPE _data,uint32_t DataWidth);/*隊列判空*/BOOL isempty_queue(Queue* _queue);/*隊列判滿*/BOOL isfull_queue(Queue* _queue);/* 數(shù)據(jù)出隊 */NODTETYPE de_queue(Queue* _queue);/* 清空隊列 */void clear_queue(Queue* _queue);

queue.c隊列初始化，此處必須傳入節(jié)點的數(shù)據(jù)占用字節(jié)數(shù)DataWidth，注意可用隊列容量總是比傳入?yún)?shù)_capacity小一，因為要判空和判滿。

BOOL init_queue(Queue *queue,uint32_t _capacity,uint32_t DataWidth){    NODTETYPE *buff= (NODTETYPE*)malloc(_capacity*sizeof(NODTETYPE));    if(buff==NULL)        return FALSE;    for(int i=0;i<_capacity;i++)    {        NODTETYPE NodeTemp=(NODTETYPE)malloc(DataWidth);        if(NodeTemp==NULL)            return FALSE;        else            buff[i]=NodeTemp;    }    queue->data=buff;    queue->capacity = _capacity;    queue->size = 0;    queue->front = 0;      queue->rear = 0;    return TRUE;}

數(shù)據(jù)節(jié)點入隊

BOOL en_queue(Queue* _queue, NODTETYPE _data,uint32_t DataWidth){    BOOL isFull;    isFull = isfull_queue(_queue);    if (isFull == TRUE)    {        _queue->front = (_queue->front + 1) % _queue->capacity;    }    memcpy(_queue->data[_queue->rear], _data,DataWidth);    _queue->rear = (_queue->rear + 1) % _queue->capacity;    _queue->size++;    return isFull;}

數(shù)據(jù)節(jié)點出隊

NODTETYPE de_queue(Queue* _queue){    if (isempty_queue(_queue))         return NULL;    NODTETYPE result = _queue->data[_queue->front];    _queue->front = (_queue->front + 1) % _queue->capacity;    _queue->size--;    return result;}

隊列清空，但是不釋放存儲空間

void clear_queue(Queue* _queue){    _queue->front = _queue->rear = 0;    _queue->size = 0;}

隊列判空

BOOL isempty_queue(Queue* _queue){if (_queue->front == _queue->rear)return TRUE;elsereturn FALSE;}

隊列判滿

BOOL isfull_queue(Queue* _queue){if ((_queue->rear + 1) % _queue->capacity == _queue->front)return TRUE;elsereturn FALSE;}

隊列清空并釋放內(nèi)存

void release_queue(Queue* _queue){    for(int i=0;i<_queue->capacity;i++)    {        free(_queue->data[i]);        _queue->data[i]=NULL;    }    clear_queue(_queue);    free(_queue);    _queue = NULL;}

調(diào)用時入隊時，要先將節(jié)點數(shù)據(jù)類型強(qiáng)制轉(zhuǎn)化為uint8_t類型，傳入形參，出隊時獲取一個uint8_t的指針，然后強(qiáng)制轉(zhuǎn)換為定義的節(jié)點類型指針，之后就可以訪問到出隊節(jié)點的數(shù)據(jù)，舉例如下：

#include "queue.h"typedef  struct ClassTest  //定義測試類型{    uint8_t a;    uint16_t b;    uint32_t c;}ClassTest;int main(int argc, char *argv[]){    Queue queue1;    Queue queue2;    init_queue(&queue1,100,sizeof (ClassTest));    init_queue(&queue2,200,1);  //測試隊列2就用uint8_t    int i=0;    uint8_t queue1_node=0;    ClassTest queue2_node={0,0,0};    while(isfull_queue(&queue1)==FALSE)    {        queue1_node=i++;        en_queue(&queue1,&queue1_node,sizeof (queue1_node));    }    i=0;    while(isfull_queue(&queue2)==FALSE)    {        queue2_node.a=i++;        queue2_node.b=2*i;        en_queue(&queue2,(uint8_t*)(&queue2_node),sizeof (queue2_node));    }    while(isempty_queue(&queue1)==FALSE)    {        NODTETYPE node=de_queue(&queue1);        printf("%d;",*((uint8_t*)(node)));    }    while(isempty_queue(&queue2)==FALSE)    {        NODTETYPE node=de_queue(&queue2);        prinf("%d;",((ClassTest*)(node))->b);    }}

關(guān)鍵詞：