一种数组环形队列的数据结构
概述
一种更好的计算队尾指针的方法。
队尾指针新算法
一个新的计算队尾指针的公式：
设模拟环形队列的线性表长度是n，队头指针为head，队尾指针为tail，则每增加一条记录，就可以用一下方法计算新的队尾指针： tail = (tail + 1) % n
环形队列示意图
思考
但是，我在移植到8266的代码时，发现有点问题。
第一，head和tail应该是存储该数组的下标而不是一个指向该数组元素的指针。如果tail是指针，那么 tail本质上是一个内存地址，*tail是指向该数组的某一元素。那么这算式tail = (tail + 1) % n其实是对某数组元素的内存地址+1，然后在用n求余。 所以head和tail应该是保存该数组的下标，而不是指向该数组元素的指针。
第二，由于原先的代码，其队尾指针总是指向最后一个入队元素的下一个元素，而《算》给出的队列，队尾指针总是指向最后一个入队的元素。如上图，一个n=12的环形队列，原先的代码tail是指向第8个，《算》是指向第7个，由于我是在8266的示例代码上修改的，所以《算》给出的队尾指针算法需要调整一下：
//元素入队之后tail++; //tail指向最后一个入队的下一个元素tail=tail % n; //重新计算tail的数值123
新的数据结构
那么我就开始定义新的数据结构了，原先的数据结构是这样的
typedef struct{ uint8_t* p_o; //指向原点的指针，用来数组首地址 uint8_t* volatile p_r; //读取指针，相当于head uint8_t* volatile p_w; //写入指针，相到于tail volatile int32_t fill_cnt; //队列计数 int32_t size; //缓冲区的大小}ringbuf;
新的数据结构：
typedef struct { char *buf; //指向队列数组的指针 unsigned int length; //数组长度 unsigned int head; //队头，存储数组下标 unsigned int tail; //队尾，存储数组下标 int fill_cnt; //队列计数}ringbuf;
判断是否空队列
一开始，本来想用if(head==tail)来判断队列是否为空的，但是由于tail保存的是入队元素的下一个数组下标，当队列填满的时候，tail的下标正好等于head，所以不能通过if(head==tail)来判断队列是否为空，
完整代码
下面是完整的数组环形队列代码，运行环境是vs2015，主函数里进行了简单的测试：
// ringbuf.cpp : 定义控制台应用程序的入口点。//#include stdafx.htypedef struct { char *buf; //指向队列数组的指针 unsigned int length; //长度 unsigned int head; //队头 unsigned int tail; //队尾 int fill_cnt; //队列计数}ringbuf;int ringbuf_init(ringbuf* r, char array[], size_t len){ if (len buf = array; r->length = len; r->fill_cnt = 0; r->head = r->tail = 0; return true;}int ringbuf_put(ringbuf* r, char data){ //当tail+1等于head时，说明队列已满 if (r->fill_cnt >= r->length) { printf(buf full!); return false; // 如果缓冲区满了，则返回错误 } r->buf[r->tail] = data; r->tail++; r->fill_cnt++; //计算tail是否超出数组范围，如果超出则自动切换到0 r->tail = r->tail % r->length; return true;}int ringbuf_get(ringbuf* r, char *c, unsigned int length){ //当tail等于head时，说明队列空 if (r->fill_cntlength长度数据 if (length > r->length) { length = r->length; } int i; for (i = 0; ifill_cnt--; *c = r->buf[r->head++]; // 返回数据给*c *c++; //计算head自加后的下标是否超出数组范围，如果超出则自动切换到0 r->head = r->head % r->length; } return true;}#define buf_len 5ringbuf buff;char buf[buf_len];int main(){ ringbuf_init(&buff, buf, sizeof(buf)); printf(1、逐个读取数据测试); int length = 5; for (int i = 0; i < length; i++) { ringbuf_put(&buff, i); } char data; length = 5; for (int i = 0; i < length; i++) { ringbuf_get(&buff, &data, 1); //从buff读取1个字节 printf(每次读取1个字节：buf pop : %d , data); //打印该字节 } printf(2、一次性读取测试); length = 5; for (int i = 0; i < length; i++) { ringbuf_put(&buff, '1' + i); } char data2[11] = { 0 }; ringbuf_get(&buff, data2, 5); printf(一次性读取5个字节：buf pop : %s , data2); //打印该字节 printf(3、放入超过缓冲区长度（buf_len+1）数据测试：); length = buf_len + 1; for (int i = 0; i < length; i++){ ringbuf_put(&buff, '1'+i); } char data3[buf_len+1] = { 0 }; ringbuf_get(&buff, data3, buf_len + 1); printf(一次性读取（buf_len+1）个字节测试：buf pop : %s , data3); //打印该字节 //4、测试读取空缓冲区 printf(4、读取空缓冲区测试：); ringbuf_get(&buff, data3, 2); //从buff读取2个字节 return 0;}
控制台打印信息如下：
1、逐个读取数据测试
每次读取1个字节：buf pop : 0
每次读取1个字节：buf pop : 1
每次读取1个字节：buf pop : 2
每次读取1个字节：buf pop : 3
每次读取1个字节：buf pop : 4
2、一次性读取测试
一次性读取5个字节：buf pop : 12345
3、放入超过缓冲区长度（buf_len+1）数据测试：
buf full!
一次性读取（buf_len+1）个字节测试：buf pop : 12345
4、读取空缓冲区测试：
buf empty!
请按任意键继续…
后话
由于存在几种队尾指向元素的方式，以上代码是还可以在修改优化一下的。
《算》的代码是不需要考虑队列是否满了，他只需要直接覆盖旧的元素即可，我的需求是需要判断队列是否填满，以免旧的元素被覆盖。
小型前移式无人叉车助力企业实现智能化生产管理
数字时代云成本越来越高，企业IT负责人们该如何选择弹性云服务器呢？
IGBT技术发展历史 IGBT内部结构及工作原理
封装测试业的规模占比下降趋势较大?
性价比超高的红米Pro：5.5英寸屏+双镜头 仅1099
一种数组环形队列的数据结构
AI概念股领涨两市，人工智能迎来风口
实战经验 | 如何选择 S2-LP 的外部晶体
中控智慧科技考勤机X10简介
英伟达新技术：机器人就可以模仿,这究竟是一种什么技术？
传感器在物联网上的应用
一加6曝光与官宣：都是为价格提升做铺垫？
“钧嵌传感”电机传感器可保证全转速状态1°精度，已拿下四千万订单
世平集团的完整太阳能绿色节能解决方案
基本RS触发器的四种状态
web程序员应具备哪些知识
华为荣耀V9月底发布 同时亮相的还有这款新机！
日产汽车将停止生产电动车及混合动力汽车电池
稀奇古怪动作的“ Disney USB”产品
最新！12省智慧灯杆项目落地案例独家盘点！
一种更好的计算队尾指针的方法。
队尾指针新算法
一个新的计算队尾指针的公式：
设模拟环形队列的线性表长度是n，队头指针为head，队尾指针为tail，则每增加一条记录，就可以用一下方法计算新的队尾指针： tail = (tail + 1) % n
环形队列示意图
思考
但是，我在移植到8266的代码时，发现有点问题。
第一，head和tail应该是存储该数组的下标而不是一个指向该数组元素的指针。如果tail是指针，那么 tail本质上是一个内存地址，*tail是指向该数组的某一元素。那么这算式tail = (tail + 1) % n其实是对某数组元素的内存地址+1，然后在用n求余。 所以head和tail应该是保存该数组的下标，而不是指向该数组元素的指针。
第二，由于原先的代码，其队尾指针总是指向最后一个入队元素的下一个元素，而《算》给出的队列，队尾指针总是指向最后一个入队的元素。如上图，一个n=12的环形队列，原先的代码tail是指向第8个，《算》是指向第7个，由于我是在8266的示例代码上修改的，所以《算》给出的队尾指针算法需要调整一下：
//元素入队之后tail++; //tail指向最后一个入队的下一个元素tail=tail % n; //重新计算tail的数值123
新的数据结构
那么我就开始定义新的数据结构了，原先的数据结构是这样的
typedef struct{ uint8_t* p_o; //指向原点的指针，用来数组首地址 uint8_t* volatile p_r; //读取指针，相当于head uint8_t* volatile p_w; //写入指针，相到于tail volatile int32_t fill_cnt; //队列计数 int32_t size; //缓冲区的大小}ringbuf;
新的数据结构：
typedef struct { char *buf; //指向队列数组的指针 unsigned int length; //数组长度 unsigned int head; //队头，存储数组下标 unsigned int tail; //队尾，存储数组下标 int fill_cnt; //队列计数}ringbuf;
判断是否空队列
一开始，本来想用if(head==tail)来判断队列是否为空的，但是由于tail保存的是入队元素的下一个数组下标，当队列填满的时候，tail的下标正好等于head，所以不能通过if(head==tail)来判断队列是否为空，
完整代码
下面是完整的数组环形队列代码，运行环境是vs2015，主函数里进行了简单的测试：
// ringbuf.cpp : 定义控制台应用程序的入口点。//#include stdafx.htypedef struct { char *buf; //指向队列数组的指针 unsigned int length; //长度 unsigned int head; //队头 unsigned int tail; //队尾 int fill_cnt; //队列计数}ringbuf;int ringbuf_init(ringbuf* r, char array[], size_t len){ if (len buf = array; r->length = len; r->fill_cnt = 0; r->head = r->tail = 0; return true;}int ringbuf_put(ringbuf* r, char data){ //当tail+1等于head时，说明队列已满 if (r->fill_cnt >= r->length) { printf(buf full!); return false; // 如果缓冲区满了，则返回错误 } r->buf[r->tail] = data; r->tail++; r->fill_cnt++; //计算tail是否超出数组范围，如果超出则自动切换到0 r->tail = r->tail % r->length; return true;}int ringbuf_get(ringbuf* r, char *c, unsigned int length){ //当tail等于head时，说明队列空 if (r->fill_cntlength长度数据 if (length > r->length) { length = r->length; } int i; for (i = 0; ifill_cnt--; *c = r->buf[r->head++]; // 返回数据给*c *c++; //计算head自加后的下标是否超出数组范围，如果超出则自动切换到0 r->head = r->head % r->length; } return true;}#define buf_len 5ringbuf buff;char buf[buf_len];int main(){ ringbuf_init(&buff, buf, sizeof(buf)); printf(1、逐个读取数据测试); int length = 5; for (int i = 0; i < length; i++) { ringbuf_put(&buff, i); } char data; length = 5; for (int i = 0; i < length; i++) { ringbuf_get(&buff, &data, 1); //从buff读取1个字节 printf(每次读取1个字节：buf pop : %d , data); //打印该字节 } printf(2、一次性读取测试); length = 5; for (int i = 0; i < length; i++) { ringbuf_put(&buff, '1' + i); } char data2[11] = { 0 }; ringbuf_get(&buff, data2, 5); printf(一次性读取5个字节：buf pop : %s , data2); //打印该字节 printf(3、放入超过缓冲区长度（buf_len+1）数据测试：); length = buf_len + 1; for (int i = 0; i < length; i++){ ringbuf_put(&buff, '1'+i); } char data3[buf_len+1] = { 0 }; ringbuf_get(&buff, data3, buf_len + 1); printf(一次性读取（buf_len+1）个字节测试：buf pop : %s , data3); //打印该字节 //4、测试读取空缓冲区 printf(4、读取空缓冲区测试：); ringbuf_get(&buff, data3, 2); //从buff读取2个字节 return 0;}
控制台打印信息如下：
1、逐个读取数据测试
每次读取1个字节：buf pop : 0
每次读取1个字节：buf pop : 1
每次读取1个字节：buf pop : 2
每次读取1个字节：buf pop : 3
每次读取1个字节：buf pop : 4
2、一次性读取测试
一次性读取5个字节：buf pop : 12345
3、放入超过缓冲区长度（buf_len+1）数据测试：
buf full!
一次性读取（buf_len+1）个字节测试：buf pop : 12345
4、读取空缓冲区测试：
buf empty!
请按任意键继续…
后话
由于存在几种队尾指向元素的方式，以上代码是还可以在修改优化一下的。
《算》的代码是不需要考虑队列是否满了，他只需要直接覆盖旧的元素即可，我的需求是需要判断队列是否填满，以免旧的元素被覆盖。
小型前移式无人叉车助力企业实现智能化生产管理
数字时代云成本越来越高，企业IT负责人们该如何选择弹性云服务器呢？
IGBT技术发展历史 IGBT内部结构及工作原理
封装测试业的规模占比下降趋势较大?
性价比超高的红米Pro：5.5英寸屏+双镜头 仅1099
一种数组环形队列的数据结构
AI概念股领涨两市，人工智能迎来风口
实战经验 | 如何选择 S2-LP 的外部晶体
中控智慧科技考勤机X10简介
英伟达新技术：机器人就可以模仿,这究竟是一种什么技术？
传感器在物联网上的应用
一加6曝光与官宣：都是为价格提升做铺垫？
“钧嵌传感”电机传感器可保证全转速状态1°精度，已拿下四千万订单
世平集团的完整太阳能绿色节能解决方案
基本RS触发器的四种状态
web程序员应具备哪些知识
华为荣耀V9月底发布 同时亮相的还有这款新机！
日产汽车将停止生产电动车及混合动力汽车电池
稀奇古怪动作的“ Disney USB”产品
最新！12省智慧灯杆项目落地案例独家盘点！