设计循环队列——oj题622

2024-01-06 00:44
文章标签 设计 队列 循环 oj 622

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

在这里插入图片描述在这里插入图片描述

.

个人主页:晓风飞
专栏:LeetCode刷题|数据结构|Linux
路漫漫其修远兮,吾将上下而求索


文章目录

  • 题目要求:
    • 应该支持如下操作:
    • 示例:
    • 提示:
  • 结构体定义
  • 队列的创建
  • 基本操作
    • 判断队列是否为空:
    • 判断队列是否已满:
    • 入队操作:
    • 出队操作:
    • 获取队首和队尾元素:
    • 内存释放
  • 难点解释
    • 难点1
    • 难点2
    • 难点3


要做题目的点击这里–>队列oj题——622.设计循环队列

题目要求:

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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 的范围内;
请不要使用内置的队列库。
在这里插入图片描述

结构体定义

首先,我们定义一个名为 MyCircularQueue 的结构体来表示循环队列:

typedef struct {int *a;     // 队列中的元素数组int k;      // 队列的最大容量int front;  // 指向队列头部元素的指针int back;   // 指向队列尾部的下一个位置的指针
} MyCircularQueue;

在这个结构体中,a 是一个整型数组,用来存储队列中的元素。k 表示队列的最大容量,front 和 back 分别表示队列头部和尾部的指针。

队列的创建

队列的创建涉及到内存的分配和初始化:

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int *)malloc(sizeof(int)*(k+1));obj->front = obj->back = 0;obj->k = k;return obj;
}

这里,我们为队列结构体和队列数组分配内存。注意,我们为数组分配 k+1 的空间,因为在循环队列中,我们总是保留一个位置不使用,以区分队列为空和队列为满的状态。

基本操作

判断队列是否为空:

// 检查队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->back; // 如果 front 和 back 相等,则队列为空
}

frontback 相等时,队列为空。

判断队列是否已满:

// 检查队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back + 1) % (obj->k + 1) == obj->front; // 如果 back 的下一个位置是 front,则队列已满
}

如果 back 的下一个位置是 front,则队列已满。

入队操作:

// 向队列中添加元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) // 如果队列已满,则无法添加元素return false;obj->a[obj->back] = value; // 在 back 的位置插入元素obj->back = (obj->back + 1) % (obj->k + 1); // 更新 back 的位置

在入队时,我们首先检查队列是否已满。如果不满,将元素放在 back 指向的位置,并更新 back 指针。

出队操作:

// 从队列中删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空,则无法删除元素return false;obj->front = (obj->front + 1) % (obj->k + 1); // 更新 front 的位置return true;
}

出队时,我们检查队列是否为空。如果不为空,则移动 front 指针。

获取队首和队尾元素:

// 获取队列头部的元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空,返回 -1return -1;return obj->a[obj->front]; // 返回队列头部的元素
}// 获取队列尾部的元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空,返回 -1return -1;return obj->a[(obj->back - 1 + obj->k + 1) % (obj->k + 1)]; // 返回队列尾部的元素
}

这两个函数用于获取队首和队尾的元素。注意在获取队尾元素时,我们使用了模运算来正确处理环形结构。

内存释放

最后,当队列不再需要时,我们应该释放其占用的内存:

// 释放队列占用的内存
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a); // 释放数组内存free(obj);    // 释放队列结构体内存
}

难点解释

难点1

在这里插入图片描述
这里我优化了代码,没有优化前是这样的:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) // 如果队列已满,则无法添加元素return false;obj->a[obj->back] = value; // 在 back 的位置插入元素obj->back++; // 更新 back 的位置obj->back %=(obj->k+1);//确保值在循环队列的有效范围内return true;
}

难点2

在这里插入图片描述

1.循环队列的容量:在这个循环队列的实现中,队列的实际容量是 k + 1,但为了区分空队列和满队列的状态,我们总是保留一个元素的空间不使用。所以,队列中最多可以存储 k 个元素。

2.队列尾部指针 (obj->back):这个指针指向队列中下一个元素将要存放的位置。当一个新元素被加入队列时,它被放置在 obj->back 指向的位置,然后 obj->back 会向前移动一个位置。

3.队列头部指针 (obj->front):这个指针指向队列中当前的第一个元素。当一个元素被移出队列时,obj->front 会向前移动一个位置。

4.判断队列是否已满:
(obj->back + 1) % (obj->k + 1) 计算出 obj->back 向前移动一个位置后的值,并使用模运算确保这个值在循环队列的有效范围内(即从 0 到 k)。


难点3

在这里插入图片描述

下面是这个表达式的详细解释:

1.obj->back: 指向队列中下一个插入元素的位置。

2.obj->back - 1: 因为 obj->back 指向的是下一个空位,所以队尾元素实际上是在 obj->back - 1 的位置。

3.由于队列是循环的,当 obj->back 为 0 时,obj->back - 1 会变成一个负数。为了正确地处理这种情况,我们加上 obj->k + 1,这保证了我们总是在一个正数的范围内操作。

4.(obj->back - 1 + obj->k + 1) % (obj->k + 1): 这个模运算确保了即使加上了 obj->k + 1,结果仍然是在队列大小的合法范围内。因此,这个表达式能够正确地处理循环队列的尾部元素访问,无论 obj->back 是在队列的开始位置还是任何其他位置

可以来我的github参观参观,看完整代码
路径点击这里–>oj622-设计循环队列

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



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

相关文章

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