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ì)（enqueue）」

入隊(duì)將一個(gè)元素添加到隊(duì)尾，并將隊(duì)尾指針 1后移，如圖：

• 「出隊(duì)（dequeue）」

出隊(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

編寫如下的測試代碼：

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(