网站首页大小,有域名了网站怎么做,大新网站制作,济南网站优化推广公司电话从今天开始我会开启一个专栏leetcode每日一题#xff0c;大家互相交流代码经验#xff0c;也当作我每天练习的自我回顾。第一天的内容是leetcode622.设计循环队列。
一、题目详细
设计你的循环队列实现。 循环队列是一种线性数据结构#xff0c;其操作表现基于 FIFO#…从今天开始我会开启一个专栏leetcode每日一题大家互相交流代码经验也当作我每天练习的自我回顾。第一天的内容是leetcode622.设计循环队列。
一、题目详细
设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
你的实现应该支持如下操作
MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例
MyCircularQueue circularQueue new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4提示
所有的值都在 0 至 1000 的范围内操作数将在 1 至 1000 的范围内请不要使用内置的队列库。
虽然这是一道中等难度的题但是理解了这道题的关键完全没有那么难。
二、解题要点
判断队满和队空的条件空间开辟的大小确定
其实这俩点总归是一点就是不要越界因为我们这里主要是以数组的形式去实现这里的循环队列。
队满和队空的判断条件
主要的有两种方法 留一个空间空置满:rear 1 front空就是rear front增加一个size变量记录数据个数。空:size0 满:size MaxSize 如果我用第一个方法的话就会浪费一个空间用第二个则不会有这样的情况我提供一些图画来帮大家理解。
队空时 第一种方法队满时 第二种方法队满时 这里我给大家展示第一种代码的实现大家可以自己去实现一下第二种方法
bool myCircularQueueIsEmpty(MyCircularQueue* queue) {return queue-front queue-rear;
}bool myCircularQueueIsFull(MyCircularQueue* queue) {return((queue-rear 1) % queue-capacity queue-front);
}
我这里用queue-capacity代替了MaxSize这里面涉及到里一个取模为什么要这么做呢其实是为了解决我们的第二个关键点防止越界。 越界处理
队列的定义是FIFO先进先出是只允许在一段删除在另一端插入的线性表。
允许插入的一端叫做队尾rear允许删除的一端叫做队头front 上面是入队的动态操作哈哈哈哈手画可能动图有点粗糙但是我们可以看到6是无法入队的因为我们按照前面的队满的判断条件(queue-rear1)%queue-capacityfront,此时已经判断为满也就是我们前面所说的会有一个空间被浪费那我们取模在什么时候用的上呢我现在就给大家举个例子 如图所示如果这里我不进行取模我的6仍旧是无法入队的并且我的rear还会越界。同样在出队时取模也有同样的妙处。
好啦把这俩个关键点弄懂基本上这道题就没有问题了接下来我给大家展示这道题的完整代码并配上一组main函数作为自练习的测试样例大家也可以对样例进行修改测试。
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stdlib.h
#include stdbool.htypedef struct {int capacity;int front;int rear;int* elements;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* queue (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (queue NULL){perror(malloc);return NULL;}queue-capacity k 1;queue-front 0;queue-rear 0;;queue-elements (int*)malloc(sizeof(int) * queue-capacity);if (queue-elements NULL){perror(malloc);free(queue);return NULL;}return queue;
}bool myCircularQueueEnQueue(MyCircularQueue* queue, int value) {if ((queue-rear 1) % queue-capacity queue-front){return false;}else{queue-rear (queue-rear 1) % queue-capacity;queue-elements[queue-rear] value;return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* queue) {if (queue-front queue-rear){return false;}else{queue-front (queue-front 1) % queue-capacity;return true;}
}int myCircularQueueFront(MyCircularQueue* queue) {if (queue-rear queue-front){return -1;}else{return queue-elements[(queue-front 1) % queue-capacity];}
}int myCircularQueueRear(MyCircularQueue* queue) {if (queue-rear queue-front){return -1;}else{return queue-elements[queue-rear];}
}bool myCircularQueueIsEmpty(MyCircularQueue* queue) {return queue-front queue-rear;
}bool myCircularQueueIsFull(MyCircularQueue* queue) {return((queue-rear 1) % queue-capacity queue-front);
}
void myCircularQueueFree(MyCircularQueue* queue) {if (queue){free(queue-elements);free(queue);}
}int main() {MyCircularQueue* queue myCircularQueueCreate(3); // 创建容量为3的循环队列printf(入队 1: %s\n, myCircularQueueEnQueue(queue, 1) ? 成功 : 失败);printf(当前队尾元素: %d\n, myCircularQueueRear(queue)); // 预期输出 1printf(当前队头元素: %d\n, myCircularQueueFront(queue)); // 预期输出 1printf(出队操作: %s\n, myCircularQueueDeQueue(queue) ? 成功 : 失败);printf(当前队头元素: %d\n, myCircularQueueFront(queue)); // 预期输出 -1printf(出队操作: %s\n, myCircularQueueDeQueue(queue) ? 成功 : 失败);printf(当前队头元素: %d\n, myCircularQueueFront(queue)); // 预期输出 -1printf(入队 2: %s\n, myCircularQueueEnQueue(queue, 2) ? 成功 : 失败);printf(入队 3: %s\n, myCircularQueueEnQueue(queue, 3) ? 成功 : 失败);printf(入队 4: %s\n, myCircularQueueEnQueue(queue, 4) ? 成功 : 失败);printf(入队 5: %s\n, myCircularQueueEnQueue(queue, 5) ? 成功 : 失败); // 预期失败因为队列已满// 释放队列内存myCircularQueueFree(queue);return 0;} 运行结果如下图 有什么问题欢迎大家留言当看到这里啦给个小心心吧
