文章目录
- 前言
- 一、方法一:数组法
- 二、方法二.链表法
- 总结
前言
前面有提到过队列的知识，这次来说一下怎么设计一个循环队列
一.循环队列（力扣）
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/design-circular-queue/description/
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
思路:循环队列无论使用数组实现还是链表实现，都要多开一个空间，也就意味着要是存K个数据的循环队列，就要开K+1个空间，不然无法实现判空和判满
方法一:数组法
注意数组法的判空和判满
判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的
1.0初始化
初始化一个数组，有头front，尾tail，数组明a
typedef struct {int* a;int front;int tail;int k;} MyCircularQueue;1.1创建
MyCircularQueue* myCircularQueueCreate(int k)
{//开辟一个循环队列的空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开辟一个数组的空间用来实现循环队列，要多开辟一个q->a = (int*)malloc(sizeof(int) * (k + 1));//初始化q->front = q->tail = 0;q->k = k;return q;
}1.2判空，判满
判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k + 1) == obj->front;
}1.3插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//如果循环队列是满的就不能插入if (myCircularQueueIsFull(obj))return false;//把末尾的值插入值obj->a[obj->tail] = value;//然后tail的往后走++obj->tail;//防止数组越界，%(k+1)把下标都控制在k之内//把越界的重置obj->tail %= (obj->k + 1);return true;
}1.4删除
数组的删除不用向链表这些Pop，直接覆盖就可以了
//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果是空的就不能删if (myCircularQueueIsEmpty(obj))return false;//头往前走++obj->front;//止数组越界，%(k+1)把下标都控制在k之内obj->front %= (obj->k + 1);return true;
}
1.5拿出最后一个数
int myCircularQueueRear(MyCircularQueue* obj) {//如果是空的就拿不了if (myCircularQueueIsEmpty(obj)){return -1;}//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数if (obj->tail == 0)return obj->a[obj->k];elsereturn obj->a[obj->tail - 1];
}1.6拿出头数据和销毁
//直接拿出
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}1.7总代码
注意把判空判满提前引用！！！
typedef struct {int* a;int front;int tail;int k;} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k)
{//开辟一个循环队列的空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开辟一个数组的空间用来实现循环队列，要多开辟一个q->a = (int*)malloc(sizeof(int) * (k + 1));//初始化q->front = q->tail = 0;q->k = k;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//如果循环队列是满的就不能插入if (myCircularQueueIsFull(obj))return false;//把末尾的值插入值obj->a[obj->tail] = value;//然后tail的往后走++obj->tail;//防止数组越界，%(k+1)把下标都控制在k之内obj->tail %= (obj->k + 1);return true;
}//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果是空的就不能删if (myCircularQueueIsEmpty(obj))return false;//头往前走++obj->front;//止数组越界，%(k+1)把下标都控制在k之内obj->front %= (obj->k + 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;}//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数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;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}方法二.链表法
2.0初始化
先初始化一个链表，在定义结构
typedef struct listNode {int data;struct Node* next;
}Node;typedef struct {Node* front;Node* tail;int k;
}MyCircularQueue;
2.1创建
这个是最难的部分，就是在创建的时候要创造一个循环链表，注意:这里其实已经开辟了k+1个空间了,不懂的自己画图
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->front = cq->tail = (Node*)malloc(sizeof(Node));cq->k = k;//创造一个循环链表//这里其实已经开辟了k+1个空间了注意while (k){Node* cur= (Node*)malloc(sizeof(Node));cur->data = 0;cur->next = NULL;cq->tail->next =cur;cq->tail= cq->tail->next;k--;}//开辟好了之后还要把尾和头发一起cq->tail->next =cq->front;cq->tail= cq->front;return cq;
}2.2判空，判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->tail->next == obj->front;
}
2.3插入
//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判满if (myCircularQueueIsFull(obj))return false;//直接在尾上插入obj->tail->data = value;obj->tail= obj->tail->next;return true;
}2.4删除
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//先判空if (myCircularQueueIsEmpty(obj))return false;//头删obj->front = obj->front->next;return true;
}2.5去头元素
int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj->front->data;
}2.6去尾元素
注意尾是前一个元素，所以不可以直接拿出，实在不理解看一下直接的动图
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;//去找尾Node* cur= obj->front;while (cur->next != obj->tail)cur= cur->next;return cur->data;}
2.7销毁
这个是我自己犯的错误
cur=cur->next,为什么不可以，因为cur等于头节点，cur等于cur->next，再释放cur，相当于把头节点next释放掉了，那我头节点后面的后面怎么去找呢？所以我们是从头节点开始释放的，把头节点用cur记录下来，释放之前让头节点走了，但是cur是头节点的傀儡节点，所以释放cur相当于是释放头节点了。
void myCircularQueueFree(MyCircularQueue* obj) {//和单链表的销毁一样Node* tmp = obj->front;while (obj->k + 1){//cur=cur->next；为什么不可以obj->front = obj->front->next;free(tmp);tmp = obj->front;obj->k--;}free(obj);
}2.8总代码
注意把判空判满提前引用！！！
typedef struct listNode {int data;struct Node* next;
}Node;typedef struct {Node* front;Node* tail;int k;
}MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->front = cq->tail = (Node*)malloc(sizeof(Node));cq->k = k;//创造一个循环链表//这里其实已经开辟了k+1个空间了注意while (k){Node* cur= (Node*)malloc(sizeof(Node));cur->data = 0;cur->next = NULL;cq->tail->next =cur;cq->tail= cq->tail->next;k--;}//开辟好了之后还要把尾和头发一起cq->tail->next =cq->front;cq->tail= cq->front;return cq;
}
//插入
//他这个题目其实是提前开辟好了，让你直接插入就可以了
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判满if (myCircularQueueIsFull(obj))return false;//直接在尾上插入obj->tail->data = value;obj->tail= obj->tail->next;return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//先判空if (myCircularQueueIsEmpty(obj))return false;//头删obj->front = obj->front->next;return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj->front->data;
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;//去找尾Node* cur= obj->front;while (cur->next != obj->tail)cur= cur->next;return cur->data;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->tail->next == obj->front;
}void myCircularQueueFree(MyCircularQueue* obj) {//和单链表的销毁一样Node* tmp = obj->front;while (obj->k + 1){obj->front = obj->front->next;free(tmp);tmp = obj->front;obj->k--;}free(obj);
}
总结
用两种解法理解了循环队列，想必对链表和队列的知识做到了巩固
