一種數(shù)組環(huán)形隊(duì)列的數(shù)據(jù)結(jié)構(gòu)

概述

一種更好的計(jì)算隊(duì)尾指針的方法。

隊(duì)尾指針新算法

一個(gè)新的計(jì)算隊(duì)尾指針的公式：

設(shè)模擬環(huán)形隊(duì)列的線性表長(zhǎng)度是N，隊(duì)頭指針為head，隊(duì)尾指針為tail，則每增加一條記錄，就可以用一下方法計(jì)算新的隊(duì)尾指針： tail = (tail + 1) % N

環(huán)形隊(duì)列示意圖

思考

但是，我在移植到8266的代碼時(shí)，發(fā)現(xiàn)有點(diǎn)問題。

第一，head和tail應(yīng)該是存儲(chǔ)該數(shù)組的下標(biāo)而不是一個(gè)指向該數(shù)組元素的指針。如果tail是指針，那么 tail本質(zhì)上是一個(gè)內(nèi)存地址，*tail是指向該數(shù)組的某一元素。那么這算式tail = (tail + 1) % N其實(shí)是對(duì)某數(shù)組元素的內(nèi)存地址+1，然后在用N求余。 所以head和tail應(yīng)該是保存該數(shù)組的下標(biāo)，而不是指向該數(shù)組元素的指針。

第二，由于原先的代碼，其隊(duì)尾指針總是指向最后一個(gè)入隊(duì)元素的下一個(gè)元素，而《算》給出的隊(duì)列，隊(duì)尾指針總是指向最后一個(gè)入隊(duì)的元素。如上圖，一個(gè)N=12的環(huán)形隊(duì)列，原先的代碼tail是指向第8個(gè)，《算》是指向第7個(gè)，由于我是在8266的示例代碼上修改的，所以《算》給出的隊(duì)尾指針?biāo)惴ㄐ枰{(diào)整一下：

//元素入隊(duì)之后
tail++;//tail指向最后一個(gè)入隊(duì)的下一個(gè)元素
tail=tail%N;//重新計(jì)算tail的數(shù)值123

新的數(shù)據(jù)結(jié)構(gòu)

那么我就開始定義新的數(shù)據(jù)結(jié)構(gòu)了，原先的數(shù)據(jù)結(jié)構(gòu)是這樣的

typedefstruct{
uint8_t*p_o;//指向原點(diǎn)的指針，用來數(shù)組首地址
uint8_t*volatilep_r;//讀取指針，相當(dāng)于head
uint8_t*volatilep_w;//寫入指針，相到于tail
volatileint32_tfill_cnt;//隊(duì)列計(jì)數(shù)
int32_tsize;//緩沖區(qū)的大小
}RINGBUF;

新的數(shù)據(jù)結(jié)構(gòu)：

typedefstruct{
char*buf;//指向隊(duì)列數(shù)組的指針
unsignedintlength;//數(shù)組長(zhǎng)度
unsignedinthead;//隊(duì)頭，存儲(chǔ)數(shù)組下標(biāo)
unsignedinttail;//隊(duì)尾，存儲(chǔ)數(shù)組下標(biāo)
intfill_cnt;//隊(duì)列計(jì)數(shù)
}RINGBUF;

判斷是否空隊(duì)列

一開始，本來想用if(head==tail)來判斷隊(duì)列是否為空的，但是由于tail保存的是入隊(duì)元素的下一個(gè)數(shù)組下標(biāo)，當(dāng)隊(duì)列填滿的時(shí)候，tail的下標(biāo)正好等于head，所以不能通過if(head==tail)來判斷隊(duì)列是否為空，

完整代碼

下面是完整的數(shù)組環(huán)形隊(duì)列代碼，運(yùn)行環(huán)境是VS2015，主函數(shù)里進(jìn)行了簡(jiǎn)單的測(cè)試：

// RingBuf.cpp :定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//

#include"stdafx.h"

typedefstruct{
char*buf;//指向隊(duì)列數(shù)組的指針
unsignedintlength;//長(zhǎng)度
unsignedinthead;//隊(duì)頭
unsignedinttail;//隊(duì)尾
intfill_cnt;//隊(duì)列計(jì)數(shù)
}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)
{
//當(dāng)tail+1等于head時(shí)，說明隊(duì)列已滿
if(r->fill_cnt>=r->length){
printf("BUFFULL!
");
returnfalse;//如果緩沖區(qū)滿了，則返回錯(cuò)誤
}

r->buf[r->tail]=data;
r->tail++;
r->fill_cnt++;
//計(jì)算tail是否超出數(shù)組范圍，如果超出則自動(dòng)切換到0
r->tail=r->tail%r->length;
returntrue;
}

intRINGBUF_Get(RINGBUF*r,char*c,unsignedintlength)
{
//當(dāng)tail等于head時(shí)，說明隊(duì)列空
if(r->fill_cnt<=0)?{
????????printf("BUF?EMPTY!
");
????????return?false;
????}

????//最多只能讀取r->length長(zhǎng)度數(shù)據(jù)
if(length>r->length){
length=r->length;
}

inti;
for(i=0;ifill_cnt--;
*c=r->buf[r->head++];//返回?cái)?shù)據(jù)給*c
*c++;
//計(jì)算head自加后的下標(biāo)是否超出數(shù)組范圍，如果超出則自動(dòng)切換到0
r->head=r->head%r->length;
}
returntrue;
}



#defineBUF_LEN5
RINGBUFBUFF;
charbuf[BUF_LEN];

intmain()
{
RINGBUF_Init(&BUFF,buf,sizeof(buf));

printf("1、逐個(gè)讀取數(shù)據(jù)測(cè)試
");
intlength=5;
for(inti=0;i

	

	控制臺(tái)打印信息如下：

	1、逐個(gè)讀取數(shù)據(jù)測(cè)試

	每次讀取1個(gè)字節(jié)：buf pop : 0

	每次讀取1個(gè)字節(jié)：buf pop : 1

	每次讀取1個(gè)字節(jié)：buf pop : 2

	每次讀取1個(gè)字節(jié)：buf pop : 3

	每次讀取1個(gè)字節(jié)：buf pop : 4

	2、一次性讀取測(cè)試

	一次性讀取5個(gè)字節(jié)：buf pop : 12345

	3、放入超過緩沖區(qū)長(zhǎng)度（BUF_LEN+1）數(shù)據(jù)測(cè)試：

	BUF FULL!

	一次性讀取（BUF_LEN+1）個(gè)字節(jié)測(cè)試：buf pop : 12345

	4、讀取空緩沖區(qū)測(cè)試：

	BUF EMPTY!

	請(qǐng)按任意鍵繼續(xù)…

	后話

	由于存在幾種隊(duì)尾指向元素的方式，以上代碼是還可以在修改優(yōu)化一下的。


	《算》的代碼是不需要考慮隊(duì)列是否滿了，他只需要直接覆蓋舊的元素即可，我的需求是需要判斷隊(duì)列是否填滿，以免舊的元素被覆蓋。

	審核編輯：湯梓紅