背景
對于資料結構，其實學過C語言的都不陌生，無外乎就隊列、棧、二叉樹等等這些。但其實對于初學者最困惑的不是資料結構是怎麼樣的，而是資料結構有什麼用？我自己也是工作好幾年後才體驗到資料結構的快樂。是以本系列文章重點從應用場景切入，讓大家了解資料結構的好處。
簡介
隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端進行删除操作，而在表的後端進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。隊列有兩種形态，順序排列的線性隊列，也有頭尾閉環的環形隊列，也稱作循環隊列。
- 線性隊列（循環隊列）
簡單的了解，就像是排隊做核酸，大家自覺排成一隊或幾隊，這每一隊就是一個隊列，先來的人先做，後到的人後做。如下圖，目前有資料Data1過來，則先進入隊裡，排在隊頭，再來個Data2時，則排在Data1後面，再來就Data3就排在Data2後面。
如果此時要讓資料出隊，則先讓Data1出隊，然後Data2和3往前移一個位置。
如果此時再來個Data4，則把Data4填到隊尾即可。
- 環形隊列（循環隊列）
跟順序隊列唯一的差別，就是它首尾相接，就是相當于一隊人排成一個環狀，環形隊列也是以得名。
當需要把Data1移出隊時，可以擷取出資料，然後修改隊頭的位置即可，不用去搬運其他成員的資料，甚至出隊的資料都不需要删除，等着後面新資料将其覆寫即可。這就是循環隊列的好處。
但實際在記憶體中，不可能真的存在一個環形的緩存（起碼現在沒有）。在記憶體裡，環形隊列跟順序隊列完全一樣，隻是其隊頭跟隊尾根據出隊入隊在不斷地變化。
應用場景
就如前面所說，隊列有個特點是可以緩沖，那這裡可以想到什麼呢？對了，就是國小做的那個數學題，一邊進水xx升/小時，另一邊排水xx升/小時，中間的那個水箱就是個隊列。。。。不舉這種浪費水的例子，咱們換一個，其實最常用的地方，就是在有事件請求跟事件消耗中，并且請求跟消耗是異步進行的場景。
舉個實際例子，現在有一個觸摸屏，使用者點選下螢幕，顯示屏會有對應的動作，點一次動一次，并且動作跟點選順序有關系，先點的先動作。那按這樣的設計思路，最簡單的寫法如下：
void Check(void)
{
/* 檢測的相關處理 */
}
void Operation(void)
{
/* 觸發的相關執行動作 */
}
int main(void)
{
/* 檢測觸摸位置 */
Check();
/* 執行對應的動作 */
Operation();
return 0;
}
但上面的實作有什麼問題？如果這時候執行的動作很多，占用時間很多，比如整個屏重新整理需要1s（誇張點的說法哈），那上面這種寫法就會導緻我按鍵隻能1s按一次，按快了沒反應。那這裡我們先引入實時作業系統的概念——時間片，把需要執行的動作切分成很多個時間片，比如整屏重新整理原本需要1s，那就把它分成100份10ms的時間片，觸摸檢測也一樣，然後在整屏每重新整理10ms的時候，就檢測一次觸摸情況。這樣在使用者的角度來看，基本就看不出來延時的時間，按鍵和屏的重新整理變成幾乎同步進行。
void Check(void)
{
while(1)
{
/* 檢測觸摸事件--10ms檢測一次 */
os_delay(10);
}
}
void Operation(void)
{
while(1)
{
/* 刷屏--重新整理一部分就延時讓出一下，或者利用作業系統本身時間片特性讓出也行。 */
os_delay(1);
}
}
int main(void)
{
/* 建立觸摸檢測和刷屏兩個任務--僞代碼，重在了解 */
task_create(Check);
task_create(Operation);
return 0;
}
但這上面的實作還是有問題，雖然同一個屏，重新整理的速度是一樣的，但是不同的人，操作的速度是不一樣的，老年人可能幾秒鐘才能操作一下，但單身20年的小夥可能1秒可以操作20下。因為屏重新整理隻能1s刷一下，那精神小夥操作的那20下，可能就隻有最後一下可以顯示出來。這時候小夥就不高興了，為什麼我一頓操作猛如虎，這屏就給這麼點反應，要求點多少下重新整理多少次。那麼這時候我們的主角終于可以登場了，分析下這個場景，觸摸檢測到1s操作了20次，而屏隻能1s重新整理一次，典型的事件請求>事件消耗，并且這個事件請求是有間斷性的，也就是小夥并不是一直按1秒操作20下的速度來操作的，隻是這麼操作了一次。那這裡我們就引入隊列，把小夥的操作都給存起來。
- 順序隊列
/*******************隊列的相關操作********************/
/* 預留的緩存大小 */
#define QUEUE_MAX 30
struct tagQueueCB
{
uint8_t Buff[QUEUE_MAX];
uint32_t Tail;
};
struct tagQueueCB QueueCB;
/* 入隊操作 */
uint8_t Queue_Push(uint8_t data)
{
uint8_t rtn = 0;
if (QueueCB.Tail < QUEUE_MAX)
{
QueueCB.Buff[QueueCB.Tail++] = data;
rtn = 1;
}
else
{
/* 隊列滿，傳回失敗 */
rtn = 0;
}
return rtn;
}
/* 出隊操作 */
uint8_t Queue_Poll(uint8_t *data)
{
uint8_t rtn = 0;
if (QueueCB.Tail)
{
*data = QueueCB.Buff[0];
QueueCB.Tail--;
for (uint32_t i = 0; i < QueueCB.Tail; i++)
{
QueueCB.Buff[i] = QueueCB.Buff[i + 1];
}
rtn = 1;
}
else
{
/* 隊列空時傳回失敗 */
rtn = 0;
}
return rtn;
}
/***************************************************/
void Check(void)
{
uint8_t data = 0;
while(1)
{
/* 檢測事件 */
/* 有觸摸事件，入一次隊 */
if (0 == Queue_Push(data))
{
/* 異常處理 */
}
/* 檢測觸摸事件--10ms檢測一次 */
os_delay(10);
}
}
void Operation(void)
{
uint8_t data = 0;
while(1)
{
/* 檢測隊列，非空則出隊，并刷整屏 */
if (0 == Queue_Poll(&data))
{
/* 異常處理 */
}
/* 執行刷屏 */
/* 刷屏--重新整理一部分就延時讓出一下，或者利用作業系統本身時間片特性讓出也行。 */
os_delay(1);
}
}
int main(void)
{
/* 建立觸摸檢測和刷屏兩個任務--僞代碼，重在了解 */
task_create(Check);
task_create(Operation);
return 0;
}
這樣就解決了小夥的手速問題。當然如果過兩年小夥手速又提升了，那這30的緩存可能也扛不住。這上面實作的就是最普通的順序隊列，使用數組存儲資料，并提供出隊、入隊的操作。然而細心的小夥伴可能已經發現了，這出隊操作效率也太低了吧，把隊頭資料移出後，後續所有資料都得往前移，而且現在是多線程，如果在入隊的過程中，執行了出隊，資料就會錯亂（重入）。那麼這裡我們就提供第二種隊列的實作方式——循環隊列。
- 循環隊列
/*******************隊列的相關操作********************/
/* 預留的緩存大小 */
#define QUEUE_MAX 30
struct tagQueueCB
{
uint8_t Buff[QUEUE_MAX];
uint32_t Head; /* 隊頭位置 */
uint32_t Tail; /* 隊尾位置 */
uint32_t Num; /* 隊列元素個數 */
};
struct tagQueueCB QueueCB;
/* 入隊操作 */
uint8_t Queue_Push(uint8_t data)
{
uint8_t rtn = 0;
if (QueueCB.Num < QUEUE_MAX)
{
QueueCB.Buff[QueueCB.Tail] = data;
QueueCB.Tail = (QueueCB.Tail + 1) % QUEUE_MAX;
/* 數量記得放最後修改，不然還是會有重入問題 */
QueueCB.Num++;
rtn = 1;
}
else
{
/* 隊列滿，傳回失敗 */
rtn = 0;
}
return rtn;
}
/* 出隊操作 */
uint8_t Queue_Poll(uint8_t *data)
{
uint8_t rtn = 0;
if (QueueCB.Num)
{
*data = QueueCB.Buff[QueueCB.Head];
QueueCB.Head = (QueueCB.Head + 1) % QUEUE_MAX;
/* 數量記得放最後修改，不然還是會有重入問題 */
QueueCB.Num--;
rtn = 1;
}
else
{
/* 隊列空時傳回失敗 */
rtn = 0;
}
return rtn;
}
/***************************************************/
void Check(void)
{
uint8_t data = 0;
while(1)
{
/* 檢測事件 */
/* 有觸摸事件，入一次隊 */
if (0 == Queue_Push(data))
{
/* 異常處理 */
}
/* 檢測觸摸事件--10ms檢測一次 */
os_delay(10);
}
}
void Operation(void)
{
uint8_t data = 0;
while(1)
{
/* 檢測隊列，非空則出隊，并刷整屏 */
if (0 == Queue_Poll(&data))
{
/* 異常處理 */
}
/* 執行刷屏 */
/* 刷屏--重新整理一部分就延時讓出一下，或者利用作業系統本身時間片特性讓出也行。 */
os_delay(1);
}
}
int main(void)
{
/* 建立觸摸檢測和刷屏兩個任務--僞代碼，重在了解 */
task_create(Check);
task_create(Operation);
return 0;
}
除了上面這種應用，還有像通信協定，也會用到隊列，一般叫通信緩存。另外還有像實時作業系統裡的郵箱，其實就是一個事件隊列。
還有一種應用，是用在日志存儲，存儲的結構其實就是一個循環隊列，但跟通信緩存有一點不同的是，通信緩存一般是不允許入隊入滿的，如果隊滿了，一般的做法也是把要入隊的資訊舍棄掉。但日志存儲則是需要把最開始的資料覆寫掉，以此來保持記錄最近的記錄。
總結
- 常見隊列有兩種，順序隊列和循環隊列。
- 一般用在需要資料緩存的地方，比如通信驅動與應用處理的銜接，日志存儲服務與應用的銜接等等。
- 對于隊列的操作，要多注意重入的問題，畢竟這種資料結構就是在多方共用記憶體的情況下使用的。
相關知識
棧、連結清單、樹、圖、散清單