基于C语言的泛类型循环队列 - 惊晓漏

基于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);
    }
}