循环队列的意思就是用限定的内存空间来完成队列相关操作。在结构上是循环的，在物理上可以是链表或者是数组
那么我们首先从数组来实现循环队列：
数组型
数组的内存不是环形的，所以我们需要用到%来实现下标的循环。
那么循环队列里面最重要的就是判断我们这个队列还能不能增删。
这里我们判断能不能删很好判断，就是头指针和尾指针是否重合。但是我们判断是否能继续删呢？
我们发现依然是头尾指针重合。那么这就不好搞了
我们可以想到的两种解决方案：
1：我们定义一个size来判断长度
2：我们额外开辟一个内存，当我们将队列填满的时候，尾指针是在头指针的前面一格
两个都可以，这里我用后面的一种。
首先是建立结构体，分别是数组，尾指针，头指针，以及长度
typedef struct {
int* arr;
int begain;
int tail;
int size;
} MyCircularQueue;
其次是初始化不用多说
MyCircularQueue* myCircularQueueCreate(int pk) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (!obj)return NULL;
obj->size = pk;
obj->arr= (int*)malloc(sizeof(int)*(pk+1));
if (!obj->arr)return NULL;
obj->begain = obj->tail = 0;
return obj;
}
判断空的，上面讨论过
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if (!obj||!obj->arr)return false;
return obj->begain == obj->tail;
}
判满的，上面讨论过
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if (!obj)return false;
return (obj->tail + 1) % (obj->size + 1) == obj->begain;
}
如队列的，入队列前要判断是否满了
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (!myCircularQueueIsFull(obj)) {
obj->arr[obj->tail++] = value;
obj->tail %= (obj->size + 1);
return true;
}
else {
return false;
}
}
出队列函数，先判断是否为空
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (!myCircularQueueIsEmpty(obj)){
obj->begain++;
obj->begain%= obj->size + 1;
return true;
}
else {
return false;
}
}
返回队列的头部元素
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))return -1;
return obj->arr[obj->begain];
}
返回队列尾部的元素
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))return -1;
int k = obj->tail == 0 ? obj->size : obj->tail-1;
return obj->arr[k];
}
销毁队列，释放队列内存
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
}
也是过了
链表型
我们换一个链表来写写看：
首先链表虽然可以构成循环结构，但是我们如果要返回队列的尾部元素怎么办呢。
这里有两种解决方法：
一种是用双向链表。
一种是每次指向末尾的前一个节点。
这里我用第二种来实现一下：
先是结构体的创建
typedef struct listnode {
int data;
struct listnode* next;
}listnode;
typedef struct {
listnode* head;
listnode* tail;
} MyCircularQueue;
再是队列的创建。这里我们创建一个哨兵节点header来方便我们写代码，最后再释放掉
MyCircularQueue* myCircularQueueCreate(int k) {
int num = k + 1;
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (!obj)return NULL;
listnode* header = (listnode*)malloc(sizeof(listnode));
if (!header)return NULL;
obj->head = NULL;
obj->tail = header;
header->next = obj->head;
while (num--) {
listnode* cur = (listnode*)malloc(sizeof(listnode));
if (!cur)return NULL;
if (!obj->head)
obj->head = cur;
obj->tail->next = cur;
obj->tail = obj->tail->next;
}
free(header);
obj->tail->next = obj->head;
return obj;
}
判断是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if (!obj)return false;
return obj->tail->next == obj->head;
}
判断是否满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if (!obj)return false;
return obj->tail->next->next == obj->head;
}
push进队列，注意判断满
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
return false;
else
{
obj->tail->next->data = value;
obj->tail = obj->tail->next;
return true;
}
}
队列pop数据，注意判断空
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return false;
}
else {
obj->head = obj->head->next;
return true;
}
}
返回队列开头的数据，注意判断空
int myCircularQueueFront(MyCircularQueue* obj) {
if (!obj || myCircularQueueIsEmpty(obj)) {
return -1;
}
else {
return obj->head->data;
}
}
同理
int myCircularQueueRear(MyCircularQueue* obj) {
if (!obj || myCircularQueueIsEmpty(obj)) {
return -1;
}
else {
return obj->tail->data;
}
}
释放内存就是一个链表的内存释放
void myCircularQueueFree(MyCircularQueue* obj) {
if (!obj)return;
if (obj->head->next = NULL) {
free(obj->head);
free(obj);
}
else {
listnode* pnewptr = obj->head, * newptr = obj->head->next;
while (newptr) {
free(newptr);
pnewptr = newptr;
newptr = newptr->next;
}
free(pnewptr);
free(obj);
}
}
