商务型网站有哪些,动漫网页制作成品图片,上海公司推荐,网站稳定性不好的原因文章目录 前言一、方法一:数组法二、方法二.链表法总结 前言
前面有提到过队列的知识#xff0c;这次来说一下怎么设计一个循环队列 一.循环队列#xff08;力扣#xff09;
. - 力扣#xff08;LeetCode#xff09;. - 备战技术面试#xff1f;力扣提供海量技术面试资… 文章目录 前言一、方法一:数组法二、方法二.链表法总结 前言
前面有提到过队列的知识这次来说一下怎么设计一个循环队列 一.循环队列力扣
. - 力扣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个数据的循环队列就要开K1个空间不然无法实现判空和判满
方法一:数组法 注意数组法的判空和判满
判空:就是fronttail的时候就是空的判满:当tail1)%(k1)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判空判满 判空:就是fronttail的时候就是空的判满:当tail1)%(k1)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;//防止数组越界%(k1)把下标都控制在k之内//把越界的重置obj-tail % (obj-k 1);return true;
}
1.4删除 数组的删除不用向链表这些Pop直接覆盖就可以了 //数组的删除不用向链表这些Pop直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果是空的就不能删if (myCircularQueueIsEmpty(obj))return false;//头往前走obj-front;//止数组越界%(k1)把下标都控制在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;//防止数组越界%(k1)把下标都控制在k之内obj-tail % (obj-k 1);return true;
}//数组的删除不用向链表这些Pop直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果是空的就不能删if (myCircularQueueIsEmpty(obj))return false;//头往前走obj-front;//止数组越界%(k1)把下标都控制在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创建 这个是最难的部分就是在创建的时候要创造一个循环链表注意:这里其实已经开辟了k1个空间了,不懂的自己画图 MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq-front cq-tail (Node*)malloc(sizeof(Node));cq-k k;//创造一个循环链表//这里其实已经开辟了k1个空间了注意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销毁
这个是我自己犯的错误 curcur-next,为什么不可以因为cur等于头节点cur等于cur-next再释放cur相当于把头节点next释放掉了那我头节点后面的后面怎么去找呢所以我们是从头节点开始释放的把头节点用cur记录下来释放之前让头节点走了但是cur是头节点的傀儡节点所以释放cur相当于是释放头节点了。 void myCircularQueueFree(MyCircularQueue* obj) {//和单链表的销毁一样Node* tmp obj-front;while (obj-k 1){//curcur-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;//创造一个循环链表//这里其实已经开辟了k1个空间了注意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);
} 总结
用两种解法理解了循环队列想必对链表和队列的知识做到了巩固
