ce編輯器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;color: black;font-size: 25px;">1. 什么是隊(duì)列
隊(duì)列(queue)是一種只能在一端插入元素、在另一端刪除元素的數(shù)據(jù)結(jié)構(gòu),遵循
「先入先出」(FIFO)的規(guī)則。隊(duì)列中有兩個(gè)基本概念:
- 隊(duì)頭指針(可變):永遠(yuǎn)指向此隊(duì)列的第一個(gè)數(shù)據(jù)元素;
- 隊(duì)尾指針(可變):永遠(yuǎn)指向此隊(duì)列的最后一個(gè)數(shù)據(jù)元素;
隊(duì)列中的數(shù)據(jù)存儲(chǔ)方式有兩種:① 基于靜態(tài)連續(xù)內(nèi)存(數(shù)組)存儲(chǔ),如圖:② 基于動(dòng)態(tài)內(nèi)存(鏈表節(jié)點(diǎn))存儲(chǔ),如圖:
?后續(xù)都使用基于靜態(tài)內(nèi)存存儲(chǔ)的隊(duì)列講解。?
隊(duì)列提供兩個(gè)統(tǒng)一的操作:
入隊(duì)將一個(gè)元素添加到隊(duì)尾,并將隊(duì)尾指針 1后移,如圖:
出隊(duì)將從隊(duì)頭中取出一個(gè)元素,并將隊(duì)頭指針 1后移,如圖:
2. 環(huán)形隊(duì)列
2.1. 環(huán)形隊(duì)列的特點(diǎn)
普通隊(duì)列的入隊(duì)操作將隊(duì)尾指針后移 1,出隊(duì)操作將隊(duì)頭指針后移 1,操作幾次之后會(huì)發(fā)現(xiàn)隊(duì)頭指針和隊(duì)尾指針都跑到緩沖區(qū)的尾部去了:這就導(dǎo)致了前面的內(nèi)存空間全被浪費(fèi),如果要重新恢復(fù)使用,則需要進(jìn)行元素和指針的移動(dòng):顯然這種隊(duì)列使用方式太不方便了,所以就誕生了環(huán)形隊(duì)列:
「不用搬移元素和指針,一直可以重復(fù)利用這段內(nèi)存空間」。
2.2. 環(huán)形隊(duì)列的實(shí)現(xiàn)
TencentOS-
tiny中環(huán)形隊(duì)列的實(shí)現(xiàn)在
tos_ring_queue.h
和
tos_ring_queue.c
中。
typedef?struct?k_ring_queue_st?{
????knl_obj_t???knl_obj;
????uint16_t????head;?//隊(duì)頭指針
????uint16_t????tail;?//隊(duì)尾指針
????size_t??????total;?//記錄隊(duì)列中元素的個(gè)數(shù)
????uint8_t????*pool;?//隊(duì)列底層的存儲(chǔ)結(jié)構(gòu)(一個(gè)數(shù)組)
????size_t??????item_size;?//隊(duì)列中每個(gè)元素的大小,單位:字節(jié)
????size_t??????item_cnt;?//隊(duì)列中可以容納的元素?cái)?shù)量
}?k_ring_q_t;
環(huán)形隊(duì)列初始化,將隊(duì)頭指針和隊(duì)尾置0:
?__API__?k_err_t?tos_ring_q_create(k_ring_q_t?*ring_q,?void?*pool,?size_t?item_cnt,?size_t?item_size)
{
?//省略了參數(shù)合法性檢查代碼
????ring_q->head????????=?0u;
????ring_q->tail????????=?0u;
????ring_q->total???????=?0;
????ring_q->pool????????=?(uint8_t?*)pool;
????ring_q->item_size???=?item_size;
????ring_q->item_cnt????=?item_cnt;
????return?K_ERR_NONE;
}
判斷環(huán)形隊(duì)列是否為滿或者為空:
__API__?int?tos_ring_q_is_empty(k_ring_q_t?*ring_q)
{
????TOS_CPU_CPSR_ALLOC();
????int?is_empty?=?K_FALSE;
????//省略了參數(shù)合法性檢查代碼
????TOS_CPU_INT_DISABLE();
????is_empty?=?(ring_q->total?==?0???K_TRUE?:?K_FALSE);
????TOS_CPU_INT_ENABLE();
????return?is_empty;
}
__API__?int?tos_ring_q_is_full(k_ring_q_t?*ring_q)
{
????TOS_CPU_CPSR_ALLOC();
????int?is_full?=?K_FALSE;
??//省略了參數(shù)合法性檢查代碼
????TOS_CPU_INT_DISABLE();
????is_full?=?(ring_q->total?==?ring_q->item_cnt???K_TRUE?:?K_FALSE);
????TOS_CPU_INT_ENABLE();
????return?is_full;
}
環(huán)形隊(duì)列入隊(duì)操作的API如下:
__API__?k_err_t?tos_ring_q_enqueue(k_ring_q_t?*ring_q,?void?*item,?size_t?item_size);
在此API中,入隊(duì)操作的實(shí)現(xiàn)如下:
__STATIC_INLINE__?void?ring_q_item_increase(k_ring_q_t?*ring_q)
{
????ring_q->tail?=?RING_NEXT(ring_q,?ring_q->tail);
???? ring_q->total;
}
環(huán)形隊(duì)列出隊(duì)操作的API如下:
__API__?k_err_t?tos_ring_q_dequeue(k_ring_q_t?*ring_q,?void?*item,?size_t?*item_size);
在此API中,出隊(duì)操作的實(shí)現(xiàn)如下:
__STATIC_INLINE__?void?ring_q_item_decrease(k_ring_q_t?*ring_q)
{
????ring_q->head?=?RING_NEXT(ring_q,?ring_q->head);
????--ring_q->total;
}
在入隊(duì)和出隊(duì)操作的時(shí)候都使用了 RING_NEXT 宏,用來獲取在環(huán)形隊(duì)列中的下一個(gè)位置:
#define?RING_NEXT(ring_q,?index)????((index? ?1)?%?ring_q->item_cnt)
2.3. 環(huán)形隊(duì)列使用Demo
編寫如下的測(cè)試代碼:
ce;font-size: 12px;-webkit-overflow-scrolling: touch;letter-spacing: 0px;padding-top: 15px;background: #f8f8f8;border-radius: 5px;">#include?
typedef?struct?item_st?{
????int?a;
????int?b;
????int?c;
}?item_t;
#define?RING_QUEUE_ITEM_MAX?5
uint8_t?ring_q_buffer[RING_QUEUE_ITEM_MAX?*?sizeof(item_t)];
k_ring_q_t?ring_q;
void?entry_task_demo(void?*arg)
{
????k_err_t?err;
????int?i;
????item_t?item;
????size_t?item_size;
????
????//創(chuàng)建環(huán)形隊(duì)列
????tos_ring_q_create(