成都代做网站,正规的网站制作,上海企业建站咨询,12306网站开发时间上次我们那个设计循环队列的时候用的是数组#xff0c;因为那个时候还是不太会链表#xff0c;现在有了链表的思路#xff0c;我们一起来看看解题步骤吧。
https://leetcode.cn/problems/design-circular-queue/description/
设计循环队列 那我们其实最主要的就是我们这个… 上次我们那个设计循环队列的时候用的是数组因为那个时候还是不太会链表现在有了链表的思路我们一起来看看解题步骤吧。
https://leetcode.cn/problems/design-circular-queue/description/
设计循环队列 那我们其实最主要的就是我们这个队列怎么定义他的定义方式其实是和顺序表一样的给一个capacity但是我们这里实现的方式是链表我们插入的时候就是malloc一个节点但是我们这里其实表面上看起来是循环队列其实是下面这个图我们这里假设k是四个节点。 这个是满的时候但是我们这里满用的不是我们下面的节点是不是head而是size capacity就行了所以我们这里的判空和判断有没有满是很简单的。我们可以来看看接口函数和结构体是怎么定义的。
我们这里就好像把顺序表的优点和链表的链式结构合在一起进行使用。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-size 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-size obj-capacity;
}判空和判断是不是满的时候就是要比数组的方式简单而且一开始的时候我想的是先搞出一个循环链表然后进行尝试但是给我的结果就是很难取判断什么时候是满的什么时候是空的还有head和tail的指向也不是很好的解决。 可以看到这样的方式很难哪怕是找到问题在那小编因为实力不行还是不知道怎么改还是看了leetcode的解题才有思路。
那后面的插入就和链表的尾插是很相似的所有我这里就不过多的讲解。 这里需要注意的就是第一次的插入我们因为没有哨兵位的头节点所有要先来判断一下否则就是对空指针的访问了。 删除也更简单只要移动head就可以了而且我们可以看这种情况就是我们插入插满之后删掉之后head最后还是变成空然后在进行插入的时候就协接上了所以这个方法很好那完整的代码就放在下面了。
typedef struct newnode
{struct newnode* next;int val;
}Node;typedef struct {int size;int capacity;Node* head;Node* tail;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-size obj-capacity 0;obj-capacity k;obj-head obj-tail NULL;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-size 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-size obj-capacity;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(!myCircularQueueIsFull(obj)){Node* newnode (Node*)malloc(sizeof(Node));newnode-next NULL;newnode-val value;if(obj-head NULL){obj-tail obj-head newnode;}else{obj-tail-next newnode;obj-tail newnode;}obj-size;return true;}return false;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(!myCircularQueueIsEmpty(obj)){obj-head obj-head-next;obj-size--;return true;}return false;
}int myCircularQueueFront(MyCircularQueue* obj) {if(!myCircularQueueIsEmpty(obj)){return obj-head-val;}return -1;
}int myCircularQueueRear(MyCircularQueue* obj) {if(!myCircularQueueIsEmpty(obj)){return obj-tail-val;}return -1;
}void myCircularQueueFree(MyCircularQueue* obj) {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);
*/
