【数据结构与算法】设计循环队列

文章目录

  • 👑前言
  • 如何设计循环队列
  • 设计循环队列
  • 整体的代码
  • 📯写在最后

👑前言

🚩前面我们 用队列实现了一个栈 ,用栈实现了一个队列 ,相信大家随随便便轻松拿捏,而本章将带大家上点难度,我们来 设计一个循环队列
🚩对于循环队列,重点就在一个 “ 循环 ”,意思也就是该队列首尾相连形成一个环,但其本质还是不变,队列 先进先出 的性质依旧存在,只不过环的大小有限定(限定放多少数据就只能放多少数据)。
🚩那么我们如何来设计这样的一个环,使它既能够像队列一样,又可以体现循环的性质?下面就带大家探讨一波。


如何设计循环队列

  • 那么该如何设计一个循环队列呢?首先第一步当然就是选取一个存储结构来存放数据,是选顺序表的数组呢还是链表呢?

  • 我们先来看看对循环队列的介绍:循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

由以上所说,既然是队尾被连接在队首之后形成一个循环,并且之前我们讲解的队列是选用的链式储存结构,那我们第一个想到的就是选用链式的储存结构来存储数据,因为只要链表的尾节点的next指向头节点就形成了循环,这是很容易想到的。那我们就先对链式这一储存结构进行分析,看到底合不合适。

抽象图:

在这里插入图片描述

  • 既然是队列,那就需要两个指针,一个命名为front指向头,一个命名为rear指向尾。由于是循环队列,刚开始就将空间开好(固定长度),那么此时frontrear都指向同一个节点,如下:

在这里插入图片描述

  • 那么此时入队列的操作过程如下:

在这里插入图片描述

  • 可以看到,rear指向有效数据节点的下一个位置。当队列入满的时候,rear指针此时又与front指针相等了,我们再来看看出队列的过程(出队列数据可以不用抹去,访问不到):

在这里插入图片描述

  • 由上面的两个操作我们不难发现,当队列为空的时候,front指针与rear指针相等,当队列满的时候,front指针与rear指针也相等,这不免就会出现冲突问题:判空和判满将如何判断呢?

  • 这里有两种方案:

    1. 第一个是多创建一个变量来统计数据的个数,当判空和判满的时候根据这个变量就可以实现;
    2. 第二个是多开一个空间(注意不是哨兵位节点),也就是规定长度为多少,开空间的时候开长度加一个空间,如下图:

在这里插入图片描述
可以看到,方案二当循环队列为空的时候,front == rear,当循环队列为满的时候,如下图:

在这里插入图片描述
由此图不难得出,当循环队列为满时,有rear->next == front,所以,方案二对于判空和判满的区分也是挺不错的。不过,大家有没有观察到,对于链式储存结构,无论是方案一还是方案二,都不好找队尾数据,因为它处在rear指针的前一个节点,实在是要找的话,就需要遍历一遍循环队列,或者在一开始就另外再定义一个prev指针,指向rear指针的前一个节点,这些都是比较麻烦的。那么根据此问题,由于数组存储形式支持随机访问,所以下面我们再来看看数组的存储形式怎么样。


  • 对于数组的存储形式,整体上来说与链式存储形式差不太多。由于循环队列的长度是固定的,因此数组的存储形式抛弃了扩容这一弱点。

数组存储形式图:
在这里插入图片描述

  • 有了链式存储的分析判断,不难得出,上图的数组存储形式也会出现判空和判满实现的冲突问题。因此这里也需要解决方案,而数组存储形式的解决方案与链式存储形式的解决方案是相同的,无非就是多定义一个变量来统计数据的个数,或者多开一个空间。多定义一个变量来统计数据的个数固然可以实现,但这里我们选取多开一个空间的形式来进行分析。

如果是多开一个空间,那么当循环队列满时,有以下情况:

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

(注意:frontrear两个指针分别是对应数据的下标 | 设规定的长度为k)

  • 如果是2情况,判满可以判断 rear + 1 == front ? ,但还有1情况rear + 1不会等于front,并且会超出数组的下标范围,因此这里可以对rear + 1取模,也就是判断 (rear + 1) % (k + 1) == front ? 即可。有了这种判断方式,无论rear是否指向数组的最后一个位置,他都可以判断,因为:当rear不是指向数组的尾时,它加一模上一个(k + 1)完全不会受到影响,就相当于是判断 rear + 1 == front ? 一样。而rear指向数组的尾时,这样操作最终就是判断 front == 0 ? 一样。

  • 那数组的判满解决了,判空如何呢?其实判空很简单,只需要判断rear是否等于front即可。

由于是数组存储形式,因此支持下标的随机访问,所以这里获取队头和队尾元素都非常的方便。

  • 如果是获取队头元素,直接返回front指向的数据即可;如果是获取队尾元素,只需要返回rear的前一个位置的数据即可,但是,如果rear此时指向数组的开头又该怎么找队尾元素呢?

在这里插入图片描述

  • 这里我们将 rear + k 然后模上 k + 1 即可。因为,如果rear是指向数组开头,rear加上k后刚好指向数组的最后一个位置,也就是循环队列的队尾。如果rear不是指向数组开头, (rear + k) % (k + 1) 刚好是rear的前一个位置,所以,这样的取模的方式,完美的实现了取队尾的功能。

综上来看,链式储存结构与数组储存结构还是数组储存结构更胜一筹,因为在取队尾元素这一块数组储存结构碾压链式储存结构,所以,这里我们选择数组储存结构来实现循环队列。

  • 这里我们采用多开一个空间的方式来实现。

  • 确定了以数组存储结构来存储数据后,那么该如何实现数据的入队和出队呢?

首先来看看数据入队列示意图:

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

  • 对于第一张图的入队列,就是在当前rear位置插入,然后rear加加即可。但是对于第二张图,rear在最后位置的时候插入数据,此时rear加加就超过数组的长度了,因此我们每次在rear加加后需要执行一下 rear %= (k + 1) 这条语句,这样做,rear在数组的尾插入数据时,会将rear转算成0,也就是指向数组的开头位置,如果rear不在数组的尾插入数据,此时rear的位置不会受任何的影响。

然后再来看看数据出队列示意图:

在这里插入图片描述

在这里插入图片描述

  • 对于第一张图,每次删除其实只需要front加加即可,如果为空就不能删了。对于第二张图,当front指向数组的最后一个位置时,出队过后,front加加会越过数组,因此,每次出队列完成,都需要执行 front %= (k + 1) 这条语句,情况其实与上面入队列时的rear一样。

入队列与出队列介绍过了,后面就是一些队列基本的接口操作了。有取队头数据,取队尾数据,判空和判满,还有循环队列的销毁。

接下来就带大家来实现喽!


设计循环队列

  • 这里我们直接以题目的方式来实现,题目链接:-> 传送门 <-

题目描述:设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
在这里插入图片描述
在这里插入图片描述

该题提供的需要我们实现的接口:

typedef struct {

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

}

int myCircularQueueFront(MyCircularQueue* obj) {

}

int myCircularQueueRear(MyCircularQueue* obj) {

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

}

void myCircularQueueFree(MyCircularQueue* obj) {

}

接下来,就是对循环队列的一系列功能接口的实现了:

1.

  • 首先当然是定义一个循环队列的结构体。

相关代码实现:

// 循环队列的结构
typedef struct {
	// 底层存储结构为数组
    int* a;
    // 指向队头
    int front;
    // 指向队尾
    int rear;
    // 规定的循环队列的长度
    // 这里存放一下规定的循环队列的长度是为了后面取模更方便
    int k;
} MyCircularQueue;

2.

  • 然后便是对一个循环队列的创造。

  • 这里开辟一段连续的空间,可以存放规定的长度加一个数据,但其实总有一个空间是用不上的。

  • 然后将frontrear都指向循环队列的队头,就是置为0

  • 最后将规定的长度存起来即可。

相关代码实现:

// 循环队列的创造(构造器),规定创造的循环队列的长度为k
MyCircularQueue* myCircularQueueCreate(int k) {
	// 先开辟一个循环队列的空间
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    // assert防止开辟空间失败
    assert(obj);
	
	// 多开一个空间,也就是开辟(k + 1)个数据空间
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    // 开始头指针和尾指针都指向0(也就是队头)
    obj->front = obj->rear = 0;
    // 存放规定的队列长度
    obj->k = k;

    return obj;
}

3.

  • 这里是入队列的实现。
  • 入队列就是在当前的rear位置插入数据,然后rear加加。
  • 根据前面的解析,入队列之后都需要取模一次,避免rear越过数组。(当然也可以通过判断的方式来处理特殊情况)
  • 当队列为满的时候就不能入队列了。

相关代码实现:

// 入队列插入数据,插入成功返回true,不成功(队列已满)那就返回false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	// 如果此时循环队列已经满了,说明入队列不能进行,直接返回 false
    if (myCircularQueueIsFull(obj)) return false;
	
	// 在rear位置上插入数据,然后rear加加
    obj->a[obj->rear ++ ] = value;
    // 每次都模上个 (k + 1)
    obj->rear %= (obj->k + 1);

	// 入队列成功返回true
    return true;
}

4.

  • 接下来是出队列操作。
  • 出队列就是front加加,根据前面的讲解,每次出队列后都要记得需模上(k + 1)。(当然也可以通过判断的方式来处理特殊情况)
  • 当队列为空的时候就不能出队列了。

相关代码实现:

// 出队列删除数据,删除成功返回true,不成功(队列为空)那就返回false
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	// 当循环队列为空,说明不能再出队列了,表明出队列失败,直接返回false
    if (myCircularQueueIsEmpty(obj)) return false;

	// 出队列直接front加加
    obj->front ++ ;
    // 每次都模上个 (k + 1)
    obj->front %= (obj->k + 1);
	
	// 出队列成功返回true
    return true;
}

5.

  • 获取队头数据,直接返回front此时指向的那个位置上的数据即可。
  • 如果循环队列为空的话,就取不了了,依题目要求直接返回-1

相关代码实现:

// 获取队头元素,如果队列为空,返回-1
int myCircularQueueFront(MyCircularQueue* obj) {
	// 如果循环队列为空,说明没有数据,直接返回-1
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[obj->front];
}

6.

  • 获取队尾数据,根据前面的分析,采用取模的方式获取。(当然也可以通过判断的方式)
  • 如果循环队列为空的话,就取不了了,依题目要求直接返回-1

相关代码实现:

// 获取队尾元素,如果队列为空,返回-1
int myCircularQueueRear(MyCircularQueue* obj) {
	// 如果循环队列此时为空,直接返回-1
    if (myCircularQueueIsEmpty(obj)) return -1;
    
    // 以取模的方式来获取
    return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}

7.

  • 对于判空,就是判断front是否等于rear即可。

相关代码实现:

// 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

8.

  • 对于判满,根据前面的分析,也是通过取模的方式来实现的。(当然也可以通过判断的方式来处理特殊情况)

相关代码实现:

// 判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

9.

  • 最后就是销毁循环链表,malloc了几次,就free(释放)几次。

相关代码实现:

// 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {
	// 有内到外依次释放空间
	// 释放数组
    free(obj->a);
    // 释放循环队列
    free(obj);
}

整体的代码

// 循环队列的结构
typedef struct {
	// 底层存储结构为数组
    int* a;
    // 指向队头
    int front;
    // 指向队尾
    int rear;
    // 规定的循环队列的长度
    int k;
} MyCircularQueue;

// 在这声明一下判空和判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

// 循环队列的创造(构造器),规定创造的循环队列的长度为k
MyCircularQueue* myCircularQueueCreate(int k) {
	// 先开辟一个循环队列的空间
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    // assert防止开辟空间失败
    assert(obj);
	
	// 多开一个空间,也就是开辟(k + 1)个数据空间
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    // 开始头指针和尾指针都指向0(也就是队头)
    obj->front = obj->rear = 0;
    // 存放规定的队列长度
    obj->k = k;

    return obj;
}

// 入队列插入数据,插入成功返回true,不成功(队列已满)那就返回false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) return false;

    obj->a[obj->rear ++ ] = value;
    obj->rear %= (obj->k + 1);

    return true;
}

// 出队列删除数据,删除成功返回true,不成功(队列为空)那就返回false
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return false;

    obj->front ++ ;
    obj->front %= (obj->k + 1);

    return true;
}

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

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

// 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

// 判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

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

📯写在最后

💝设计一个循环队列还是有些复杂的呢,不过看过本文章,相信大家也可以轻松拿捏。
❤️‍🔥后续将会持续输出有关数据结构与算法的文章,你们的支持就是我写作的最大动力!

感谢阅读本小白的博客,错误的地方请严厉指出噢~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/2848.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】SIGCHLD信号

文章目录SIGCHLD信号SIGCHLD信号 回忆: 为了避免出现僵尸进程,父进程需要使用wait或waitpid函数等待子进程结束,父进程可以阻塞等待子进程结束,也可以非阻塞地查询的是否有子进程结束等待清理,即轮询的方式 如果采用阻塞等待:父进程阻塞就不能处理自己的工作了如果采用非阻塞等…

Python日志logging实战教程

一、什么是日志 在《网络安全之认识日志采集分析审计系统》中我们认识了日志。日志数据的核心就是日志消息或日志&#xff0c;日志消息是计算机系统、设备、软件等在某种刺激下反应生成的东西。 日志数据&#xff08;log data&#xff09;就是一条日志消息的内在含义&#xf…

第十四届蓝桥杯第三期模拟赛 【python】

第十四届蓝桥杯第三期模拟赛 【python】 文章目录第十四届蓝桥杯第三期模拟赛 【python】✨最小的十六进制&#xff08;python的16进制&#xff09;❓️问题描述答案提交&#x1f9e0;思路&#x1f5a5;︎参考答案✨Excel的列&#xff08;进制转化&#xff09;❓️问题描述答案…

串口通信(STM32演示实现)

目录 一、串行通信的概念 二、寄存器 2.1控制寄存器USART_CR1 2.2控制寄存器USART_CR2​编辑 2.3串口寄存器USART_BRR 2.4 USART_ISR 2.5USART_TDR 2.6USART_RDR​编辑 三、实现串口数据的收发 一、串行通信的概念 u通信&#xff0c;最少要有两个对象&#xff0c;一个收…

强化学习、监督学习、无监督学习是什么

1 强化学习 1.1 定义 强化学习是机器学习学习方式的一种&#xff0c;是让计算机实现从一开始完全随机的进行操作&#xff0c;通过不断试错的方式去总结出每一步的最佳行为决策&#xff0c;基于环境给予的反馈&#xff0c;去调整自己的行为决策&#xff0c;从而对未来的行为给…

什么是推挽输出,开漏输出?

这篇文章是看B站“工科男孙老师”这个视频的笔记推挽 开漏 高阻 这都是谁想出来的词&#xff1f;&#xff1f; 我觉得讲的很好&#xff0c;做一下笔记 1.什么是IO输出三态 一共有&#xff1a;高电平, 低电平&#xff0c;浮空/高阻态 三种IO态 2.推挽输出 推挽输出能够表示高、…

短链接是怎么设计的?带你入门

文章目录前言一、短链1、原理1.1 短链生成原理1.2 短链跳转原理&#xff1a;2、设计&#xff1a;2.1 短链需求2.2 考虑的问题&#xff1f;二、实践案例1、设计表&#xff1a;2、生成短链&#xff1a;前言 说到 URL 你肯定不陌生&#xff0c;浏览器输入一段 URL&#xff0c;立马…

QMessageBox手动添加按钮并绑定按钮的信号

视频展示效果&#xff08;结合代码看效果更佳哦&#xff0c;代码在最下面&#xff09;&#xff1a; QMessageBox手动添加有重试效果的按钮效果图&#xff1a; 点击详细文本之后展开如下图&#xff1a; 图标可选&#xff1a; QMessageBox::Critical错误图标QMessageBox::NoIco…

第二十一天 数据库开发-MySQL

目录 数据库开发-MySQL 前言 1. MySQL概述 1.1 安装 1.2 数据模型 1.3 SQL介绍 1.4 项目开发流程 2. 数据库设计-DDL 2.1 数据库操作 2.2 图形化工具 2.3 表操作 3. 数据库操作-DML 3.1 增加(insert) 3.2 修改(update) 3.3 删除(delete) 数据库开发-MySQL 前言 …

深度学习:GPT1、GPT2、GPT-3

深度学习&#xff1a;GPT1、GPT2、GPT3的原理与模型代码解读GPT-1IntroductionFramework自监督学习微调ExperimentGPT-2IntroductionApproachConclusionGPT-3GPT-1 Introduction GPT-1&#xff08;Generative Pre-training Transformer-1&#xff09;是由OpenAI于2018年发布的…

从0到1深度学习环境搭建

目录第一步&#xff1a;安装anaconda第二步&#xff1a;创建一个虚拟环境试一下第三步&#xff1a;确定cuda算力&#xff0c;配置cudapytorch官网找版本pycharm配置pycharm进行设置setting 能够打开conda的shell终端如何给下载的项目设置合适的环境如果必须要低版本的pytorch才…

智驾芯片“性价比之王”凭何抢滩增量市场?

未来几年&#xff0c;智能驾驶功能将进入跨越式升级的阶段&#xff0c;同时L2将快速普及&#xff0c;L2进入集中放量的阶段。 包括自动泊车 (APA)、家庭区域记忆泊车 (HAVP)、交通拥堵辅助 (TJA)、高速辅助驾驶 (HWA)、自动辅助导航驾驶 (NOA) 等在内的功能已为普通车主耳熟能…

美颜sdk的动态面具、3D面具实现流程

在美颜sdk的实现中&#xff0c;面具是很重要的一个部分&#xff0c;不管是动态面具还是3D面具都需要实现的&#xff0c;我们在开发中常用的是动态面具和3D面具。但是两种面具有很多不同之处&#xff0c;比如制作材料、制作方式等等。在这里我们先来了解一下动态面具和3D面具是如…

8个不能错过的程序员必备网站,惊艳到我了!!!

程序员是一个需要不断学习的职业&#xff0c;不少朋友每天来逛CSDN、掘金等网站&#xff0c;但一直都抱着“收藏从未停止&#xff0c;学习从未开始”的态度&#xff0c;别骗自己了兄弟。在编程体系中&#xff0c;有很多不错的小工具&#xff0c;可以极大得提升我们的开发效率。…

电容在微分、积分电路中的本质以及应用

很多朋友觉得PID是遥不可及&#xff0c;很神秘&#xff0c;很高大上的一种控制&#xff0c;对其控制原理也很模糊&#xff0c;只知晓概念性的层面&#xff0c;知其然不知其所以然&#xff0c;那么本期从另类视角来探究微分、积分电路的本质&#xff0c;意在帮助理解PID的控制原…

第十四届蓝桥杯三月真题刷题训练——第 21 天

目录 第 1 题&#xff1a;灭鼠先锋 问题描述 运行限制 代码&#xff1a; 思路&#xff1a; 第 2 题&#xff1a;小蓝与钥匙 问题描述 答案提交 运行限制 代码&#xff1a; 思路 : 第 3 题&#xff1a;李白打酒加强版 第 4 题&#xff1a;机房 第 1 题&#xff1…

存储专题扩容,HA、LB分布式存储

一、架构与存储的关系一个新的硬盘在linux系统里使用一般来说就三步:(分区,格式化)-挂载-使用blocklvs:四层负载均衡&#xff0c;nginx、haproxy四层和七层都有redis、memcache缓存中间件是缓存后端数据库读的信息。高端的容器技术&#xff0c;一旦系统出现可以可以直接重装系统…

【springboot】读写分离:

文章目录一、mysql主从复制&#xff08;从库可以有多个&#xff09;&#xff1a;【1】提前准备好两台服务器&#xff0c;分别安装Mysql并启动成功【2】配置---主库Master【3】配置---从库Slave【4】克隆的虚拟机导致mysql主从UUID一致怎么修改&#xff1a;【5】测试二、读写分离…

springboot学生综合测评系统

031-springboot学生综合测评系统演示录像2022开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&…

uniapp封装各个时间方法

难点&#xff1a;在项目中我们经常会用到时间转换或时间比对加减问题为了方便很多页面去调用时间方法&#xff0c;我把时间方法封装成了公共方法1.首先在根目录创建文件夹与pages平级&#xff0c;我这里创建了plugins文件夹2.其次在plugins文件夹下面创建index.js文件&#xff…