一种数组环形队列的数据结构
概述
一种更好的计算队尾指针的方法。
队尾指针新算法
一个新的计算队尾指针的公式：
设vwin 环形队列的线性表长度是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
新的数据结构
那么我就开始定义新的数据结构了，原先的数据结构是这样的
typedefstruct{
uint8_t*p_o;//指向原点的指针，用来数组首地址
uint8_t*volatilep_r;//读取指针，相当于head
uint8_t*volatilep_w;//写入指针，相到于tail
volatileint32_tfill_cnt;//队列计数
int32_tsize;//缓冲区的大小
}RINGBUF;
新的数据结构：
typedefstruct{
char*buf;//指向队列数组的指针
unsignedintlength;//数组长度
unsignedinthead;//队头，存储数组下标
unsignedinttail;//队尾，存储数组下标
intfill_cnt;//队列计数
}RINGBUF;
判断是否空队列
一开始，本来想用if(head==tail)来判断队列是否为空的，但是由于tail保存的是入队元素的下一个数组下标，当队列填满的时候，tail的下标正好等于head，所以不能通过if(head==tail)来判断队列是否为空，
完整代码
下面是完整的数组环形队列代码，运行环境是VS2015，主函数里进行了简单的测试：
// RingBuf.cpp :定义控制台应用程序的入口点。
//
#include"stdafx.h"
typedefstruct{
char*buf;//指向队列数组的指针
unsignedintlength;//长度
unsignedinthead;//队头
unsignedinttail;//队尾
intfill_cnt;//队列计数
}RINGBUF;
intRINGBUF_Init(RINGBUF*r,chararray[],size_tlen)
{
if(len<2 || array==NULL){
return false;
}
r->buf=array;
r->length=len;
r->fill_cnt=0;
r->head=r->tail=0;
returntrue;
}
intRINGBUF_Put(RINGBUF*r,chardata)
{
//当tail+1等于head时，说明队列已满
if(r->fill_cnt>=r->length){
printf("BUFFULL!
");
returnfalse;//如果缓冲区满了，则返回错误
}
r->buf[r->tail]=data;
r->tail++;
r->fill_cnt++;
//计算tail是否超出数组范围，如果超出则自动切换到0
r->tail=r->tail%r->length;
returntrue;
}
intRINGBUF_Get(RINGBUF*r,char*c,unsignedintlength)
{
//当tail等于head时，说明队列空
if(r->fill_cnt<=0) {
printf("BUF EMPTY!
");
return false;
}
//最多只能读取r->length长度数据
if(length>r->length){
length=r->length;
}
inti;
for(i=0;ifill_cnt--;
*c=r->buf[r->head++];//返回数据给*c
*c++;
//计算head自加后的下标是否超出数组范围，如果超出则自动切换到0
r->head=r->head%r->length;
}
returntrue;
}
#defineBUF_LEN5
RINGBUFBUFF;
charbuf[BUF_LEN];
intmain()
{
RINGBUF_Init(&BUFF,buf,sizeof(buf));
printf("1、逐个读取数据测试
");
intlength=5;
for(inti=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!
请按任意键继续…
后话
由于存在几种队尾指向元素的方式，以上代码是还可以在修改优化一下的。
《算》的代码是不需要考虑队列是否满了，他只需要直接覆盖旧的元素即可，我的需求是需要判断队列是否填满，以免旧的元素被覆盖。
审核编辑：汤梓红
-
算法
+关注
关注
23文章
4607浏览量
92820 -
指针
+关注
关注
1文章
480浏览量
70549 -
代码
+关注
关注
30文章
4779浏览量
68516 -
数据结构
+关注
关注
3文章
573浏览量
40121 -
数组
+关注
关注
1文章
417浏览量
25939
原文标题：一种数组环形队列的数据结构
文章出处：【微信号：技术让梦想更伟大，微信公众号：技术让梦想更伟大】欢迎添加关注！文章转载请注明出处。
发布评论请先 登录
相关推荐
嵌入式常用数据结构------队列操作简介
环形队列的相关资料分享
数据结构的简介和线性表及栈队列和数组的详细说明
深度解析数据结构与算法篇之队列及环形队列的实现
数据结构解决滑动窗口问题
工商网监
评论