首页 > 其他分享 >基于C语言的泛类型循环队列

基于C语言的泛类型循环队列

时间:2023-06-22 22:44:31浏览次数:38  
标签:node Queue capacity 队列 C语言 queue 循环 NODTETYPE

循环队列多用于通信数据缓存中,尤其是在双方设备接收数据与处理数据不同步的情况下,使用循环队列先缓存通信数据,然后按照时间戳数据出队作出相应的处理,是一种比较合适的做法,在嵌入式编程中亦是如此。使用循环队列的数据结构可以实现上述功能,在一些低端的编程平台手写一个循环队列既满足了功能需求又不会开销太多资源。

设计思想

实现一个队列可以使用顺序表(数组)或链表实现。前者访问速度块,但是要占用连续的存储空间,适用于内存小但是速度要求较快的存储场合。后者访问速度慢但是基于链表式的结构,可以使用碎片内存,适用内存大,速度慢的场合。本文面向的编程平台是中低端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);
    }
}

标签:node,Queue,capacity,队列,C语言,queue,循环,NODTETYPE
From: https://www.cnblogs.com/JXL-Blogs/p/17498508.html

相关文章

  • 输入,选择,while循环
    输入,选择,while循环用户交互Scanner之前我们学的基本语法中我们并没有实现程序和人的交互,但是Java给我们提供了这样一个工具类,我们可以获取用户的输入。java.util.Scanner是Java5的新特征,我们可以通过Scanner类来获取用户的输入。基本语法:scanners=newScanner(System......
  • 学生信息管理系统-C语言版
    环境操作系统:Windows11编译器:GCC源代码函数较多,自定义头文件,主文件引入即可头文件:functions.h头文件所对应的源文件:functions.c主文件:学生信息管理系统.cfunctions.h#ifndef_FUNCTINOS_H_#define_FUNCTINOS_H_#defineMAX_STU100typedefstructStudents{ cha......
  • C语言三子棋项目(顺序逻辑-小白学习笔记)
    首先要确定游戏的基本框架简易来说,由进入游戏--->选择菜单--->进入游戏三部分组成应用在c语言项目中,我们通过功能来对文件进行区分,主函数main()内进入游戏,通过test函数加入我们的菜单,但这里meau()菜单选项我们不希望执行一次,因为如果玩家选择错误,将会导致程序无法进行。这里通过dowh......
  • C语言 大小端转换(16位)c51,ARM
    //C++#include<arpa/inet.h>uint32_thtonl(uint32_tbuffer);//32位uint16_thtons(uint16_tbuffer);//16位Linux上,无符号c++版 #define__SWP16(A)((((uint16)(A)&0xff00)>>8)|\(((uint16)(A)&0x00ff)......
  • 01-C语言基础语法
    目录一.C语言发展史二.数据类型三.常量和变量四.字符串和转义字符五.选择语句六.循环语句七.函数一.C语言发展史1963年ALGOL60作为C语言最早的模型,剑桥大学将其发展成为CPL(CombinedProgramingLanguage)。1967年,剑桥大学的MatinRichards对CPL语言进行了简......
  • 数组越界导致的死循环,以及对存储方式的思考
    一、bug有如下代码:intmain(){ inti=0; intarr[10]={1,2,3,4,5,6,7,8,9,10}; for(i=0;i<=12;i++){ printf("hehe\n"); arr[i]=0; } return0;}按正常思路,该代码会打印13个hehe,并把arr数组里的10个元素改为0,但为什么计算机会死循环打印无数个hehe?二、原......
  • Android,两个互相影响的EditText如何避免死循环
    简单来说,是一个类似如下的需求:两个EditText,假设名字分别是et1和et2;et1的值*一个数字,假设是4500=et2的值;当et1的值发生变化时,et2的值也发生变化,et2的值发生变化时,et1的值也发生变化,用过用简单的 TextWatcher就会发生死循环,如何避免,下面是这个例子代码的最核心部分,简单来说就......
  • celery笔记五之消息队列的介绍
    本文首发于公众号:Hunter后端原文链接:celery笔记五之消息队列的介绍前面我们介绍过task的处理方式,将task发送到队列queue,然后worker从queue中一个个的获取task进行处理。task的队列queue可以是多个,处理task的worker也可以是多个,worker可以处理任意queue......
  • 【数据结构与算法】用队列实现栈
    ......
  • 图的遍历——DFS, BFS(邻接矩阵,邻接表)——C语言描述
    图的遍历——DFS,BFS(邻接矩阵,邻接表)——C语言描述目录图的遍历——DFS,BFS(邻接矩阵,邻接表)——C语言描述0测试用例框架1图的深度优先遍历(DFS)1.1邻接矩阵(1)数据结构(2)代码(3)测试用例(4)打印结果1.2邻接表(1)数据结构(2)代码(3)测试用例(4)结果2图的广度度优先遍历(BFS)2.1队列(1)数据结构......