环形队列，是一种非常高效的数据结构，在操作系统、数据库、中间件和各种应用系统中大量使用。今天咱们就来盘它。
下面是一个环形队列的示意图：
环形队列，有两个指针：头指针和尾指针。在队尾写入，移动尾指针；从队列头部读取，移动头指针。
环形队列，是一种特殊的队列。因此具有队列的显著特征：先进先出。
其特殊性在于"环形", 内存空间可以不断重复使用，无需频繁分配和释放内存。并且，可以非常容易实现无锁的数据结构，在多生产者多消费者的多线程并发场景中，效率非常高。
今天，我们先来实现一个最基本的环形队列。后续文章，再不断为其增加更加强悍的特性。
通常，我们用一个数组来实现环形队列。数组内存，一次性分配好，写入超过数组末尾时，会回绕至数组开始位置继续写入。读取至数组尾部也会回绕。
需要重点解决的问题是：
当头指针和尾指针相遇时，需要准确判断出，环形队列是空，还是满，从而决定是否可以继续写入，是否能够继续读取。
我们用一个变量 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 <stdlib.h>#include <string.h>
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 <stdio.h>
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_queuering_queue is empty!ring_queue_push succ, val = 1ring_queue_push succ, val = 2ring_queue_push succ, val = 3ring_queue_pop succ, val = 1ring_queue_push succ, val = 4ring_queue is full!ring_queue_push failed! iret = -1ring_queue_pop succ, val = 2ring_queue_pop succ, val = 3ring_queue_pop succ, val = 4ring_queue_pop failed! iret = -1
复制代码
我的微信号是 实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。
评论