[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

相关文章

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

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