创作不易，给个三连吧！！
一、前言
对于循环队列，博主也是源自于一道力扣的OJ题
后来我在网上查过，这个循环队列是有自己的应用场景的！！并不是出题者为了出题而产生的，所以我觉得不光要能做会这道题，还得多去探究这道题的不同方式。而且这道题虽然是循环队列，看似好像要把头和尾连起来，但实际上实现过程中是可以不需要的！这也是他非常特别的一点，因此在这我会重点介绍他的数组实现和链式结构实现。
二、数组实现循环队列
怎么用数组去实现循环队列呢？我们来画图研究一下：
2.1 结构体的创建
typedef int QDataType; typedef struct MyCircularQueue { QDataType* a;//动态数组 int capacity;//记录循环队列的容量 int front;//记录队首 int rear;//记录队尾 } MyCircularQueue;
2.2 构造一个k长度的队列并返回
根据我们之前的思路，我们要多创建一块空间！！
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if (obj == NULL) { perror("malloc obj fail"); exit(1); } obj->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1)); if (obj->a == NULL) { perror("malloc obj->a fail"); exit(1); } obj->front = obj->rear = 0; obj->capacity = k; return obj; }
2.3 向循环队列插入一个元素。如果成功插入则返回真。
我们要往循环队列中插入一个元素，那么首先必须确保队列不为满（后面会封装），那我们之前分析过队列不为满的情况是rear指针的下一个位置是front，但是我们要注意一个特殊情况，如下图：
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value) { if (myCircularQueueIsFull(obj)) return false; obj->a[obj->rear] = value; obj->rear++; obj->rear %= (obj->capacity + 1); return true; }
但是我们要注意的是实际上我们是多开了一个空间！！！%的时候要把多的空间算上
2.4 向循环队列删除一个元素。如果成功删除则返回真。
我们要往循环队列中删除一个元素，那么首先必须确保队列不为空（后面会封装），front++就行了，同样front也会遇到上面这种情况，处理当时一样，++完后%上数组的实际大小
bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return false; obj->front++; obj->front %= (obj->capacity + 1); return true; }
2.5 从队首获取元素。如果队列为空，返回 - 1
直接取头指针就行了
int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; }
2.6 从队尾获取元素。如果队列为空，返回 - 1
要注意rear指针指向的是最后一个元素的下一个位置，所以要取得的话就要找到rear的前一个位置的下标，这里我们不能直接让rear--，因为我们只是获取队列尾的元素，并不能去改变rear的指向，所以我们要算出rear前面那个位置的下标，其实也是一样，利用%的修正，让rear加上数组实际大小-1，然后再%数组的大小，就刚还是rear前面的位置的下标了！！
int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; return obj->a[(obj->rear + obj->capacity) % (obj->capacity + 1)]; }
2.7 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; }
2.8 判断循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear + 1)%(obj->capacity + 1) ==obj->front;//rear为k的时候正好 }
2.9 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a);//没必要置空，因为obj用不了，obj->a也用不了 front rear k 也没必要释放 free(obj); //obj = NULL; }
2.10 全部代码
2.10.1 MyCircularQueue.h
#pragma once #include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h> typedef int QDataType; typedef struct MyCircularQueue { QDataType* a;//动态数组 int capacity;//记录循环队列的容量 int front;//记录队首 int rear;//记录队尾 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列 bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。 bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。 int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空，返回 - 1 。 int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空，返回 - 1 。 bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空 bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满 void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列
2.10.2 MyCircularQueue.c
#include"MyCircularQueue.h" MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if (obj == NULL) { perror("malloc obj fail"); exit(1); } obj->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1)); if (obj->a == NULL) { perror("malloc obj->a fail"); exit(1); } obj->front = obj->rear = 0; obj->capacity = k; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value) { if (myCircularQueueIsFull(obj)) return false; obj->a[obj->rear] = value; obj->rear++; obj->rear %= (obj->capacity + 1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return false; obj->front++; obj->front %= (obj->capacity + 1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; return obj->a[(obj->rear + obj->capacity) % (obj->capacity + 1)]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear + 1)%(obj->capacity + 1) ==obj->front;//rear为k的时候正好 } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a);//没必要置空，因为obj用不了，obj->a也用不了 front rear k 也没必要释放 free(obj); //obj = NULL; }
2.11 相关选择题
5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)（ ？）
A (rear - front + N) % N + 1
B (rear - front + N) % N
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)
答：这题就是根据我们上面那道题的一个变形，所以我们知道肯定是%上长度的，所以可以直接选B
三、链式结构实现循环队列
怎么用链式结构来实现循环队列呢？我们来分析一下：
3.1 结构体的创建
我们按照链式队列的思路，创建一个队列结构体来管理头尾指针，同时加上capacity（容量）和size（有效数据）
typedef int QDataType; typedef struct QNode { struct QNode* next;//节点 QDataType val;//数据域 }QNode; typedef struct MyCircularQueue { QNode* front;//链表的头指针 QNode* rear;//链表的尾指针 int capacity;//记录链表的容量 int size;//记录链表的有效节点 }MyCircularQueue;
3.2 构造一个k长度的队列并返回
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if (obj == NULL) { perror("malloc fail"); exit(1); } obj->front = obj->rear = NULL; obj->size = 0; obj->capacity = k; return obj; }
3.3 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value) { //如果为满了，直接就返回false if (myCircularQueueIsFull(obj)) return false; //不满足就创建节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->val = value; newnode->next = NULL; //创建成功，要考虑队列为空和不为空的情况 if (myCircularQueueIsEmpty(obj))//为空，让新节点成为头 obj->front = obj->rear = newnode; else//不为空，让tail继续往后遍历 { obj->rear->next = newnode; obj->rear = newnode; } obj->size++; return true; }
3.4 向循环队列删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) { //为空就没有删的必要了 if (myCircularQueueIsEmpty(obj)) return false; //不为空，删除头节点，让下一个节点成为新的头，然后释放掉 QNode* cur = obj->front->next; free(obj->front); obj->front = cur; obj->size--; return true; }
3.5 从队首获取元素。如果队列为空，返回 - 1
int myCircularQueueFront(MyCircularQueue* obj) { //为空，返回1 if (myCircularQueueIsEmpty(obj)) return -1; //不为空，就获取头指针的数据 return obj->front->val; }
3.6 从队尾获取元素。如果队列为空，返回 - 1
int myCircularQueueRear(MyCircularQueue* obj) { //为空，返回1 if (myCircularQueueIsEmpty(obj)) return -1; //不为空，就获取尾指针的数据 return obj->rear->val; }
3.7 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->size == 0; }
3.8 判断循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size == obj->capacity; }
3.9 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) { //本质是链表，要一个个释放 QNode* pcur = obj->front;//用来遍历删除的 while (pcur) { QNode* next= pcur->next; free(pcur); pcur = next; } free(obj); }
3.10 全部代码
3.10.1 MyCircularQueue.h
#pragma once #include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h> typedef int QDataType; typedef struct QNode { struct QNode* next;//节点 QDataType val;//数据域 }QNode; typedef struct MyCircularQueue { QNode* front;//链表的头指针 QNode* rear;//链表的尾指针 int capacity;//记录链表的容量 int size;//记录链表的有效节点 }MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列 bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。 bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。 int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空，返回 - 1 。 int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空，返回 - 1 。 bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空 bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满 void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列
3.10.2 MyCircularQueue.c
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if (obj == NULL) { perror("malloc fail"); exit(1); } obj->front = obj->rear = NULL; obj->size = 0; obj->capacity = k; } bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value) { //如果为满了，直接就返回false if (myCircularQueueIsFull(obj)) return false; //不满足就创建节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->val = value; newnode->next = NULL; //创建成功，要考虑队列为空和不为空的情况 if (myCircularQueueIsEmpty(obj))//为空，让新节点成为头 obj->front = obj->rear = newnode; else//不为空，让tail继续往后遍历 { obj->rear->next = newnode; obj->rear = newnode; } obj->size++; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { //为空就没有删的必要了 if (myCircularQueueIsEmpty(obj)) return false; //不为空，删除头节点，让下一个节点成为新的头，然后释放掉 QNode* cur = obj->front->next; free(obj->front); obj->front = cur; obj->size--; return true; } int myCircularQueueFront(MyCircularQueue* obj) { //为空，返回1 if (myCircularQueueIsEmpty(obj)) return -1; //不为空，就获取头指针的数据 return obj->front->val; } int myCircularQueueRear(MyCircularQueue* obj) { //为空，返回1 if (myCircularQueueIsEmpty(obj)) return -1; //不为空，就获取尾指针的数据 return obj->rear->val; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->size == 0; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size == obj->capacity; } void myCircularQueueFree(MyCircularQueue* obj) { //本质是链表，要一个个释放 QNode* pcur = obj->front;//用来遍历删除的 while (pcur) { QNode* next= pcur->next; free(pcur); pcur = next; } free(obj); }
四、总结
我们会发现，在这边无论是用数组实现和链表实现，本质上我们只是从逻辑层次上把它认为是相连的，但是物理层次上并没有把它连在一起，虽然链表是可以做到相连的，但是相连的话会比较复杂，不相连我们也可以解决，只要保证我们能够控制得住边界问题就行！！ 
