手撕環形隊列

環形隊列，是一種非常高效的數據結構，在操作系統、數據庫、中間件和各種應用系統中大量使用。今天咱們就來盤它。

下面是一個環形隊列的示意圖：

環形隊列，有兩個指針：頭指針和尾指針。在隊尾寫入，移動尾指針；從隊列頭部讀取，移動頭指針。

環形隊列，是一種特殊的隊列。因此具有隊列的顯著特征：先進先出。

其特殊性在于"環形", 內存空間可以不斷重復使用，無需頻繁分配和釋放內存。并且，可以非常容易實現無鎖的數據結構，在多生產者多消費者的多線程并發場景中，效率非常高。

今天，我們先來實現一個最基本的環形隊列。后續文章，再不斷為其增加更加強悍的特性。

通常，我們用一個數組來實現環形隊列。數組內存，一次性分配好，寫入超過數組末尾時，會回繞至數組開始位置繼續寫入。讀取至數組尾部也會回繞。

需要重點解決的問題是：

當頭指針和尾指針相遇時，需要準確判斷出，環形隊列是空，還是滿，從而決定是否可以繼續寫入，是否能夠繼續讀取。

我們用一個變量 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

// ring_queue.c #include "ring_queue.h" #include #include int ring_queue_init(ring_queue_t* pqueue, int item_size, int capacity) { memset(pqueue, 0, sizeof(*pqueue)); pqueue->pbuf = (char*)malloc(item_size * capacity); if (!pqueue->pbuf) { return -1; } pqueue->item_size = item_size; pqueue->capacity = capacity; pqueue->same_cycle = 1; return 0; } void ring_queue_destroy(ring_queue_t* pqueue) { free(pqueue->pbuf); memset(pqueue, 0, sizeof(*pqueue)); } int ring_queue_push(ring_queue_t* pqueue, void* pitem) { if (ring_queue_is_full(pqueue)) { return -1; } memcpy(pqueue->pbuf + pqueue->tail * pqueue->item_size, pitem, pqueue->item_size); pqueue->tail = (pqueue->tail + 1) % pqueue->capacity; if (0 == pqueue->tail) { // a new cycle pqueue->same_cycle = 0; // tail is not the same cycle with head } return 0; } int ring_queue_pop(ring_queue_t* pqueue, void* pitem) { if (ring_queue_is_empty(pqueue)) { return -1; } memcpy(pitem, pqueue->pbuf + pqueue->head * pqueue->item_size, pqueue->item_size); pqueue->head = (pqueue->head + 1) % pqueue->capacity; if (0 == pqueue->head) { pqueue->same_cycle = 1; // head is now the same cycle with tail } return 0; } int ring_queue_is_empty(ring_queue_t* pqueue) { return (pqueue->head == pqueue->tail) && pqueue->same_cycle; } int ring_queue_is_full(ring_queue_t* pqueue) { return (pqueue->head == pqueue->tail) && !pqueue->same_cycle; }

寫個測試程序，驗證一下：

// test_ring_queue.c #include "ring_queue.h" #include static void test_push(ring_queue_t* pq, int val); static void test_pop(ring_queue_t* pq); int main() { ring_queue_t queue, *pq = &queue; int iret = ring_queue_init(pq, sizeof(int), 3); iret = ring_queue_is_empty(pq); printf("ring_queue is%s empty!\n", iret ? "" : " not"); int val = 1; test_push(pq, val++); test_push(pq, val++); test_push(pq, val++); test_pop(pq); test_push(pq, val++); iret = ring_queue_is_full(pq); printf("ring_queue is%s full!\n", iret ? "" : " not"); test_push(pq, val++); test_pop(pq); test_pop(pq); test_pop(pq); test_pop(pq); return 0; }

編譯，運行這個測試程序，輸出結果為：

$ ./test_ring_queue ring_queue is empty! ring_queue_push succ, val = 1 ring_queue_push succ, val = 2 ring_queue_push succ, val = 3 ring_queue_pop succ, val = 1 ring_queue_push succ, val = 4 ring_queue is full! ring_queue_push failed! iret = -1 ring_queue_pop succ, val = 2 ring_queue_pop succ, val = 3 ring_queue_pop succ, val = 4 ring_queue_pop failed! iret = -1

我的微信號是 實力程序員，歡迎大家轉發至朋友圈，分享給更多的朋友。

C 語言 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。