環形隊列，是一種非常高效的數據結構，在操作系統、數據庫、中間件和各種應用系統中大量使用。今天咱們就來盤它。
下面是一個環形隊列的示意圖：
環形隊列，有兩個指針：頭指針和尾指針。在隊尾寫入，移動尾指針；從隊列頭部讀取，移動頭指針。
環形隊列，是一種特殊的隊列。因此具有隊列的顯著特征：先進先出。
其特殊性在於"環形", 內存空間可以不斷重復使用，無需頻繁分配和釋放內存。並且，可以非常容易實現無鎖的數據結構，在多生產者多消費者的多線程並發場景中，效率非常高。
今天，我們先來實現一個最基本的環形隊列。後續文章，再不斷為其增加更加強悍的特性。
通常，我們用一個數組來實現環形隊列。數組內存，一次性分配好，寫入超過數組末尾時，會回繞至數組開始位置繼續寫入。讀取至數組尾部也會回繞。
需要重點解決的問題是：
當頭指針和尾指針相遇時，需要準確判斷出，環形隊列是空，還是滿，從而決定是否可以繼續寫入，是否能夠繼續讀取。
我們用一個變量 same_cycle，來完成對環形隊列空/滿的判斷。具體邏輯如下：
1）初始，head = 0, tail = 0，都指向環形隊列的位置0處。我們把head或tail指針，在環形隊列中轉瞭完整一圈，叫一個輪次。初始，same_cycle = 1(true), 表示head和tail 兩個指針是同一輪次的。
2）寫入時，如果隊列已滿，則無法寫入，直接返回失敗。如果隊列未滿，則在tail 位置寫入，tail移動至下一個位置(可能會回繞)。如果下一個位置為數組位置0，則表示開始瞭一個新的輪次，因此設置 same_cycle = 0(false)。
3）讀取時，如果隊列已空，則無法讀取，直接返回失敗。如果隊列未空，則從head位置讀取，head移動至下一個位置(可能會回繞)。如果下一個位置為數組位置0，則表示開始瞭一個新的輪次，與tail指針的輪次變得相同，因此設置 same_cycle = 1(true)。
根據以上，環形隊列為空的判斷規則為：
(head == tail) && same_cycle
環形隊列已滿的判斷規則為：
(head == tail) && !same_cycle
環形隊列，C語言實現的代碼如下：
// ring_queue.h
#ifndef RING_QUEUE_H
#define RING_QUEUE_H
typedef struct ring_queue_t {
char* pbuf;
int item_size;
int capacity;
int head;
int tail;
int same_cycle;
} ring_queue_t;
int ring_queue_init(ring_queue_t* pqueue, int item_size, int capacity);
void ring_queue_destroy(ring_queue_t* pqueue);
int ring_queue_push(ring_queue_t* pqueue, void* pitem);
int ring_queue_pop(ring_queue_t* pqueue, void* pitem);
int ring_queue_is_empty(ring_queue_t* pqueue);
int ring_queue_is_full(ring_queue_t* pqueue);
#endif
