网站建设专家如何选,网络集资网站怎么做,网站建设好后怎么制作网页,在本地怎么做网站力扣 622 循环队列
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构#xff0c;其操作表现基于 FIFO#xff08;先进先出#xff09;原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前…力扣 622 循环队列
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
你的实现应该支持如下操作
MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
思路分析
循环队列与普通队列相比在于它在逻辑上是环形的空间是固定的 所以就不能像普通队列一样去满队时扩容而是要提前开辟好所用的空间。
针对上述的所有功能我们先从判断队满和队空进行解释这是循环队列的核心。
isEmpty(): 检查循环队列是否为空在初始化时我们将front和back都设为0为最开始的位置每次放入数据back都会往后移动而出队的话front就会往后移当front移动到back位置时队就空了即当frontback时队列就为空了。
isFull(): 检查循环队列是否已满根据放数据的方法当队满时back会回到front的位置这里先不考虑如何实现循环这时就会和队空的情况重合了无法判断。 这里可以采取的方法可以定义一个size记录进队的个数但还有一种巧妙的方法。 定义多一个空间当往里面放数据时back不断向后移动如图队列有效长度为5队满的情况下back是不存放数据的此时发现只要back下一个为front队就满了。
Front: 从队首获取元素。如果队列为空返回 -1 直接将front对应的下标返回即可注意一下队空的返回条件。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真每插入一个元素back就会往后移动一位但当back移动到末尾而在此之前已经出队几个元素front也向前移动此时back就得移动到front之前的位置来达到循环的功能我们在之前的定义的数组大小是K1个当back超过k1的范围时就需要对k1进行取余控制在该范围内。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真没删除一个元素front就向后移动和插入元素一样防止front越界也得对front求余。Rear: 获取队尾元素。如果队列为空返回 -1 这里就有说法了如果back在front前面那直接返回back的位置即可但如果出现back在front前面的情况那就得另外考虑。我们可以找到back循环前的位置也就是它原本移动到的不进行循环的最后位置这就是队尾元素我们可以通过加上数组个数K来找到它原本的位置但这样一来也会出现越界的情况那我们在对数组长度取余就行了。
typedef struct {int* a;//存放数据的数组int front;//队头int back;队尾int k;//数据个数} MyCircularQueue;
//后面涉及调用顺序的问题提前声明一下
MyCircularQueue* myCircularQueueCreate(int k);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
bool myCircularQueueDeQueue(MyCircularQueue* obj);
int myCircularQueueFront(MyCircularQueue* obj);
int myCircularQueueRear(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
void myCircularQueueFree(MyCircularQueue* obj);
void myCircularQueueFree(MyCircularQueue* obj);//初始化
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;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//如果为空返回false{return false;}obj-a[obj-back]value;obj-back;obj-back%(obj-k1);//back后每次取余一下实现循环的功能当back在数组范围内求余保持不变大于则会回到起始位置实现循环return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front%(obj-k1);//和back操作一样每次取余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-backobj-k)%(obj-k1)];//先k找到back循环前的原本位置防止越界进行求余}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-backobj-front;}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back1)%(obj-k1)obj-front;}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj myCircularQueueCreate(k);* bool param_1 myCircularQueueEnQueue(obj, value);* bool param_2 myCircularQueueDeQueue(obj);* int param_3 myCircularQueueFront(obj);* int param_4 myCircularQueueRear(obj);* bool param_5 myCircularQueueIsEmpty(obj);* bool param_6 myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/
