当前位置：首页 > news >正文

leetcode设计循环队列（链表方式来实现）

news 来源：原创 2024/5/12 16:08:14

在这里插入图片描述
上次我们那个设计循环队列的时候用的是数组，因为那个时候还是不太会链表，现在有了链表的思路，我们一起来看看解题步骤吧。

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);
*/