基於C語言的泛型別迴圈佇列

迴圈佇列多用於通訊資料快取中，尤其是在雙方裝置接收資料與處理資料不同步的情況下，使用迴圈佇列先快取通訊資料，然後按照時間戳資料出隊作出相應的處理，是一種比較合適的做法，在嵌入式程式設計中亦是如此。使用迴圈佇列的資料結構可以實現上述功能，在一些低端的程式設計平臺手寫一個迴圈佇列既滿足了功能需求又不會開銷太多資源。

設計思想

實現一個佇列可以使用順序表（陣列）或連結串列實現。前者存取速度塊，但是要佔用連續的儲存空間，適用於記憶體小但是速度要求較快的儲存場合。後者存取速度慢但是基於連結串列式的結構，可以使用碎片記憶體，適用記憶體大，速度慢的場合。本文面向的程式設計平臺是中低端MCU，時鐘主頻、RAM空間有限，因此選用順序表來實現迴圈佇列。
關於順序表實現迴圈佇列的文章網上又很多，但是大多都基於一個明確的資料型別，如果在一個工程中兩種完全不同的資料型別都想使用迴圈佇列的資料結構就會使得相同的程式碼出現多次，導致程式碼冗餘。
泛型別迴圈佇列的思想是將順序表中每個節點都看作一個uint8_t*型別的指標，在佇列初始化時，要傳入節點佔用空間位元組數，對每個節點malloc一個相應的儲存空間，當資料入隊時使用memcpy函數將源地址位元組數拷貝到目標地址即可，佇列資料表的結構有點類似於雜湊表，操作與定型別迴圈佇列類似。

程式碼實現

佇列實現包含兩個檔案：queue.h和queue.c
queue.h:
使用列舉自定義BOOL型別，C99標準之後包含stdbool.h可使用標準布林型

 typedef enum
 {
    FALSE,
    TRUE
 } BOOL;

宏定義順序表中的節點型別

#define NODTETYPE uint8_t*

定義迴圈佇列結構體

typedef struct Queue
{
	uint32_t capacity;     // 佇列總容量
	uint32_t size;         // 當前佇列大小
	uint32_t front;        // 佇列頭節點
	uint32_t rear;         // 佇列尾節點
  NODTETYPE* data;         //儲存節點的順序表
} Queue;

介面函數

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

queue.c
佇列初始化，此處必須傳入節點的資料佔用位元組數DataWidth，注意可用佇列容量總是比傳入引數_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;
}

資料節點入隊

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;
}

資料節點出隊

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;
	else
		return FALSE;
}

佇列判滿

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

佇列清空並釋放記憶體

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;
}

呼叫時入隊時，要先將節點資料型別強制轉化為uint8_t型別，傳入形參，出隊時獲取一個uint8_t的指標，然後強制轉換為定義的節點型別指標，之後就可以存取到出隊節點的資料，舉例如下：

#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);
    }
}