网站视频下载,品牌网站建设制作,太原网站开发培训,做网站用vue还是用jquery. - 力扣#xff08;LeetCode#xff09;. - 备战技术面试#xff1f;力扣提供海量技术面试资源#xff0c;帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/design-circular-queue/
1.题目
设计你的循环队列实现。 循环队列是一…. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/design-circular-queue/
1.题目
设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 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 的范围内请不要使用内置的队列库。
2.解析 我们设计循环队列的关键是要有效地利用数组空间并且能够处理队列满和队列空的情况。下面是一种使用数组实现循环队列的解法其中backk1的含义是为了区分队列满和队列空的情况。 首先我们需要定义一个固定大小的数组a来存储队列元素以及两个指针front和back来标记队列的头部和尾部。 初始化时将front和back都设置为0表示队列为空。 判断队列是否为空isEmpty 判断front是否等于back如果相等则表示队列为空返回true;否则返回false。 判断队列是否已满isFull 判断back1%k是否等于front如果相等则表示队列已满返回true;否则返回false。 入队操作enqueue 首先判断队列是否已满即back1%k是否等于front。如果相等则表示队列已满无法继续入队。如果队列未满则将元素放入back指向的位置并将back指针向后移动一位即backback1%k。 出队操作dequeue 首先判断队列是否为空即front是否等于back。如果相等则表示队列为空无法进行出队操作。如果队列不为空则将front指向的元素出队并将front指针向后移动一位即frontfront1%k。 获取队头元素getFront 首先判断队列是否为空即front是否等于back。如果相等则表示队列为空无法获取队头元素。如果队列不为空则返回front指向的元素。 3.代码总结
1.构造器函数用于创建一个指定长度的循环队列。
首先通过malloc函数动态分配了一个MyCircularQueue结构体的内存空间并将其地址赋给指针变量obj。
然后通过malloc函数再次动态分配了一个整型数组的内存空间并将其地址赋给指针变量obj-a。这个数组的长度为k1多分配了一个空间用于判断队列是否满的条件。
接着将队列的头指针front和尾指针back都初始化为0。
最后将k的值赋给队列的长度k。
最终返回指向创建的循环队列的指针obj。
MyCircularQueue* myCircularQueueCreate(int k)//构造器设置队列长度为 k {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a(int*)malloc(sizeof(int)*(k1));obj-front0;obj-back0;obj-kk;return obj;
}
2. 检查循环队列是否为空 函数的返回值是一个bool类型的值表示循环队列是否为空。
如果循环队列为空则返回true否则返回false。
函数的实现是通过比较循环队列的front和back的值来判断循环队列是否为空。
如果它们相等说明队列中没有元素即队列为空返回true否则返回false。
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//检查循环队列是否为空。{return obj-frontobj-back;
}
3. 检查循环队列是否已满
函数的返回值是一个bool类型的值表示循环队列是否已满。如果循环队列已满则返回true否则返回false。
函数的实现是通过计算(back1)%(k1)与front的值是否相等来判断循环队列是否已满。
如果它们相等说明队列已满返回true否则返回false。
这里使用了取模运算来实现循环队列的特性。由于循环队列的尾部和头部相连所以需要将back的下一个位置计算为(back1)%(k1)其中k为队列长度。如果这个值与front相等说明队列已满。
bool myCircularQueueIsFull(MyCircularQueue* obj)//检查循环队列是否已满。{return (obj-back1)%(obj-k1)obj-front;
}
4. 向循环队列插入一个元素
函数的返回值是一个bool类型的值表示插入操作是否成功。
如果插入成功则返回true否则返回false。
函数的实现首先通过调用myCircularQueueIsFull函数来检查循环队列是否已满。
如果队列已满则表示无法插入新元素直接返回false。
如果队列未满则将value值插入到队列的obj-back位置并且将obj-back的值加1。为了保证obj-back在[0, k]的范围内需要使用取模运算进行处理即obj-back%(obj-k1)。这样可以使back的值在超出队列长度时重新回到队列起始位置。
最后返回true表示插入成功。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//向循环队列插入一个元素。如果成功插入则返回真。{if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-back]value;obj-back;obj-back%(obj-k1);//将 obj-back 除以 (obj-k1) 的余数然后将结果赋值给 obj-back。return true;
}
5. 循环队列中删除一个元素
函数的返回值是一个bool类型的值表示删除操作是否成功。
如果删除成功则返回true否则返回false。
函数的实现首先通过调用myCircularQueueIsEmpty函数来检查循环队列是否为空。
如果队列为空则表示无法执行删除操作直接返回false。
如果队列不为空就执行删除操作。
即将obj-front的值加1然后使用取模运算来确保obj-front在[0, k]的范围内。
最后返回true表示删除成功。
bool myCircularQueueDeQueue(MyCircularQueue* obj)//从循环队列中删除一个元素。如果成功删除则返回真。{if(myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front%(obj-k1);return true;}
6.循环队列中获取队首元素
函数的返回值是一个int类型的值表示队首元素。如果队列为空则返回-1。
函数的实现首先通过调用myCircularQueueIsEmpty函数来检查循环队列是否为空。如果队列为空则返回-1。
如果队列不为空则直接返回obj-a[obj-front]即队首元素的值。
int myCircularQueueFront(MyCircularQueue* obj)//从队首获取元素。如果队列为空返回 -1 。{if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
} 7.获取循环队列的队尾元素
首先判断队列是否为空通过调用函数myCircularQueueIsEmpty(obj)来判断。如果队列为空则返回-1。如果队列不为空使用取模运算(obj-backobj-k)%(obj-k1)来计算队尾元素的下标。这里obj-back表示队尾元素的下标obj-k表示队列的容量减1。这样做是为了实现循环队列的封装。返回队尾元素obj-a[(obj-backobj-k)%(obj-k1)]即对应下标位置上的元素值。
int myCircularQueueRear(MyCircularQueue* obj)//: 获取队尾元素。如果队列为空返回 -1 。{if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[(obj-backobj-k)%(obj-k1)];
}
8.释放循环队列的内存空间
首先通过调用free(obj-a)来释放存储队列元素的数组的内存空间。obj-a指向数组的起始地址free(obj-a)将释放该内存空间。
然后通过调用free(obj)来释放存储循环队列结构体的内存空间。obj指向循环队列结构体的起始地址free(obj)将释放该内存空间。
通过这两个free()函数的调用可以确保循环队列所占用的所有内存空间都被释放防止内存泄漏。
void myCircularQueueFree(MyCircularQueue* obj){free(obj-a);free(obj);
}9.总的代码
typedef struct
{int *a;int front;int back;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k)//构造器设置队列长度为 k {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a(int*)malloc(sizeof(int)*(k1));obj-front0;obj-back0;obj-kk;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//检查循环队列是否为空。{return obj-frontobj-back;
}bool myCircularQueueIsFull(MyCircularQueue* obj)//检查循环队列是否已满。{return (obj-back1)%(obj-k1)obj-front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//向循环队列插入一个元素。如果成功插入则返回真。{if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-back]value;obj-back;obj-back%(obj-k1);//将 obj-back 除以 (obj-k1) 的余数然后将结果赋值给 obj-back。return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)//从循环队列中删除一个元素。如果成功删除则返回真。{if(myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front%(obj-k1);return true;}int myCircularQueueFront(MyCircularQueue* obj)//从队首获取元素。如果队列为空返回 -1 。{if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj)//: 获取队尾元素。如果队列为空返回 -1 。{if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[(obj-backobj-k)%(obj-k1)];
}void myCircularQueueFree(MyCircularQueue* obj){free(obj-a);free(obj);
}
