手撕环形队列

网友投稿 616 2022-05-29

环形队列,是一种非常高效的数据结构,在操作系统、数据库、中间件和各种应用系统中大量使用。今天咱们就来盘它。

下面是一个环形队列的示意图:

环形队列,有两个指针:头指针和尾指针。在队尾写入,移动尾指针;从队列头部读取,移动头指针。

环形队列,是一种特殊的队列。因此具有队列的显著特征:先进先出。

手撕环形队列

其特殊性在于"环形", 内存空间可以不断重复使用,无需频繁分配和释放内存。并且,可以非常容易实现无锁的数据结构,在多生产者多消费者的多线程并发场景中,效率非常高。

今天,我们先来实现一个最基本的环形队列。后续文章,再不断为其增加更加强悍的特性。

通常,我们用一个数组来实现环形队列。数组内存,一次性分配好,写入超过数组末尾时,会回绕至数组开始位置继续写入。读取至数组尾部也会回绕。

需要重点解决的问题是:

当头指针和尾指针相遇时,需要准确判断出,环形队列是空,还是满,从而决定是否可以继续写入,是否能够继续读取。

我们用一个变量 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小时内删除侵权内容。

上一篇:OpenCV 单目摄像头(python版)
下一篇:Python基础(四)
相关文章