概述

一種更好的計算隊尾指針的方法。

隊尾指針新算法

一個新的計算隊尾指針的公式：

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

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

思考

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

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

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

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

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

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

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

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

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

判斷是否空隊列

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

完整代碼

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

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

#include"stdafx.h"

typedefstruct{
char*buf;//指向隊列數(shù)組的指針
unsignedintlength;//長度
unsignedinthead;//隊頭
unsignedinttail;//隊尾
intfill_cnt;//隊列計數(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時，說明隊列已滿
if(r->fill_cnt>=r->length){
printf("BUFFULL!
");
returnfalse;//如果緩沖區(qū)滿了，則返回錯誤
}

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

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

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

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



#defineBUF_LEN5
RINGBUFBUFF;
charbuf[BUF_LEN];

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

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

	

	控制臺打印信息如下：

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

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

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

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

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

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

	2、一次性讀取測試

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

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

	BUF FULL!

	一次性讀?。˙UF_LEN+1）個字節(jié)測試：buf pop : 12345

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

	BUF EMPTY!

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

	后話

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


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

	審核編輯：湯梓紅