【C语言】【LeetCode】循环队列

阅读本书更多章节>>>>

---

目录

 （一）题目描述

（二）数据结构的选择

（三）函数接口的分析实现 

---

正文开始：

 （一）题目描述

        题目链接：622. 设计循环队列

        设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

        循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

        你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3circularQueue.enQueue(1);  // 返回 truecircularQueue.enQueue(2);  // 返回 truecircularQueue.enQueue(3);  // 返回 truecircularQueue.enQueue(4);  // 返回 false，队列已满circularQueue.Rear();  // 返回 3circularQueue.isFull();  // 返回 truecircularQueue.deQueue();  // 返回 truecircularQueue.enQueue(4);  // 返回 truecircularQueue.Rear();  // 返回 4

提示：

所有的值都在 0 至 1000 的范围内；操作数将在 1 至 1000 的范围内；请不要使用内置的队列库。

 （题目来源leetcode）

---

 

（二）数据结构的选择

         

        在C语言中，实现队列的数据结构可以选择使用数组或链表，具体选择哪种数据结构取决于应用的需求和对性能的要求。

数组：使用数组实现队列的优势是简单和高效。可以使用一个固定大小的数组来表示队列，并使用两个指针front和rear来分别指示队列的前端和后端。入队操作可以通过将元素添加到rear指针指向的位置来实现，而出队操作可以通过将元素从front指针指向的位置移除来实现。数组的缺点是长度固定，一旦实现的队列满了，就不能再添加元素。

链表：使用链表实现队列的优势是可以动态地调整队列的大小，没有固定的长度限制。可以使用一个指针来表示链表的头部，并使用另一个指针来表示链表的尾部。入队操作可以通过在链表的尾部添加节点来实现，而出队操作可以通过删除链表的头部节点来实现。链表的缺点是相对于数组来说，操作稍微复杂一些，需要维护指针的指向关系。

        综上所述，如果对队列的长度有明确的限制，可以选择使用数组实现队列。如果队列的长度不确定或需要频繁地进行插入和删除操作，可以选择使用链表实现队列。

        在循环队列的题目要求中，指定了队列的数据个数为K，因此本次实现队列采用数组的方式实现；通过定义一个结构体来方便对循环队列的维护：

typedef struct {    int* a;//动态数组    int k;//队列大小    int front;//队头指针，指向队头数据    int rear;//队尾指针，指向队尾数据的下一个位置} MyCircularQueue;

         如果rear指向的是队尾元素，那么数据个数为0和数据个数为1的情况无法区分，仔细想一想，这两种情况都是front和rear指针指向队首（数组下标为0的位置）；

 

         于是，我们可以通过多创建1个位置，让rear指向队尾元素的下一个位置——开辟k+1个位置，满足了存储k个数据的要求，又可以将数据个数为0和数据个数为1的情况区分开。

---

 

         一般认为：rear + 1 == front时，表示队列满了，但是当rear指向队尾时，rear + 1 就跑到队列外面了，为了解决这一问题，我们通过取模实现；

 //obj为实例化的对象 (obj->rear+1)%(obj->k+1)==obj->front

---

 得出结论：F和R的下标相同时，表示队列是空的。

---

（三）函数接口的分析实现 

（1） MyCircularQueue(k): 构造器，设置队列长度为 k。

MyCircularQueue* myCircularQueueCreate(int k) {    //申请并初始化环形链表    MyCircularQueue* que = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));    que->a = (int*)malloc(sizeof(int)*(k+1));//多开辟一个空间    que->front = 0;//指向队列头部    que->rear = 0;//指向队列尾部的下一个元素    que->k = k;    return que;}

 

（2） isEmpty(): 检查循环队列是否为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    return obj->front == obj->rear;}

 

（3） isFull(): 检查循环队列是否已满。

bool myCircularQueueIsFull(MyCircularQueue* obj) {    return (obj->rear+1)%(obj->k+1)==obj->front;}

 

（4） enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {    if(myCircularQueueIsFull(obj))//满了，返回假    {        return false;    }    //没有满，插入    obj->a[obj->rear++] = value;    obj->rear %= (obj->k+1);    return true;}

 

（5） deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))//空了，返回假    {        return false;    }    obj->front++;    if(obj->front == obj->k+1)        obj->front = 0;    return true;//没有空，出数据}

 

（6） Front: 从队首获取元素。如果队列为空，返回 -1 。

int myCircularQueueFront(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))    {        return -1;    }    return obj->a[obj->front];}

 

（7）Rear: 获取队尾元素。如果队列为空，返回 -1 。

int myCircularQueueRear(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))    {        return -1;    }    return obj->a[(obj->rear-1 + obj->k+1) % (obj->k+1)];}

 

（8）C语言没有析构函数，需要手动释放循环队列

void myCircularQueueFree(MyCircularQueue* obj) {        free(obj->a);    free(obj);}

 

---

完~

未经作者同意禁止转载

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-03-25/148178.html，文章来源：网络cs，作者：欧阳逸，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！