当前位置: 首页 > news >正文

【数据结构】设计环形队列

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

思路:
在环形队列中,队列为空时,队头队尾指向同一个位置。当队列不为空时,队头指向插入的第一个数据,队尾指向最后一个数据的下一个位置。当tail+1等于front时,说明环形队列已满。

注意:
环形队列的队尾不能像常规队列中队尾一样指向最后一个数据,如果这样的话,我们将不能区别环形队列的状态是空还是满,因为此时队头和队尾都指向同一个位置。这就意味着,我们必须留出一个空间,这个空间不能存放数据,这样我们才能很好的区别环形队列的状态是空还是满。

在这里插入图片描述

我们如果用一个数组来实现这个环形队列的话,上面这三种状态就对应于以下三种状态:

在这里插入图片描述

可以看出,此时这个数组和环形完全扯不上关系,这其实很简单,我们只需注意判断两个地方:
 1.当指针指向整个数组的后方的时候,让该指针重新指向数组的第一个元素。
 2.当指针指向整个数组的前方的时候,让该指针直接指向数组最后一个有效元素的后面。

这样就使得该数组在逻辑上是“环形”的了。
在这里插入图片描述

代码:

// 设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
#include <stdbool.h>
#include <stdlib.h>
// 循环队列的结构:使用数组来存储,队头,队尾的下标,一个存储数据的数组。K表示队列长度
typedef struct
{int *queue;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue *myCircularQueueCreate(int k) {// 数组大小要开辟k+1 预留一个空的空间,以方便判断空和满的两种情况MyCircularQueue *obj = (MyCircularQueue *) malloc(sizeof(MyCircularQueue));obj->queue = (int *) malloc(sizeof(int) * (k + 1));obj->front = 0;obj->rear = 0;obj->k = k;return obj;
}// 队列判空front == rear
bool myCircularQueueIsEmpty(MyCircularQueue *obj) {assert(obj);// 判空的条件是front和rear都为0return obj->front == obj->rear;
}// 队列判满 (rear+1)%(k+1)=front
bool myCircularQueueIsFull(MyCircularQueue *obj) {assert(obj);// 判满的条件是队列满了,rear指向了最后一个空的数组,+1需要回到front的位置,也就是(rear+1)%(k+1)==frontreturn ((obj->rear + 1) % (obj->k + 1)) == obj->front;
}//求有效长度(rear-front+k+1)%(k+1)
int myCircularQueueLength(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return 0;return (obj->rear - obj->front + obj->k + 1) % (obj->k + 1);
}bool myCircularQueueEnQueue(MyCircularQueue *obj, int value) {assert(obj);// 进队列  如果队列满了,就无法进队列,返回falseif (myCircularQueueIsFull(obj))return false;obj->queue[obj->rear++] = value;// rear的值溢出,需要重新设置obj->rear %= (obj->k + 1);/* 也可以这么写if (obj->rear > obj->k)obj->rear = 0;*/return true;
}bool myCircularQueueDeQueue(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return false;obj->front++;// front溢出重新设置obj->front %= (obj->k + 1);/* 也可以这么写if (obj->front > obj->k)obj->front = 0;*/return true;
}int myCircularQueueFront(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj->queue[obj->front];
}int myCircularQueueRear(MyCircularQueue *obj) {assert(obj);if (myCircularQueueIsEmpty(obj))return -1;// 如果rear == 0 说明rear在最后的位置  也就是k的位置if (obj->rear == 0)return obj->queue[obj->k];elsereturn obj->queue[obj->rear - 1];
}void myCircularQueueFree(MyCircularQueue *obj) {free(obj->queue);free(obj);
}

相关文章:

【数据结构】设计环形队列

环形队列是一种线性数据结构&#xff0c;其操作表现基于 FIFO&#xff08;先进先出&#xff09;原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 环形队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里&#xff0c;一旦一个队列…...

无涯教程-JavaScript - COUPDAYSNC函数

描述 COUPDAYSNC函数返回从结算日期到下一个息票日期的天数。 语法 COUPDAYSNC (settlement, maturity, frequency, [basis])争论 Argument描述Required/OptionalSettlement 证券的结算日期。 证券结算日期是指在发行日期之后将证券交易给买方的日期。 RequiredMaturity 证…...

python 随机生成emoji表情

问答板块觉得比较有意思的问题 当时搜了些网上的发现基本都不能用&#xff0c;不知道是版本的问题还是咋的就开始自己研究 python随机生成emoji 问题的产生解决官网文档数据类型实现思路实现前提&#xff1a;具体实现&#xff1a; 其他常见用法插入 Emoji 表情&#xff1a;解析…...

python关闭指定进程以excel为例

先说下环境&#xff1a; Excel版本&#xff1a; Python2.7.13和Python3.10.4并存。 2、打开两个excel工作簿 看进程是这样的&#xff1a; 3、用python编程kill进程 # -*- coding: utf-8 -*- import os proc_nameEXCEL.EXE if __name__ __main__:os.system(taskkill /im {} /…...

前后端中的异步和事件机制 | 前后端开发

前言 在前后端程序设计开发工作中&#xff0c;小伙伴们一定都接触过事件、异步这些概念。出现这些概念的原因之一是&#xff0c;我们的代码在执行过程中所涉及的逻辑在不同的场合下执行时间的期望是各不相同的。为了尽量做到充分利用CPU等资源做尽可能多的事&#xff0c;免不了…...

设计模式篇(Java):装饰者模式

&#x1f468;‍&#x1f4bb;本文专栏&#xff1a;设计模式篇-装饰者模式 &#x1f468;‍&#x1f4bb;本文简述&#xff1a;装饰者模式的详解以及jdk中的应用 &#x1f468;‍&#x1f4bb;上一篇文章&#xff1a; 设计模式篇(Java)&#xff1a;桥接模式 &#x1f468;‍&am…...

Spark【RDD编程(三)键值对RDD】

简介 键值对 RDD 就是每个RDD的元素都是 &#xff08;key&#xff0c;value&#xff09;类型的键值对&#xff0c;是一种常见的 RDD&#xff0c;可以应用于很多场景。 因为毕竟通过我们之前Hadoop的学习中&#xff0c;我们就可以看到对数据的处理&#xff0c;基本都是以…...

从板凳围观到玩转行家:Moonbeam投票委托如何让普通用户一同参与

今年5月&#xff0c;Moonbeam发起了一项社区链上治理中投票委托反馈的调查。187位社区成员参与了这项调查&#xff0c;调查发现受访者对治理感兴趣&#xff0c;增加参与度只需要进行一些调整&#xff0c;即更简化的投票流程。 治理和去中心化是Web3的核心&#xff0c;随着Moon…...

SpringMVC的文件上传文件下载多文件上传---详细介绍

目录 前言&#xff1a; 一&#xff0c;文件上传 1.1 添加依赖 1.2 配置文件上传解析器 1.3 表单设置 1.4 文件上传的实现 二&#xff0c;文件下载 controller层 前端jsp 三&#xff0c;多文件上传 Controller层 运行 前言&#xff1a; Spring MVC 是一个基于 Java …...

Spark【RDD编程(四)综合案例】

案例1-TOP N个数据的值 输入数据&#xff1a; 1,1768,50,155 2,1218,600,211 3,2239,788,242 4,3101,28,599 5,4899,290,129 6,3110,54,1201 7,4436,259,877 8,2369,7890,27 处理代码&#xff1a; def main(args: Array[String]): Unit {//创建SparkContext对象val conf…...

Golang报错mixture of field:value and value initializers

Golang报错mixture of field:value and value initializers 这个错误跟编程习惯&#xff08;模式&#xff09;有关&#xff0c;都知道golang 语言的编程与java /python 以及其他的编程语言相似 &#xff0c;一通百通&#xff0c;易学万卷书。 编程中同一个结构中要保持唯一模…...

【网络教程】记一次使用Docker手动搭建BT宝塔面板的全过程(包含问题解决如:宝塔面板无法开启防火墙,ssh,nginx等)

文章目录 准备安装安装宝塔面板开启ssh和修改ssh的密码导出镜像问题解决宝塔面板无法开启防火墙无法启动ssh设置密码nginx安装失败设置开机启动相关服务准备 演示的系统环境:Ubuntu 22.04.3 LTS更新安装/升级docker到最新版本升级docker相关命令如下# 更新软件包列表并自动升级…...

【大虾送书第九期】速学Linux:系统应用从入门到精通

目录 &#x1f36d;写在前面 &#x1f36d;为什么学习Linux系统 &#x1f36d;Linux系统的应用领域 &#x1f36c;&#xff11;.Linux在服务器的应用 &#x1f36c;&#xff12;.嵌入式Linux的应用 &#x1f36c;&#xff13;.桌面Linux的应用 &#x1f36d;Linux的版本选择 &a…...

docker相关命令

####### 帮助启动类命令 ########## 启动docker systemctl start docker 停止docker systemctl stop docker 重启docker systemctl restart docker 查看docker状态 systemctl status docker 开机启动 systemctl enable docker 查看docker概要信息 docker info 查看…...

【Redis】4、rsync远程同步

与inodify结合使用&#xff0c;实现实时同步 rsync简介 rsync&#xff08;Remote Sync&#xff0c;远程同步&#xff09;是一个开源的快速备份工具&#xff0c;可以在不同主机之间镜像同步整个目录树&#xff0c;&#xff1b;支持增量备份&#xff0c;并保持链接和权限&#…...

无服务架构--Serverless

无服务架构 无服务架构&#xff08;Serverless Architecture&#xff09;即无服务器架构&#xff0c;也被称为函数即服务&#xff08;Function as a Service&#xff0c;FaaS&#xff09;&#xff0c;是一种云计算模型&#xff0c;用于构建和部署应用程序&#xff0c;无需关心…...

2023-09-07 LeetCode每日一题(修车的最少时间)

2023-09-07每日一题 一、题目编号 2594. 修车的最少时间二、题目链接 点击跳转到题目位置 三、题目描述 给你一个整数数组 ranks &#xff0c;表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。 同时给你…...

数据挖掘实验-主成分分析与类特征化

数据集&代码https://www.aliyundrive.com/s/ibeJivEcqhm 一.主成分分析 1.实验目的 了解主成分分析的目的&#xff0c;内容以及流程。 掌握主成分分析&#xff0c;能够进行编程实现。 2.实验原理 主成分分析的目的 主成分分析就是把原有的多个指标转化成少数几个代表…...

70. 爬楼梯 (进阶),322. 零钱兑换,279.完全平方数

代码随想录训练营第45天|70. 爬楼梯 &#xff08;进阶&#xff0c;322. 零钱兑换&#xff0c;279.完全平方数 70.爬楼梯文章思路代码 322.零钱兑换文章思路代码 279.完全平方数文章思路代码 总结 70.爬楼梯 文章 代码随想录|0070.爬楼梯完全背包版本 思路 将楼梯长度视为背…...

Apache Doris 2.0 如何实现导入性能提升 2-8 倍

数据导入吞吐是 OLAP 系统性能的重要衡量标准之一&#xff0c;高效的数据导入能力能够加速数据实时处理和分析的效率。随着 Apache Doris 用户规模的不断扩大&#xff0c; 越来越多用户对数据导入提出更高的要求&#xff0c;这也为 Apache Doris 的数据导入能力带来了更大的挑战…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...