[LeetCode]-622. 设计循环队列

2023-11-11 20:04

本文主要是介绍[LeetCode]-622. 设计循环队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

662. 设计循环队列

题目

思路

代码


662. 设计循环队列

622. 设计循环队列 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/design-circular-queue/

题目

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

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

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

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

示例:

思路

开辟一个大小为k+1的数组,可存放k个有效元素,队列头front和队列尾rear为数组下标,边插入删除数据边移动front和rear的位置,超过数组尾时回到数组头位置形成循环达到循环队列的效果。

实现循环队列效果如下:

难点1:

rear在数组尾时插入数据:rear刚好到数组尾时,要在rear上插入数据,rear要循环回到数组头的位置,而不是直接rear++就完了。

解决方法:

  • 取模思想:rear++后模上数组长度k+1,超过数组尾后回到数组头  如下图: 

难点2:

front在数组尾时删除数据:front刚好在数组尾位置上时,要从队头front删除元素,front后移超过数组尾了。

解决方法:

  • 取模思想:front超过数组尾时,模上数组长度k+1,front回到数组头位置  如下图:

难点3:

取队尾元素:当rear在数组下标为0的位置时,rear-1到-1的位置了,而队尾元素在数组尾的位置。

解决方法:

  • 加 if 语句,当rear在下标为0位置,取队尾元素位置为下标k+1。
  • 取模思想:取下标时(rear+(k+1)-1)%(k+1)如下图:

代码

(下面函数里面有要调用的函数如探空、探满这些,这些函数要放前面些,先声明再使用) 

typedef struct {int* a;//起始地址int front;//数组下标int rear;//数组下标int k;//有效数据个数
} MyCircularQueue;//构造器
MyCircularQueue* myCircularQueueCreate(int k) {//结构体开辟空间MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//数组开辟空间,多开辟一个可区分满和空obj->a=(int*)malloc(sizeof(int)*(k+1));//开始是空的状态obj->front=obj->rear=0;//传入的数(有效个数)给给kobj->k=k;return obj;
}
//探空和探满尽量位置往前放
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==(obj->front);
}//插入一个元素 成功返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断是否满if(myCircularQueueIsFull(obj))return false;//插入rear位置obj->a[obj->rear]=value;obj->rear++;//模上一个数组的长度,rear超过到数组尾可以循环回到数组头obj->rear%=(obj->k+1);return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断是否为空if(myCircularQueueIsEmpty(obj))return false;//队头front往后移 ++front++obj->front;//取模可在超过队尾时回到队头,取模不影响中间的移动obj->front%=(obj->k+1);return true;
}//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {//探空if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;else//模上k+1  rear+(k+1)-1 % (k+1)return obj->a[(obj->rear+obj->k) % (obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

这篇关于[LeetCode]-622. 设计循环队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/392519

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出(OutOfMemoryError),所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本(可能导致内存溢出)2.2 修改后的版本问题在

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi