数据结构——循环队列的实现(上）：https://developer.aliyun.com/article/1496804
4.用数组实现循环队列
4.1设计队列结构
前面我们提到过设计队列时考虑加上一个size记录存放节点个数以便判断队列是否为空
typedef struct { int front;//首下标 int rear;//尾下标 int* a;//数组 int k;//记录k值 } MyCircularQueue;
这里采用一个结构体封装，并记录数组的首尾下标，并保留一个k来记录k值，以便后面使用。
4.2构造队列（k+1个节点）
MyCircularQueue(k): 构造器，设置队列长度为 k
MyCircularQueue* myCircularQueueCreate(int k) { //开辟循环队列空间 MyCircularQueue* queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if (queue == NULL) { perror("malloc fail1"); return NULL; } //开辟数组空间 queue->a = (int*)malloc(sizeof(int)*(k+1)); if (queue->a == NULL) { perror("malloc fail2"); return NULL; } queue->front = 0; queue->rear = 0;//尾指向最后一个元素的下一个 queue->k = k;//记录k，后面使用 return queue; }
这里注意开辟了（k+1）个节点空间，采用的是前面说的第二种情况，rear指向最后一个元素的下一个位置。
4.3向循环队列插入一个元素
myCircularQueueEnQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。代码如下：
//插入数据 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { assert(obj); //判断队列是否满了 if(myCircularQueueIsFull(obj)) { return false; } //插入队列 //1.队列无元素的情况 if (myCircularQueueIsEmpty(obj)) { obj->a[obj->front] = value; obj->rear++; obj->rear %= obj->k+1; return true; } //2.队列有元素的情况 obj->a[obj->rear] = value; obj->rear ++; obj->rear %= obj->k+1; return true; }
这里也分两种情况来插入，💥💥此外还要注意插入元素之后rear要++，但是如果rear超过数组的长度k+1就会造成越界访问，所以这里提供了一个方法：每次rear++之后再与k+1取模运算，这样就可以得到小于等于k的值，不会造成越界访问。
4.4判断循环队列是否为空
myCircularQueueIsEmpty(): 检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { assert(obj); if (obj->front == obj->rear) return true; return false; }
因为rear指向最后一个元素的下一个元素，所以当rear等于front时，数组为空，此时一个数据也没有插入。
4.5判断循环队列是否满了
myCircularQueueIsFull(): 检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) { assert(obj); if((obj->rear+1)%(obj->k+1)==obj->front) { return true; } return false; }
数组并非像链表那样有pNext指针指向下一个节点，链表可以形成天然的循环结构，而数组却要依靠首尾下标来模拟实现，如图所示有两种情况：
当删除节点时只需将front++即可，所以front位置可能不是0；
4.6从循环队列中删除一个元素
myCircularQueueDeQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。注意队列先进先出，是头删。
//删除数据 bool myCircularQueueDeQueue(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) { return false; } //头删，因为是先进先出 obj->front++; obj->front %= obj->k+1; return true; }
注意这里front也是一样，在+1后可能大于k造成越界，所以要进行取模运算。
4.7 从队首获取元素
myCircularQueueFront: 从队首获取元素。如果队列为空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; }
4.8获取队尾元素
Rear: 获取队尾元素。如果队列为空，返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[(obj->rear+obj->k)%(obj->k+1)]; }
这里要注意本来应该返回rear-1；因为rear指向尾节点的下一位，但是如果rear值为0时，再-1就变成-1了，也会造成越界访问，所以也要进行取模运算(rear-1+k+1)%(k+1),即可，因为数组有k+1个节点所以要+（k+1）并%(k+1)
3.9销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) { assert(obj); free(obj->a); free(obj); return; }
3.10结果如下：
5.结语
链表来实现循环队列有一个好处就是形成了天然的环形结构，对应数组实现循环队列则需要front，rear不断进行取模运算以防越界；但是链表实现需要手动将开辟的节点链接在一起，数组则不一样它一开辟就是地址连续的一段空间；其他的实现链表和数组都差不多；
以上就是循环队列的实现啦~ 大家有什么疑问可以写在评论区或者私信我哦~ 完结撒花~🥳🥳🎉🎉🎉
