网站wap版,国内有名的网站设计公司,凡科登陆网站手机版,成都幕墙设计公司622. 设计循环队列 - 力扣#xff08;LeetCode#xff09; 思路 思路#xff1a;首先循环队列的意思是#xff1a;空间固定#xff0c;就是提前开辟好#xff0c;满了就不能插入了#xff0c;但是删除数据后仍有空间#xff0c;删除循环队列里面的数据后#xff0c;保…622. 设计循环队列 - 力扣LeetCode 思路 思路首先循环队列的意思是空间固定就是提前开辟好满了就不能插入了但是删除数据后仍有空间删除循环队列里面的数据后保留它的空间就能再插入数据即可以重复利用之前删除的空间。 这一题的循环让我们想到一个约瑟夫环的问题所以这题我们不加哨兵位因为加哨兵位转的时候就可能不太好操作。 猜想front和rear指向空指向同一个位置问题得单独判断插入第一个数据的时候如何因为你0个数据和1个数据的时候是分不清的。 对front和rear都指向空的疑问队列有头有尾front为头rear为尾两者为空指向同一节点意味着你插入一个数据时尾要往后走一下。这样rear有点像栈中的意思了top意味它不是指向栈顶元素而是指向栈顶元素的下一个。 对rear指向尾的下一个的疑问如果front、rear相等为空那么满时front也等于rear所以无法判断空和满。 因此到这里我们最好选择rear指向尾的下一个。 改进当然可以用size来记录链表的长度从而区分满不满代入接口发现找尾不好找所以我们能不能加一个rear的prev前驱指针从而来找尾但是好像有点不好控制如果这样的话还不如直接双向链表因此链表看起来虽然简单但越解决越复杂。这里我们想到对于数组能够随意访问下标我们可以尝试一下数组。 我们先来总结一下链表的点 1.rear为尾的下一个得改成双向才好控制。 2.rear指向最后一个初始化和为空的时候得做特殊处理。 因此综上所述用数组可能选择更好。 分析rear指向尾不好指向尾的话初始化的话你先初始化为0时你是初始化的0还是插入的0是无法判断的而且在删除的时候也要单独删除最后一个。所以我们使得rear指向尾的下一个。 其次虽然使得rear指向尾的下一个但是我们之前上述的疑问中所说的空和满无法判断这里我们称为假溢出问题。 以k4举例我们要多开一个空间对多开空间而言front等于rear即为空因为是数组吗我们可以直接用下标来进行访问循环的话就用一下下标回绕的思路就好了。 rear加1回绕到front就为满。当然回绕吗就是取模%k1对于删除来说删除一次就往后走一次当front等于rear时就为空。回绕的问题就解决了。 总结数组的好处数组好找这里rear是指向尾的下一个的运用数组可以找到尾。 ok我们要的条件是front指向头、rear指向尾的下一个、多开一个空间。 当然这题已经给定空间数组开辟好了空间之后初始化就可以控制了一个指向头一个指向尾的下一个所以相当于左闭右开。左闭右开才可以在最开始都为空如果是左闭右闭初始化就有问题我们在链表初始化的时候已经说过。 创建结构体 我们先看这个代码中给的这个结构体
typedef struct {} MyCircularQueue; 前面我们分析过为了实现这个循环队列我们要一个front代表头rear指向尾的下一个当然有个整型指针用来指向我们的数据,这里我们传递个我们这个数字的有效节点。
typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue; 构建循环队列
接下来开始创建对应创建的话先创建整个结构体在对里面的指针进行malloc记住这里我们多扩一个。当然也需要初始化一下构建的结构体里面的数据。
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int* b(int*)malloc(sizeof(int)*(k1));obj-ab;obj-front0;obj-rear0;obj-kk;return obj;
}
判空
之后我们先写一下判断是否为空frontrear时就为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-rear;
}判满 接下来是判断是否为满这个时候结对考虑轮转数组的问题了当然%k1对于没有到达下标为4的没有影响以k4时为例。 bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear1)%(obj-k1)obj-front;
}
释放
然后我们先写一下比较好写的释放吧就是释放obj的a再释放obj因为obj是指针这里传递的也是指针因此这里可以不用把obj置为空。
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
} 接下来还有四个接口没写分别是插入数据删除数据取队头元素取队尾元素。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {}bool myCircularQueueDeQueue(MyCircularQueue* obj) {}int myCircularQueueFront(MyCircularQueue* obj) {}int myCircularQueueRear(MyCircularQueue* obj) {} 取对头元素和取队尾元素
我们先来写取对头元素和取队尾元素两个接口吧首先这两个我们都得先判断他们是否为空如果为空就直接跳出循环取对头元素比较好取直接用front的下标就能取到但是对于取队尾元素呢好像不能直接写可能得考虑取模的情况因为可能会遇到下面这种情况。 int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[(obj-rear-1obj-k1)%(obj-k1)];}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
} 插入元素和删除元素 ok,到了这里我们还剩下插入元素和删除元素首先对应插入元素来说我们得先判断是否满了如果元素满了那么由于空间是给定的所以无法再继续插入了。如果没有满就先考虑下图这种情况 这时rear再最后一个这个时候要插入元素应该回转rear。 所以应该利用取模。而对于删除元素来说先要判断是否为空如果为空那么就无法删除就直接退出然后这里的回转运用到了我们找队尾元素的思路。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-rear]value;obj-rear(obj-rear1)%(obj-k1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj-front(obj-front1)%(obj-k1);return true;
} 最终代码
typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int* b(int*)malloc(sizeof(int)*(k1));obj-ab;obj-front0;obj-rear0;obj-kk;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear1)%(obj-k1)obj-front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-rear]value;obj-rear(obj-rear1)%(obj-k1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj-front(obj-front1)%(obj-k1);return true;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[(obj-rear-1obj-k1)%(obj-k1)];}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[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);
*/
