【数据结构】循环队列（数组实现）

目录

一、循环队列定义

怎么使一个数组在逻辑上呈“环状”呢？

 二、循环队列与顺序队列的差异

1、存储方式:

2、操作方式:

3、空间利用率：

4、循环队列判断队空的方式：

5、循环队列判断队满的方式

完整测试代码及注释： 

总结：

一、循环队列定义

将顺序存储队列的元素的一维数组首尾相接，形成一个环状，如下图所示，这种形式表示的队列称为循环队列。循环队列仍然是顺序队列结构，只是逻辑上和前面的顺序队列有所不同。

#define MAXLEN 6           // 定义环形队列的最大长度为 6

typedef int DataType;     // 定义数据类型为整型

typedef struct CircularQueue  // 定义环形队列的结构体
{
    DataType a[MAXLEN];   // 定义存储数据的数组
    int front, rear;      // 定义队头和队尾指针
    int size;             // 定义队列元素个数
} CQueue;

void InitCQueue(CQueue* q)  // 初始化环形队列
{
    q->front = q->rear = 0; // 队头和队尾指针都指向队列的开始位置
    q->size = 0;            // 队列元素个数为 0，即初始为空队列
}

怎么使一个数组在逻辑上呈“环状”呢？

在数据结构中，可以使用一个 front 指针和一个 rear 指针来表示环状队列的队头和队尾位置，当 rear 指针移动到数组的最后一个位置时，如果再有元素需要入队，那么应该将 rear 指针指向数组的第一个位置。同样地，当 front 指针移动到数组的最后一个位置时，如果还有元素需要出队，那么应该将 front 指针指向数组的第一个位置。

具体实现方法如下：

  1. 初始化：定义一个数组和两个指针 front 和 rear，初始化时，将 front 指针和 rear 指针都指向数组的第一个位置。

  2. 入队：如果队列未满，则将元素插入 rear 指向的位置，然后将 rear 指针后移一位。当 rear 指针移动到数组的最后一个位置时，若队列未满，则将 rear 指针指向数组的第一个位置。

  3. 出队：如果队列非空，则将队头元素取出，然后将 front 指针后移一位。当 front 指针移动到数组的最后一个位置时，只要队列非空，就将 front 指针指向数组的第一个位置。

假设队列开辟的数组单元数为MAXSIZE，它的数组下标在0~MAXSIZE-1之间，若使队头或队尾增1，且使front和rear指针对应的数组下标保持在数组范围内，可以利用取模运算实现。

例如，在下图所示的循环队列示意图最大空间为MAXSIZE=8，数组下标为0~7之间。

非空队时如图（2）中队头指针front指向队列中队头元素的前一个位置，队尾指针rear 指向队列的队尾元素位置。

  •         入队时的队尾指针加1操作修改为： rear=(rear+1)%MAXSIZE;
  •         出队时的队头指针加1操作修改为：front=(front+1)%MAXSIZE；

入队代码实现： 

void CQueuePush(CQueue* q, DataType x)   // 元素入队
{
    assert(q);  // 判断 q 是否为空
    if (!CQueueFull(q))  // 如果队列未满
    {
        q->rear = (q->rear + 1) % MAXLEN;   // 队尾指针后移一位
        q->a[q->rear] = x;  // 在队尾处添加元素
        q->size++;  // 队列元素个数加 1
    }
    else    // 队列已满，无法添加数据
    {
        printf("队列已满，无法添加数据！\n");
        exit(-1);
    }
}

 出队代码实现： 

void CQueuePop(CQueue* q)   // 元素出队
{
    assert(q);  // 判断 q 是否为空
    if (!CQueueEmpty(q))    // 如果队列非空
    {
        q->front = (q->front + 1) % MAXLEN; // 队头指针后移一位
        q->size--;  // 队列元素个数减 1
    }
    else    // 队列已空，无法删除数据
    {
        printf("队列已空，无法删除数据！\n");
        exit(-1);
    }
}

 二、循环队列与顺序队列的差异

  • 1、存储方式:

    • 顺序队列：使用数组作为底层数据结构，按照顺序存储元素。
    • 循环队列：仍然使用数组作为底层数据结构，但是通过循环利用数组的空间，实现循环存储。

  • 2、操作方式:

    • 顺序队列：使用两个指针front和rear分别表示队头和队尾，元素入队时rear指针后移，元素出队时front指针后移。
    • 循环队列：同样使用两个指针front和rear表示队头和队尾，但是在数据满或空的状态下，指针继续向后移动的时候保持循环关系。
      • 入队时队尾指针+1：rear=(rear+1)%MAXSIZE;
      • 出队时队头指针+1：front=(front+1)%MAXSIZE;

  • 3、空间利用率：

    • 顺序队列：存储元素的空间是连续的，当队列未满但是数组的末尾已经被利用时，无法继续插入元素。
    • 循环队列：通过循环利用数组空间，解决了顺序队列存储空间的浪费问题，可以实现更高的空间利用率。

4、循环队列判断队空的方式：

图（1）中队头与队尾指针指向同一位置时为空队，判断方法与顺序队列一致。

 代码实现：

int CQueueEmpty(CQueue* q)  // 判断队列是否为空
{
    assert(q);  // 判断 q 是否为空
    if (q->front == q->rear)  // 通过队头和队尾指针是否相等，判断队列是否为空
    {
        return 1;   // 队列为空
    }
    return 0;       // 队列非空
}

5、循环队列判断队满的方式

由 图(3) 可见，循环队列解决了顺序队列中“假溢出”的现象，充分利用了固定长度的队列中的空间。我们知道，在长度不可增长的顺序队列中，判断队列是否队满的条件是rear==MAXLEN。那么在循环队列中，我们判断队满的方式则为：(rear+1)%MAXLEN==front;  


 

代码实现：

int CQueueFull(CQueue* q)   // 判断队列是否为满
{
    assert(q);  // 判断 q 是否为空
    if ((q->rear + 1) % MAXLEN == q->front)  // 通过队尾和队头指针是否相邻，判断队列是否为满
    {
        return 1;   // 队列为满
    }
    return 0;       // 队列未满
}

我们理解完顺序队列与循环队列的差异后，在固定长度代码的基础上对front、rear指针的移动和判满操作进行修改即可得到循环队列的代码。

完整测试代码及注释： 

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


#define MAXLEN 6           // 定义环形队列的最大长度为 6

typedef int DataType;     // 定义数据类型为整型

typedef struct CircularQueue  // 定义环形队列的结构体
{
    DataType a[MAXLEN];   // 定义存储数据的数组
    int front, rear;      // 定义队头和队尾指针
    int size;             // 定义队列元素个数
} CQueue;

void InitCQueue(CQueue* q)  // 初始化环形队列
{
    q->front = q->rear = 0; // 队头和队尾指针都指向队列的开始位置
    q->size = 0;            // 队列元素个数为 0，即初始为空队列
}

int CQueueFull(CQueue* q)   // 判断队列是否为满
{
    assert(q);  // 判断 q 是否为空
    if ((q->rear + 1) % MAXLEN == q->front)  // 通过队尾和队头指针是否相邻，判断队列是否为满
    {
        return 1;   // 队列为满
    }
    return 0;       // 队列未满
}

int CQueueEmpty(CQueue* q)  // 判断队列是否为空
{
    assert(q);  // 判断 q 是否为空
    if (q->front == q->rear)  // 通过队头和队尾指针是否相等，判断队列是否为空
    {
        return 1;   // 队列为空
    }
    return 0;       // 队列非空
}

void CQueuePush(CQueue* q, DataType x)   // 元素入队
{
    assert(q);  // 判断 q 是否为空
    if (!CQueueFull(q))  // 如果队列未满
    {
        q->rear = (q->rear + 1) % MAXLEN;   // 队尾指针后移一位
        q->a[q->rear] = x;  // 在队尾处添加元素
        q->size++;  // 队列元素个数加 1
    }
    else    // 队列已满，无法添加数据
    {
        printf("队列已满，无法添加数据！\n");
        exit(-1);
    }
}

void CQueuePop(CQueue* q)   // 元素出队
{
    assert(q);  // 判断 q 是否为空
    if (!CQueueEmpty(q))    // 如果队列非空
    {
        q->front = (q->front + 1) % MAXLEN; // 队头指针后移一位
        q->size--;  // 队列元素个数减 1
    }
    else    // 队列已空，无法删除数据
    {
        printf("队列已空，无法删除数据！\n");
        exit(-1);
    }
}

int CQueueTop(CQueue* q)   // 获取队首元素
{
    if (!CQueueEmpty(q))    // 如果队列非空
    {
        return q->a[q->front + 1];  // 返回队头下一个位置的元素
    }
    else    // 队列已空，无法获取队首数据
    {
        printf("队列已空，无法获取队首数据！\n");
        exit(-1);
    }
}

int CQueueTail(CQueue* q)   // 获取队尾元素
{
    if (!CQueueEmpty(q))    // 如果队列非空
    {
        return q->a[q->rear];   // 返回队尾位置的元素
    }
    else    // 队列已空，无法获取队尾数据
    {
        printf("队列已空，无法获取队尾数据！\n");
        exit(-1);
    }
}


int main()
{
	CQueue q;
	InitCQueue(&q);
	CQueuePush(&q, 1);
	CQueuePush(&q, 2);
	CQueuePush(&q, 3);
	CQueuePush(&q, 4);
	CQueuePush(&q, 5);
	CQueuePop(&q);
	CQueuePop(&q);
	CQueuePop(&q);
	CQueuePop(&q);
	//CQueuePop(&q);
	int x;
	x = CQueueTop(&q);
	printf("%d\n", x);
	x = CQueueTail(&q);
	printf("%d\n", x);
    return 0;
}

总结：

循环队列通过环形数组的设计，充分利用了存储空间，并实现了高效的元素入队和出队操作。在使用循环队列时，需要特别注意队列为空和队列满的判断，避免出现错误。

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

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

相关文章

Vue 中的 ref 与 reactive：让你的应用更具响应性（上）

Vue 中的 ref 与 reactive：让你的应用更具响应性（上）

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
用HTML的原生语法实现两个div子元素在同一行中排列

用HTML的原生语法实现两个div子元素在同一行中排列

代码如下&#xff1a; <div id"level1" style"display: flex;"><div id"level2-1" style"display: inline-block; padding: 10px; border: 1px solid #ccc; margin: 5px;">这是第一个元素。</div><div id"…
阅读更多...
计算机系统基础

计算机系统基础

C 语言相关内容省略&#xff0c;复习自用&#xff0c;仅供参考~ 概述 冯诺伊曼结构 存储程序工作方式&#xff1a;将事先编好的程序和原始数据送入主存后才能执行程序&#xff0c;程序被启动执行后&#xff0c;计算机能在不需要操作人员干预下自动完成逐条指令取出和执行的任…
阅读更多...
解析为什么Go语言要使用[]rune而不是string来表示中文字符

解析为什么Go语言要使用[]rune而不是string来表示中文字符

众所周知&#xff0c;Go语言中有以下这些数据类型。但rune32这个go语言特有的数据类型&#xff0c;比较有意思却经常遭到忽视。所以今天探索学习一下这个数据类型的功能、用法。 Go基本数据类型 布尔&#xff1a;bool 字符串&#xff1a;string 整数&#xff1a; int int8 …
阅读更多...
NNDL 作业13 优化算法3D可视化 [HBU]

NNDL 作业13 优化算法3D可视化 [HBU]

老师作业原博客:【23-24 秋学期】NNDL 作业13 优化算法3D可视化-CSDN博客 NNDL 作业13 优化算法3D可视化-CSDN博客 编程实现优化算法&#xff0c;并3D可视化 1. 函数3D可视化 分别画出 和 的3D图 NNDL实验 优化算法3D轨迹 鱼书例题3D版_优化算法3d展示-CSDN博客 代码&#…
阅读更多...
JSON网络令牌JWT

JSON网络令牌JWT

1.什么是身份验证 日常生活中的身份验证的场景: 比如进入公司的大楼时&#xff0c;需要携带工牌&#xff1b;打卡上班时&#xff0c;需要指纹识别&#xff1b;打开工作电脑时&#xff0c;需要输入密码。 2. 什么是 JSON 网络令牌&#xff1f; JSON Web Token (JWT) 是一个开…
阅读更多...
智能编程助手！华为云CodeArts Snap免费公测：基于盘古研发大模型

智能编程助手！华为云CodeArts Snap免费公测：基于盘古研发大模型

近日&#xff0c;华为云CodeArts Snap正式开启公测。 这是一款基于华为云研发大模型的智能化编程助手&#xff0c;旨在为开发者提供高效且智能的编程体验&#xff0c;提升研发人员的单兵作战能力。 该服务公测期间免费&#xff0c;不向用户收取任何费用&#xff0c;商用后&am…
阅读更多...
【论文阅读|冷冻电镜】DISCA: High-throughput cryo-ET structural pattern mining

【论文阅读|冷冻电镜】DISCA: High-throughput cryo-ET structural pattern mining

论文题目 High-throughput cryo-ET structural pattern mining by unsupervised deep iterative subtomogram clustering 摘要 现有的结构排序算法的吞吐量低&#xff0c;或者由于依赖于可用模板和手动标签而固有地受到限制。本文提出了一种高吞吐量的、无需模板和标签的深度…
阅读更多...
【C++入门到精通】function包装器 | bind() 函数 C++11 [ C++入门 ]

【C++入门到精通】function包装器 | bind() 函数 C++11 [ C++入门 ]

阅读导航 引言一、function包装器1. 概念2. 基本使用3. 逆波兰表达式求值&#xff08;1&#xff09;普通写法&#xff08;2&#xff09;使用包装器以后的写法 二、bind() 函数温馨提示 引言 很高兴再次与大家分享关于 C11 的一些知识。在上一篇文章中&#xff0c;我们讲解了 c…
阅读更多...
Vue前端文字效果：如何让一段文本像是手动一个一个字打出来的

Vue前端文字效果：如何让一段文本像是手动一个一个字打出来的

效果展示 自己做的AI聊天机器人界面&#xff0c;我觉得比微信还好看 由于这个前端略微复杂&#xff0c;下文用最简单的例子来展示&#xff1a; 分析需求 对于AI聊天工具的前端&#xff0c;如果AI生成的文本像是一个一个字打出来的&#xff0c;就会让AI看起来更像真的人&…
阅读更多...
打造炫酷粒子效果的前端利器tsParticles

打造炫酷粒子效果的前端利器tsParticles

前端潮流速递 &#xff1a;打造炫酷粒子效果的前端利器tsParticles 在现代前端开发中&#xff0c;动画和视觉效果是吸引用户的关键元素之一。而实现炫酷而引人入胜的粒子效果&#xff0c;常常需要耗费大量的时间和精力。然而&#xff0c;有了 tsParticles&#xff0c;这一切变…
阅读更多...
MySQL 8.0 开关 Redo Logging

MySQL 8.0 开关 Redo Logging

一 前言 前几天有客户测试使用云数据库的时候提出 要禁止mydumper 关闭redo log的操作 (说白了就是导入数据时保持MySQL 实例的redo logging功能)&#xff0c; 这才想起 在 MySQL 8.0.21 版本中&#xff0c;开启了一个新特性 “Redo Logging 动态开关”。 在新实例导数据的场…
阅读更多...
搭建宠物寄养小程序流程

搭建宠物寄养小程序流程

近日&#xff0c;一地宠物寄养需求旺盛&#xff0c;元旦满房&#xff0c;春节几近饱和&#xff0c;一窝难求。随着市场需求的增长&#xff0c;对于很多宠物行业的商家&#xff0c;可以考虑开展宠物寄养服务&#xff0c;尤其是节假日的宠物寄养需求会更高。因此&#xff0c;商家…
阅读更多...
FastApi-快速入门1

FastApi-快速入门1

FastAPI 是一个用于构建 API 的现代、快速&#xff08;高性能&#xff09;的 web 框架&#xff0c;使用 Python 3.8 并基于标准的 Python 类型提示。 关键特性: 快速&#xff1a;可与 NodeJS 和 Go 并肩的极高性能&#xff08;归功于 Starlette 和 Pydantic&#xff09;。最快…
阅读更多...
算法通关村番外篇-数组实现队列

算法通关村番外篇-数组实现队列

大家好我是苏麟 , 今天来用数组实现一下队列 . 数组实现队列 顺序存储结构存储的队列称为顺序队列&#xff0c;内部使用一个一维数组存储&#xff0c;用一个队头指针 front 指向队列头部节点(即使用int类型front来表示队头元素的下标)&#xff0c;用一个队尾指针rear(有的地方…
阅读更多...
3dmax灯光缓存参数应该怎么设置？

3dmax灯光缓存参数应该怎么设置？

细分&#xff1a;用来决定灯光缓存的样本数量&#xff0c;样本数量以此数值的平方来计算。数值越高&#xff0c;效果越好&#xff0c;速度越慢。 一般出图建议1000到1800之间已经足够了 采样大小&#xff1a;用来控制灯光缓存的样本尺寸大小&#xff0c;较小的数值意味着较小的…
阅读更多...
Vue 模板编译原理解析

Vue 模板编译原理解析

Vue 模板编译原理解析 模板编译整体流程 首先我们看一下什么是编译&#xff1f; 所谓编译&#xff08;Compile&#xff09;&#xff0c;指的是将语言 A 翻译成语言 B&#xff0c;语言 A 就被称之为源码&#xff08;source code&#xff09;&#xff0c;语言 B 就被称之为目标…
阅读更多...
清风数学建模笔记-主成分分析

清风数学建模笔记-主成分分析

内容&#xff1a;主成分分析 介绍&#xff1a; 主成分分析是一种降维算法&#xff0c;它通过旋转和变换将多个指标转化为少数几个主成分&#xff0c;这些主成分是原变量的线性组合&#xff0c;且互不相关&#xff0c;其能反映出原始数据的大部分信息。 例如解决多重共线性问题…
阅读更多...
Vue+ElementUI笔记(1)

Vue+ElementUI笔记(1)

一、表格 1.上移、下移和移除功能 需求&#xff1a;有时我们会面对类似这样的表格 图中的上移&#xff0c;下移功能需求明显要求我们改变两行数据的顺序。在实际开发中这种功能一般由后台来做&#xff0c;因为列表数据一般从后台获取刷新。即是我们点击”上移“&#xff0c;向…
阅读更多...
K8Spod组件

K8Spod组件

一个pod能包含几个容器 一个pause容器(基础容器/父容器/根容器&#xff09; 一个或者多个应用容器(业务容器) 通常一个Pod最好只包含一个应用容器&#xff0c;一个应用容器最好也只运行一个业务进程。 同一个Pod里的容器都是运行在同一个node节点上的&#xff0c;并且共享 net、…
阅读更多...
最新文章

Copyright @ 2022~2023