实训建设网站的目的,什么网站 是cms系统下载地址,自助建网站,新华书店网站建设今天我们一起来做一道关于队列的OJ题目#xff0c;这是力扣题目622题#xff0c;点击题目链接可以直接跳转#xff0c;https://leetcode.cn/problems/design-circular-queue/ 首先#xff0c;我们看到要求#xff0c;需要我们实现哪些功能#xff1f; 我们需要设置队列长…今天我们一起来做一道关于队列的OJ题目这是力扣题目622题点击题目链接可以直接跳转https://leetcode.cn/problems/design-circular-queue/ 首先我们看到要求需要我们实现哪些功能 我们需要设置队列长度K队首元素队尾元素插入元素删除元素判断空判断满。那这么多接口我们要从哪里入手呢我们现在做题无外乎要么用顺序表的方式要么用链表的方式使用两者其实都可以今天我们就用顺序表的方式实现吧。既然使用顺序表也就是数组那么我们要考虑一点在什么情况下这个队列为空要确定这个循环队列为空那就需要保证头元素的下标和尾元素的下标相等才可以假设我们设头元素下标为frontback为尾元素下一个位置因为我们要区分back0时到底是有一个元素还是没有元素的情况。即要保证frontback时队列为空。 考虑了队列为空的情况那什么时候循环队列满了呢满了就是已经不能再放其它元素也就是尾位置back就要追上front了也就是backfront吗那我们想一想队列为空的时候和队列为满的时候都是frontback我们要怎么区分这两种情况呢
我们不妨设置队列长度K的时候多开一个空间即k1,我们保证k1个空间最多只使用k个留出一个位置让back1front时为满队列。这样就能区分队列满和队列空的情况了。 下来我们开始做题。
typedef struct {int *a;//数组int front;//队首元素下标int back;//队尾元素下标的下一个位置int k;//队列大小
} MyCircularQueue;
我们定义完结构体变量下来需要对结构题的成员初始化即
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a(int*)malloc(sizeof(int)*(k1));obj-front0;obj-back0;obj-kk;return obj;}
为什么我们要给开k1个空间呢原因我们在上面讲过了就是为了让队列满的情况时back1front。
下来我们先把容易实现的接口先完成先把什么时候为空什么时候为满实现。
为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-back;
}
为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-back1obj-front;//这样做合适吗
}我们要考虑到这是一个循环队列下面这种情况能满足吗 back要一直往后走吗 显然不是这是一个循环队列当back走到k时下一次就要回到起点那怎么表示呢我们不妨这样表示(obj-back1)%(obj-k1)obj-front这个队列一共有k1个空间我们知道如果一个小的数%一个比自己大的数是不会改变值的所以如果back1k1,此时back就要回到起点了。所以判断队列满我们可以这样写
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back1)%(obj-k1)obj-front;
} 下面我们写插入接口
这是一个bool类型也就是要返回true和false,那什么时候要返回false呢注意这是往队列插入元素如果队列已经满了我们就插不了元素了。剩下就可以正常插入了直接让obj-a[obj-back]value即可再让obj-back。注意到这里我们还要需要检查back有没有超过队列空间的大小即我们需要在后面让obj-back%obj-k1;即
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj-a[obj-back]value;obj-back;obj-back(obj-back)%(obj-k1);return true;
}
队列删除
删除接口同样是bool类型我们要判断什么时候删除失败当然就是队列为空的时候删除失败我们要先检查队列是否为空再删除删除非常简单直接让front就可以了front一直在,有没有可能front也会超出队列的空间大小当然有可能所以我们也需要对front检查一下即obj-front%obj-k1;
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj-front;obj-front(obj-front)%(obj-k1);return true;
}
下面就是返回对头元素
题目里说了如果队列为空就返回-1这种情况我们也要处理一下其余就直接返回obj-a[obj-front]即可。
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];
}队尾元素
同样我们也要处理一次队列为空返回-1的情况然后直接返回obj-a[obj-back-1]可以吗
我们思考一下如果back0呢我说的不是队列为空时因为为空时我们已经处理了我说的时当back已经走了至少一轮重新回到起点的情况此时的back-1就成-1了那我们怎么处理呢我们要知道这种情况下的back时已经被取模了k1后那我们不妨可以给back-1k1再给它取模k1;即(obj-back-1)(obj-k1)%(obj-k1);怎么理解这个公式还是那句话back-1不可能大于k1一个数%比他小的数值不变(ab)%b,如果a比b小且a是正数那这个值是不变的这一种情况也就对应了我们此处back!0的情况如果back0,尾元素就在k的位置那back-1就是-1他再加上k1再%k1要比k1小所以结果就是k那个位置。
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[(obj-back-1obj-k1)%(obj-k1)];
}
到这里这道题就大功告成了此时我们运行报了一个这样错误
是因为我们在前面调用了就很多次队列为空为满的情况也没有声明所以我们可以把判断队列为空为满挪到插入接口前面就可以啦。
好啦本次题目就到这里了希望大家能够多多支持我们下次再见
