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

news/2025/3/19 8:28:47/

目录

一、前言

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);
}

http://www.ppmy.cn/news/1261652.html

相关文章

玩转系统|利用HestiaCP自建NS解析及邮局并利用MailGun进行发信

前述 HestiaCP是一个VestaCP分叉来的产物,而同样作为VestaCP分叉来的myVesta也具有类似的功能。VestaCP本身作为一个社区的产区,其仅仅有一个商业插件需要每月付费5USD进行使用,因此为了达到完全开放使用的目的,这里选择使用Hest…

2024年值得关注的8个未来数据库

2024年值得关注的8个未来数据库 关系型数据库管理系统在数据库技术领域占据主导地位已经多年了。当SQL在1970年代首次出现时,关系型数据库管理系统的使用和受欢迎程度迅速提升。很快,MySQL成为了大多数公司和团队首选的数据库。 然而,2023年…

代码混淆技术探究与工具选择

代码混淆技术探究与工具选择 引言 在软件开发中,保护程序代码的安全性是至关重要的一环。代码混淆(Obfuscated code)作为一种常见的保护手段,通过将代码转换成难以理解的形式来提升应用被逆向破解的难度。本文将介绍代码混淆的概…

Perfectly Clear Workbench Mac/Win中文版——提升照片处理效率的必备工具

Perfectly Clear Workbench是一款功能强大的照片处理工具,现已推出Mac和Win中文版。无论您是摄影爱好者、专业摄影师,还是社交媒体达人,这款软件都能帮助您提升照片处理效率,使您的作品更加出色。 Perfectly Clear Workbench的主…

220V降12V鱼缸加热棒电源芯片WT5106

220V降12V鱼缸加热棒电源芯片WT5106 WT5106,一款高效率高精度的非隔离降压开关电源恒压控制驱动芯片,赋予你的设备超能电力!它适用于85VAC到265VAC全范围输入电压的非隔离Buck、Buckboost拓扑结构,为你的小家电、电机驱动、继电器…

帮企10合一万能分销商城源码系统 源码开源可二次开发 附带完整的搭建教程

电子商务的普及,越来越多的企业开始涉足网络销售领域。然而,自行开发一套电商平台需要投入大量的时间和资金,对于很多初创企业或缺乏技术能力的企业来说是一个巨大的挑战。此外,由于电子商务领域的竞争激烈,如何降低运…

力扣题:字符的统计-12.6

力扣题-12.6 [力扣刷题攻略] Re:从零开始的力扣刷题生活 力扣题1:696. 计数二进制子串 解题思想:先统计连续的0和连续的1的个数,然后进行相加即可(想不到一点) class Solution(object):def countBinaryS…

使用BigDL-LLM优化大语言模型

BigDL-LLM是一个用于在英特尔XPU上使用INT4/FP4/INT8/FP8运行LLM(大型语言模型)的库,具有非常低的延迟(适用于任何PyTorch模型)。 在英特尔CPU上安装BigDL-LLM 安装 pip install --pre --upgrade bigdl-llm[all] 运…