Leetcode:622. 设计循环队列 题解【具详细】

2023-12-01 02:01

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

目录

一、题目:

二、思路详解:

1.循环队列的存储定义

2.循环队列的创建

3.循环队列的判空与判断情况

(1) 循环队列的判空:

 (2) 循环队列的判满

4.循环队列元素的插入

5.循环队列元素的删除

6.获取队头元素

7.获取队尾元素 

8.循环队列释放

三、完整代码展示:


一、题目:

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

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

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

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

难度:中等

题目链接:622. 设计循环队列

示例:

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

题目解析:就是根据题中给的接口进行函数的实现。要求我们实现一个循环队列。

用心阅读下方会有很大的收获。 

二、思路详解:

1.循环队列的存储定义

首先我们需要定义出一个循环队列的存储定义,这里采用的是使用动态数组来进行模拟循环队列,根据题中给出的接口返回类型,我们可以知道循环队列的数据类型为int 。

其次,还需定义两个记录数组的下标,一个记录队列的队头,另一个记录队列的队尾(也就是指向要入队的下一个元素的位置)。另外还要提供一个表示要存储数据的具体个数。

如图:

代码:

//采用动态数组的形式来模拟循环队列
typedef struct {int* a;     //指向数组int front;  //队头int tail;   //队尾int k;      //数据个数
} MyCircularQueue;

2.循环队列的创建

循环队列的创建,先使用malloc进行创建一个 循环队列空间

接着根据给的数据个数k让指针a指向一个动态数组,在分别对front,tail,k进行初始化,注意tail = 0表示要存放的下一个数据元素的位置,对动态数组a开辟空间的时候要多开辟一个空间,避免假溢出的现象。最后一定要返回之前创建的循环队列。

代码:

//创建长度为k的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {//使用动态内存函数来申请内存//这里多申请一个空间的目的是防止假溢出//使用malloc创建一个循环队列MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//为循环队列里面的指针a ,让a指向一个长度为k+1的数组obj->a= (int*)malloc(sizeof(int)*(k+1));obj->front = 0; //队头从数组的下标0开始obj->tail = 0; //队尾指向下一个元素obj->k = k; //队列的长度为kreturn obj;
}

物理存储情况,如图:

但是我们一般会到其循环的逻辑结构,逻辑存储,如图:

 3.循环队列的判空与判断情况

循环队列的插入和删除是不可避免的,当这之前就需要先完成判和判满的接口。注意:一定要把判空和判满的函数实现放在队列插入和删除函数实现的前面。

(1) 循环队列的判空:

根据函数的返回类型是bool,空我们就返回true ,否则返回false。

  • isEmpty(): 检查循环队列是否为空。

因为这里采取的是通过动态数组来模拟循环队列,所以队列空的条件就是当front == tail 的时候,此时的循环队列就是空的。

如图:

代码:

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//队空,就是队头与队尾相同时return obj->front == obj->tail;
}
 (2) 循环队列的判满

 同样根据函数的返回类型是bool,空我们就返回true ,否则返回false。

  • isFull(): 检查循环队列是否已满。

什么时候会满呢?当(tail+1)%(k+1) == front,就是队尾下标加1模开辟空间的个数 

可能很多会对为什么要多开辟一个空间,原因就在这:对于队列的判满的情况,

当没有创建的额外空间,队列只有数据10 和 11 的情况下,

像上图就是假溢出现象,这个队列并没有满。

总的来说:

循环队列为了区分队列的空和满,需要额外增加一个空的元素来占据队列的一个位置,这样队列满的状态就可以通过头尾指针相邻且不重合来判断,而不会出现头尾指针重合但队列实际上并不满的情况。同时循环队列需要对头尾指针进行模运算,如果没有额外的空间,那么当队列最后一个元素占据了数组最后一个位置时,下一个元素就会从数组的第一个位置开始,这样就无法正确进行模运算,而增加一个空的元素可以解决这个问题。

 代码:

bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->k+1) == obj->front;
}

 4.循环队列元素的插入

  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

插入前判断是否满,满就返回false,接着就是数据的插入,插入后,对tail下标进行取模(因为是反复利用原来的空间,还有就是避免溢出),插入成功就返回true。

 代码:

//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素前先进行判断是否满if(myCircularQueueIsFull(obj)){return false;}//插入元素使用尾插obj->a[obj->tail] = value;obj->tail++;//避免tail的下标越界obj->tail%=(obj->k+1);return true;
}

5.循环队列元素的删除

 删除前,要进行判断是否为空。队头减一,进行删除,删除后取模。

  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

 代码:

//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除元素队列不能为空if(myCircularQueueIsEmpty(obj)){return false;}//出队,头删obj->front++;obj->front%=(obj->k+1);return true;
}

 6.获取队头元素

获取前进行判断,是否为空。

Front: 从队首获取元素。如果队列为空,返回 -1  

  代码:

//获取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}return obj->a[obj->front];
}

7.获取队尾元素 

获取前进行判断,是否为空。

Rear: 获取队尾元素。如果队列为空,返回 -1  

  代码:

//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}//注意当tail = 0的情况return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
}

解释一下 上述最后一行代码:

重点:

首先tail是指向要存放下一个元素的位置,找队尾元素时,tail要进行-1。

 因为数组下标最小是从0开始的,当tail ==0且队列不为空的情况下,上方代码obj->tail-1,就会造成0-1 == -1的情况。上方采用(obj->tail - 1+ obj->k+1)%(obj->k+1)就可以完美的避免,当然

其实可以写成

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;// return obj->a[(obj->tail-1 + obj->k+1)%(obj->k+1)];if(obj->tail == 0){return obj->a[obj->k];}else{return obj->a[obj->tail-1];}
}

8.循环队列释放

 因为用malloc开辟的动态内存空间,为了避免内存泄漏,我们还要释放内存。注意释放的顺序。

 代码:

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

三、完整代码展示:

 代码: 


//采用动态数组的形式来模拟循环队列
typedef struct {int* a;     //指向数组int front;  //队头int tail;   //队尾int k;      //数据个数
} MyCircularQueue;//创建长度为k的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {//使用动态内存函数来申请内存//这里多申请一个空间的目的是防止假溢出//使用malloc创建一个循环队列MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//为循环队列里面的指针a ,让a指向一个长度为k+1的数组obj->a= (int*)malloc(sizeof(int)*(k+1));obj->front = 0; //队头从数组的下标0开始obj->tail = 0; //队尾指向下一个元素obj->k = k; //队列的长度为kreturn obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//队空,就是队头与队尾相同时return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->k+1) == obj->front;
}//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素前先进行判断是否满if(myCircularQueueIsFull(obj)){return false;}//插入元素使用尾插obj->a[obj->tail] = value;obj->tail++;//避免tail的下标越界obj->tail%=(obj->k+1);return true;
}//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除元素队列不能为空if(myCircularQueueIsEmpty(obj)){return false;}//出队,头删obj->front++;obj->front%=(obj->k+1);return true;
}//获取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}return obj->a[obj->front];
}//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}//注意当tail = 0的情况return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

这篇关于Leetcode:622. 设计循环队列 题解【具详细】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

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 结

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

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

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