设计循环队列---力扣622

2024-06-04 18:28
文章标签 设计 力扣 队列 循环 622

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

1、题目

1.1基础设置与讲解

循环队列,即固定长度的队列,可以想象成一个环形队列

就类似于这种队列,队尾指针后会有一个空位,用于控制判断队列为空还是为满;

typedef int MyDataType;typedef struct {MyDataType front;MyDataType rear;MyDataType* a;MyDataType capacity;
} MyCircularQueue;

首先将int更名为MyDataType,方便对数据类型的统一管理;

并定义了一个结构体MyCircularQueue,

结构体内的成员

    MyDataType front;-----用于表示队列头指针
    MyDataType rear;-----尾指针
    MyDataType* a;-----存储队列元素的数组
    MyDataType capacity;-----队列所占空间大小

1.2节点创建

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* new = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (new == NULL){perror("malloc fail");exit(-1);}new->a = (int*)malloc(sizeof(int)*(k+1));new->front = new->rear = 0;new->capacity = k ;return new;
}

首先节点的创建必须有返回值,以供使用,这个返回值显而易见应该是MyCircularQueue*,因为返回的是一个结构体的存储。

先开辟一个大小为MyCircularQueue类型的空间,并且创建一个新结构体用于接收,对开皮的空间进行判定,如果开辟失败则返回perror,并结束进行,如果空间开辟成功,则将结构体内部成员进行初始化,防止出现野指针、空指针等问题。

其中capacity的大小为k,而

    new->a = (int*)malloc(sizeof(int)*(k+1));

此处的k是队列长度,而开辟空间的时候应该加一,因为使用a这个数组存储,而数组是从0开始编号,所以k+1;

1.3队列的满和空

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

第一个函数,判断队列是否为空,为空则返回true,如果不为空则返回false,当头指针与尾指针相同时,则代表队列此时为空,如下图;

第二个函数,判断队列是否为满,为满则返回true,如果不为满则返回false,

1.4入队列

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj->a[obj->rear] = value;obj->rear++;obj->rear = (obj->rear) % (obj->capacity+1);return true;
}

首先保证队列不为满,为满则无法进行存储;队尾指针进行数组数据输入。

 obj->rear = (obj->rear) % (obj->capacity+1);

这行代码的作用是将 rear 限制在 0 到 obj->capacity(包含)之间,以确保其不超过队列的容量。

其中如果只是obj->capacity的话只能在0~capacity-1,所以需要obj->capacity+1;

这是因为循环队列是一个环形结构,在到达数组末尾时会绕回到数组的起始位置,因此需要用取模操作来实现这种循环。

1.5出队列

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}obj->a[obj->front] = 0;obj->front++;obj->front = (obj->front) % (obj->capacity+1);return true;
}

1.6取头指针和尾指针的数据

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

1.7对队列进行释放

void myCircularQueueFree(MyCircularQueue* obj) {while (obj->a[obj->front] != 0){obj->a[obj->front] = 0;obj->front++;obj->front = (obj->front) % (obj->capacity+1);}obj->capacity = 0;obj->front = obj->rear = NULL;free(obj->a);free(obj);
}

2、总结

  1. 选择合适的数据结构: 循环队列通常基于数组实现,因为数组能够提供 O(1) 的随机访问时间,这对于循环队列中常见的插入和删除操作至关重要。但也可以使用链表实现循环队列,尤其在需要动态扩展队列大小时,链表实现可能更灵活。

  2. 确定队列的容量: 循环队列的容量应该是队列数组的大小减去 1,这是因为需要一个额外的位置来区分队列的空和满状态。

  3. 定义队列的属性: 需要定义队列结构体,并在其中包含头指针、尾指针以及存储元素的数组等属性。头指针和尾指针用于指示队列的起始位置和结束位置,而数组用于存储队列中的元素。

  4. 实现基本操作: 循环队列通常需要实现以下基本操作:

    • 入队操作(enqueue):向队尾插入元素。
    • 出队操作(dequeue):从队首删除元素。
    • 判空操作(isEmpty):检查队列是否为空。
    • 判满操作(isFull):检查队列是否已满。
    • 获取队首元素(front):返回队首元素的值,但不删除它。
    • 获取队尾元素(rear):返回队尾元素的值,但不删除它。

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



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

相关文章

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