数组实现循环队列(增设队列大小size)

2023-12-11 20:01

本文主要是介绍数组实现循环队列(增设队列大小size),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、前言

1.如何实现循环?

2.如何判断队列为空?

3.如何判断队列为满?

二、循环队列的结构定义

三、循环队列的创建及其初始化

四、入队

五、出队

六、取队头元素

七、取队尾元素

八、循环队列判空

九、循环队列判满

十、循环队列销毁


一、前言

利用数组实现循环队列,重点要解决的问题有三个:

1.如何实现循环?

由于数组大小k是确定的,要实现队列循环就需要让数组下标循环,利用两个下标front、back分别指向首元素和尾元素的下一个位置。front = (front+1) % k,back = (back+1) % k,即可完成下标的循环。

2.如何判断队列为空?

初始化时,front和back都为0,此时为空。因此我们确定判空条件为 front = back时循环队列为空。

3.如何判断队列为满?

我们发现,当队列满时,由于back指向队尾元素的下一个,因此队列满时,front = back ,与队列空时相矛盾。如何解决呢?

两种解决方法:

一是:循环队列结构中新增队列大小 size ,当size=0且front = back时,队列为空;当size≠0且front = back时,队列为满。

二是:新增一个空间,不存储数据,front = (front+1) % (k+1),back = (back+1) % (k+1),当 (back+1) % (k+1) = front时,队列为满。

本文仅讲解方法一,方法二详解:数组实现循环队列(新增一个空间)-CSDN博客

二、循环队列的结构定义

循环队列的结构中包含数组、头指针、尾指针、队列容量、队列大小(队列大小用于区分队列空与满的情况)

//方法一
typedef int MCQDataType;
//循环队列结构定义
typedef struct {MCQDataType *a;int front;//头指针,指向队头元素int back;//尾指针,指向队尾元素的下一个位置int size;//队列大小int k;//队列容量
} MyCircularQueue;

三、循环队列的创建及其初始化

为循环队列动态申请一个内存空间,再将头指针、尾指针、队列大小都初始化为0,队列容量为k

//方法一
//循环队列创建及其初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* mcq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));mcq->a=(MCQDataType*)malloc(sizeof(MCQDataType)*(k));mcq->front=mcq->back=mcq->size=0;mcq->k=k;return mcq;
}

四、入队

先通过size判断队列是否满,不满再将数据入队,同时尾指针要  加1模k (back = (back+1) % k) 

//方法一
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(obj->size==obj->k)//队列已满{return false;}obj->a[obj->back]=value;obj->back=(obj->back+1)%obj->k;obj->size++;return true;
}

五、出队

先通过size判断队列是否空,不空再将数据出队,同时头指针要  加1模k (front = (front+1) % k)

//方法一
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(obj->size==0)//队列为空{return false;}obj->front=(obj->front+1)%obj->k;obj->size--;return true;
}

六、取队头元素

先通过size判断队列是否为空,不空直接返回队头元素即可

//方法一
//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(obj->size==0)//队列为空{return -1;}return obj->a[obj->front];
}

七、取队尾元素

先通过size判断队尾是否为空。由于尾指针指向的是队尾元素的下一个位置,所以需要返回back-1位置的元素。由此需要判断尾指针是否指向0位置,如果指向0位置则不能back-1,否则越界,需要返回数组的最后一个位置元素,即k-1的位置;如果不指向0位置,则返回back-1位置的元素即可。

//方法一
//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(obj->size==0){return -1;}if(obj->back==0){return obj->a[obj->k-1];}else{return obj->a[obj->back-1];}
}

八、循环队列判空

通过size判空即可

//方法一
//循环队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size==0;
}

九、循环队列判满

通过size判满即可

//方法一
//循环队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size==obj->k;
}

十、循环队列销毁

动态申请的内存空间需要动态销毁

//方法一
//循环队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

这篇关于数组实现循环队列(增设队列大小size)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID:1. ​​useGeneratedKeys+keyProperty(推

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》:本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被