ce編輯器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;color: black;font-size: 25px;">1. 什么是隊列

隊列（queue）是一種只能在一端插入元素、在另一端刪除元素的數(shù)據(jù)結(jié)構(gòu)，遵循「先入先出」（FIFO）的規(guī)則。

隊列中有兩個基本概念：

• 隊頭指針（可變）：永遠指向此隊列的第一個數(shù)據(jù)元素；
• 隊尾指針（可變）：永遠指向此隊列的最后一個數(shù)據(jù)元素；

隊列中的數(shù)據(jù)存儲方式有兩種：

① 基于靜態(tài)連續(xù)內(nèi)存（數(shù)組）存儲，如圖：② 基于動態(tài)內(nèi)存（鏈表節(jié)點）存儲，如圖：

?后續(xù)都使用基于靜態(tài)內(nèi)存存儲的隊列講解。

?

隊列提供兩個統(tǒng)一的操作：

• 「入隊（enqueue）」

入隊將一個元素添加到隊尾，并將隊尾指針 1后移，如圖：

• 「出隊（dequeue）」

出隊將從隊頭中取出一個元素，并將隊頭指針 1后移，如圖：

2. 環(huán)形隊列

2.1. 環(huán)形隊列的特點

普通隊列的入隊操作將隊尾指針后移 1，出隊操作將隊頭指針后移 1，操作幾次之后會發(fā)現(xiàn)隊頭指針和隊尾指針都跑到緩沖區(qū)的尾部去了：這就導(dǎo)致了前面的內(nèi)存空間全被浪費，如果要重新恢復(fù)使用，則需要進行元素和指針的移動：顯然這種隊列使用方式太不方便了，所以就誕生了環(huán)形隊列：「不用搬移元素和指針，一直可以重復(fù)利用這段內(nèi)存空間」。

2.2. 環(huán)形隊列的實現(xiàn)

TencentOS-tiny中環(huán)形隊列的實現(xiàn)在tos_ring_queue.h和tos_ring_queue.c中。

typedef?struct?k_ring_queue_st?{
????knl_obj_t???knl_obj;

????uint16_t????head;?//隊頭指針
????uint16_t????tail;?//隊尾指針
????size_t??????total;?//記錄隊列中元素的個數(shù)

????uint8_t????*pool;?//隊列底層的存儲結(jié)構(gòu)（一個數(shù)組）

????size_t??????item_size;?//隊列中每個元素的大小，單位：字節(jié)
????size_t??????item_cnt;?//隊列中可以容納的元素數(shù)量
}?k_ring_q_t;
環(huán)形隊列初始化，將隊頭指針和隊尾置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)形隊列是否為滿或者為空：

__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)形隊列入隊操作的API如下：

__API__?k_err_t?tos_ring_q_enqueue(k_ring_q_t?*ring_q,?void?*item,?size_t?item_size);
在此API中，入隊操作的實現(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)形隊列出隊操作的API如下：

__API__?k_err_t?tos_ring_q_dequeue(k_ring_q_t?*ring_q,?void?*item,?size_t?*item_size);
在此API中，出隊操作的實現(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;
}
在入隊和出隊操作的時候都使用了 RING_NEXT 宏，用來獲取在環(huán)形隊列中的下一個位置：

#define?RING_NEXT(ring_q,?index)????((index? ?1)?%?ring_q->item_cnt)


2.3. 環(huán)形隊列使用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)形隊列
????tos_ring_q_create(