【队列】循环队列（Circular Queue）详解
文章目录
一、循环队列简介
在实际开发中，队列是一种常用的数据结构，而循环队列（Circular Queue）则一般是一种基于数组实现的队列（也可使用循环链表）。与传统的 FIFO 队列相比，循环队列通过将数组首尾相连形成一个 “环”，能够更高效地利用内存空间。
循环队列的主要思想是：当队尾指针到达数组末端时，如果数组前面还有空余空间，就可以从数组头部重新利用这些空间进行入队操作。也就是说，数组的末端和头部通过逻辑上的连接，形成一个环状结构，从而避免了顺序队列中由于出队操作而导致的空间浪费问题。
如下图就是一个典型的循环队列，其中的 front 表示头指针，指向队头。rear 则表示尾指针，指向队尾元素的下一个位置。
二、循环队列的判空和判满
在循环队列中，front 与 rear 都是可以循环移动的，当队空时，front == rear 成立；当队满时，front == rear 也成立。因此显然不能只凭 front == rear 来判断队空还是队满。
为了解决这个问题，在循环队列中约定：少用一个元素空间，当队尾标识的 rear在队头标识front 的上一个位置时，队列为满。此时，判断队空和队满的条件分别如下：
队空时：front == rear
队满时：(rear + 1) % MAXSIZE == front
其中，MAXSIZE是队列容量的大小
两种情况下队列中指针的状态如下图所示：
既然少一个元素空间，这就意味着，如果要存储的数据个数最大为 k，那么你需要开辟的循环队列的大小应为 k+1
三、循环队列的实现
我们来以具体的一道题目来实现循环队列的各种操作
leetcode 622. 设计循环队列
typedefstruct{int* a;int front;// 头“指针”指向队头数据int tail;// 尾“指针”指向队尾的下一个位置int k;// 一会儿开辟的队列大小为 k+1} MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj);// 前面先实现的函数要用到这两个接口，所以事先声明一下// 循环队列的初始化 MyCircularQueue*myCircularQueueCreate(int k){ MyCircularQueue* cq =(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->a =(int*)malloc(sizeof(int)*(k+1)); cq->front =0;// 初始化数据 cq->tail =0; cq->k = k;return cq;}// 入队 bool myCircularQueueEnQueue(MyCircularQueue* obj,int value){if(myCircularQueueIsFull(obj))return false;// 满了就不能再入了 obj->a[obj->tail]= value;// 将数据入进来++obj->tail;// 更新tail obj->tail %=(obj->k+1);// tail 自增了之后可能超出循环队列的大小范围所以要取模// 模的是循环队列的大小 k+1return true;}// 出队 bool myCircularQueueDeQueue(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return false;// 为空就不能再删 obj->front =(obj->front+1)%(obj->k+1);// 和前面是一样的原理，注意同样是加一再取模return true;}// 获取队头元素intmyCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;return obj->a[obj->front];}// 获取队尾元素intmyCircularQueueRear(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;if(obj->tail ==0)return obj->a[obj->k];// 跨越了一个循环的情况elsereturn obj->a[obj->tail-1];}// 判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj){return obj->front == obj->tail;}// 判满 bool myCircularQueueIsFull(MyCircularQueue* obj){return(obj->tail+1)%(obj->k+1)== obj->front;// tail的后一个是front说明满了，但是有可能tail+1跨过了一个循环。所以要取模}// 释放voidmyCircularQueueFree(MyCircularQueue* obj){free(obj->a);// 注意这里要先释放结构体内的数组！！！不然会可能内存泄漏free(obj);}
