数据结构----队列
一、队列
1)队列定义
队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 允许插入的端是队尾,允许删除的端是队头。队列是一个先进先出(FIFO)的线性表,相应 的也有顺序存储和链式存储两种方式。
2)循环队列
顺序存储就是用数组实现,比如有一个n个元素的队列,数组下标0的一端是队 头,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,但是如果删除 队头元素,后面的元素就要往前移动,对应的时间复杂度就是O(n),性能自然不 高。
为了提高出队的性能,就有了循环队列,需要有两个指针,front指向队头,rear指 向对尾元素的下一个位置,元素出队时front往后移动,如果到了对尾则转到头部, 同理入队时rear后移,如果到了对尾则转到头部,这样通过下标front出队时,就不 需要移动元素了。

同时规定,当队列为空时,front和rear相等,那么队列什么时候判断为满呢?按照 循环操作rear依次后移,然后再从头开始,也是出现rear和front相等时,队列满。
这样跟队列空的情况就相同了,为了区分这种情况,规定数组还有一个空闲单元 时,就表示队列已满, (也就是队头指针在队尾指针的下一位置时,队满。) 因为rear 可能在front后面,也可能循环到front前面,所以队列满的条件就变成了 (rear+1)%maxsize == front 。 对于队列的元素个数计算为:(rear -front+maxsize)%maxsize。
3)用数组实现的顺序存储循环队列
4) 链式队列
循环队列要事先申请好空间,整个过程都不能释放,而且要有固定的长度,如果长度事先无法估计,这种方式显然不够灵活;所以就引入了链式存储队列,其实就是 线性表的单链表,只是它只能对尾进,队头出。并且规定队头指针指向链队列的头结点,对尾指针指向终端节点,当队列为空时,front和rear都指向头结点。(尾插头删)
入队操作,就是在链表尾部插入结点;出队操作就是头结点的后继结点出队,然后将头结点的后继后移。如果最后除了头结点外,只剩一个元素了,就把rear也指向头结点。

二、队列的操作步骤
1.构建静态数组队列结构
1)建立结构体
2)初始化队列
3)入队
4)出队
5)遍历
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include<stdbool.h>
#include<assert.h>//静态数组构建队列结构
#define SIZE 5
typedef int ele_type;typedef struct queue
{ele_type arr[SIZE];int front;int real;
} Queue;//初始化队列
void init(Queue* que)
{assert(que);memset(que->arr, 0, sizeof(ele_type) * SIZE);que->front = 0;que->real = 0;
}//插入元素--入队
bool push_queue(Queue* que, ele_type val)
{assert(que);if ((que->real + 1) % SIZE == que->front)return false;que->arr[que->real] = val;que->real++;que->real = que->real % SIZE;return true;}//删除元素--出队
bool pop_queue(Queue* que, ele_type* rtval)
{assert(que);if (que->front == que->real)return false;*rtval = que->arr[que->front++];que->front = que->front % SIZE;return true;}//遍历队列
void print_queue(Queue* que)
{if (que->front == que->real)return;if (que->front < que->real){for (int i = que->front; i < que->real; i++){printf("%d\n", que->arr[i]);}}else{for (int i = que->front; i < SIZE; i++){printf("%d\n", que->arr[i]);}for (int i = 0; i < que->real; i++){printf("%d\n", que->arr[i]);}}}//获取数组长度
int get_queue_size(Queue* que)
{return ((que->real - que->front + SIZE) % SIZE);}//清空数组
void Clear_queue(Queue* que)
{que->front = que->real = 0;}int main()
{Queue q;init(&q);push_queue(&q, 11);push_queue(&q, 12);push_queue(&q, 13);push_queue(&q, 14);ele_type temp;pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);push_queue(&q, 15);push_queue(&q, 16);printf("===================\n");print_queue(&q);printf("ele num=%d\n", get_queue_size(&q));return 0;
}
运行结果:

2.构建链表队列结构
1)建立结构体
2)初始化队列
3)入队
4)出队
5)遍历
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include<stdbool.h>
#include<assert.h>//静态数组构建队列结构
#define SIZE 5
typedef int ele_type;typedef struct queue
{ele_type arr[SIZE];int front;int real;
} Queue;//初始化队列
void init(Queue* que)
{assert(que);memset(que->arr, 0, sizeof(ele_type) * SIZE);que->front = 0;que->real = 0;
}//插入元素--入队
bool push_queue(Queue* que, ele_type val)
{assert(que);if ((que->real + 1) % SIZE == que->front)return false;que->arr[que->real] = val;que->real++;que->real = que->real % SIZE;return true;}//删除元素--出队
bool pop_queue(Queue* que, ele_type* rtval)
{assert(que);if (que->front == que->real)return false;*rtval = que->arr[que->front++];que->front = que->front % SIZE;return true;}//遍历队列
void print_queue(Queue* que)
{if (que->front == que->real)return;if (que->front < que->real){for (int i = que->front; i < que->real; i++){printf("%d\n", que->arr[i]);}}else{for (int i = que->front; i < SIZE; i++){printf("%d\n", que->arr[i]);}for (int i = 0; i < que->real; i++){printf("%d\n", que->arr[i]);}}}//获取数组长度
int get_queue_size(Queue* que)
{return ((que->real - que->front + SIZE) % SIZE);}//清空数组
void Clear_queue(Queue* que)
{que->front = que->real = 0;}int main()
{Queue q;init(&q);push_queue(&q, 11);push_queue(&q, 12);push_queue(&q, 13);push_queue(&q, 14);ele_type temp;pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);push_queue(&q, 15);push_queue(&q, 16);printf("===================\n");print_queue(&q);printf("ele num=%d\n", get_queue_size(&q));return 0;
}
运行结果:

相关文章:
数据结构----队列
一、队列 1)队列定义 队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 允许插入的端是队尾,允许删除的端是队头。队列是一个先进先出(FIFO)的线性表,相应 的也有顺序存储和链式存储两种方式。 2&#…...
【python】实现对文件夹中的图像连续重命名方法
import os import shutildef rename_images(input_folder):# 获取输入文件夹下的所有图片文件(假设都是.jpg格式)image_files [f for f in os.listdir(input_folder) if os.path.isfile(os.path.join(input_folder, f)) and f.endswith(".jpg"…...
【nginx 第一篇章】认识一下 NGINX 服务器
一、简介 Nginx (engine x) 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。由俄罗斯程序员 Igor Sysoev 开发,并在2004年首次公开发布。Nginx 以其高并发处理能力、低内存消耗、稳定性、丰富的功能集、简单的配置以及低学…...
【物联网】(防水篇)哪些电子产品需要通过 IPX7 防水级别测试?
哪些电子产品需要通过 IPX7 防水级别测试? 举例一些可能需要通过 IPX7 防水级别测试的产品 - 电子产品:如智能手机、平板电脑、智能手表、运动手环等,以满足用户在不同场景下的使用需求,例如在潮湿环境或意外沾水时仍能正常工作。…...
高级java每日一道面试题-2024年8月09日-网络篇-什么是XSS攻击如何避免?
如果有遗漏,评论区告诉我进行补充 面试官: 什么是XSS攻击如何避免? 我回答: XSS(Cross-Site Scripting,跨站脚本攻击)是一种常见的Web应用程序安全漏洞,攻击者通过在网页中注入恶意脚本,当其他用户浏览这些网页时&…...
Linux时间管理:命令与脚本的完美结合
目录 前言 Linux时间管理命令 date命令 cron定时任务 at命令 sleep命令 脚本与时间命令的结合使用 备份脚本示例 设置cron任务 监控脚本执行时间 结论 致谢 前言 在Linux系统中,时间管理是一项基础而关键的任务。无论是安排周期性的备份、监控任务的执…...
基于ssm+vue+uniapp的微信外卖小程序
开发语言:Java框架:ssmuniappJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:M…...
lvs(linux virtual server)实例
一.lvs概述 1.1什么是lvs LVS(Linux Virtual Server)是一个基于Linux操作系统的虚拟服务器技术,用于实现负载均衡和高可用性。LVS通过将客户端的请求分发到多台后端服务器上,从而提高整体服务的处理能力和可靠性。LVS主要有两个组…...
Unity游戏开发
Unity游戏开发 系列文章的目录: 第一章:Hello,Unity! “好读书,不求甚解;每有会意,便欣然忘食。” 本文目录: Unity游戏开发 Unity游戏开发前言今天我们来体验一下unity开发创建第一…...
5. MQTT消息类型详解(三)
9 SUBACK消息 9.1 消息结构 SUBACK消息是订阅确认消息,格式如下: ------------------------------- | 消息类型(1字节) | ------------------------------- | 保留标志(1字节) …...
TypeScript JSX
介绍 在线的免费的代码转换器工具:可以把HTML 代码移植到 JSX 语法。还支持很多其他的转换。 JSX 是 ECMAScript 的一种类似 XML 的语法扩展,没有任何定义的语义。它不打算由引擎或浏览器实现。它并不是将 JSX 纳入 ECMAScript 规范本身的提议。它旨在供…...
java里的序列化反序列化、HttpMessageConverter、Jackson、消息转化器、对象转化器...都是啥?
前段时间在学习SSM框架(spring boot、spring MVC、mybatis)后端项目的时候,发现他们的项目里:响应类Result类要实现Serializable接口、转化响应给前端的时间数据的格式要用到什么“消息转换器”MappingJackson2HttpMwssageConvert…...
GNU/Linux - memtool使用
在Yocto中为NXP的i.MX系列芯片构建Linux系统时,可以加入一些实用工具,比如直接操作内存的memtool。 这些工具在imx-test包中,比如imx-test_git.bb里。 比如在imx-image-core.bb中,IMAGE_INSTALL "imx-test" ࿰…...
Qt5.12.8源码交叉编译带openssl版本
一.背景 近期项目由于对接方的Qt版本是Qt5.12.8,后台服务是https的,之前用的Qt5.15.10要切换成Qt5.12.8,并且为了能支持https,必须要重新编译Qt。 二.环境 环境准备: Ubuntu版本 :18.04; openss…...
串行并行数据转换
前言 串行数据传输通常在数据传输距离较远时使用,而并行数据传输适用于短距离、高速数据交换。通过转换,可以根据实际需求选择合适的传输方式,以优化数据传输效率和速度。串行数据传输在长距离传输中可以减少信号的干扰和失真,因为…...
推荐一个优秀的 .NET MAUI 组件库
目录 前言 组件介绍 组件展示 布局 按钮 复选框 进度条 导航栏 组件地址 最后 前言 .NET MAUI 的发布,项目中可以使用这个新的跨平台 UI 框架来轻松搭建的移动和桌面应用。 为了帮助大家更快地构建美观且功能丰富的应用,本文将推荐一款优秀…...
用Manim创建条形图【BarChart】
BarChart是Manim库中用于创建条形图的函数。它允许用户通过一组值创建一个条形图,其参数可以调整条形的外观和布局。 BarChart(values, bar_namesNone, y_rangeNone, x_lengthNone, y_lengthNone, bar_colors[#003f5c, #58508d, #bc5090, #ff6361, #ffa600],bar_w…...
iMES工厂管家:强大的工厂管理系统
iMES工厂管家:强大的工厂管理系统 在现代工厂管理中,iMES工厂管家作为一款功能强大的MES系统,为用户提供了全面的管理解决方案。本文将介绍iMES工厂管家的基本信息、特点、以及如何快速部署和使用。 软件简介 iMES工厂管家是一款基于.NetCor…...
iOS ------ 事件响应链
响应者链 响应者链是由一系列链接在一起的响应者(UIResponser之类:UIApplication,UIViewController,UIView)注组成的。一般情况下,一条响应链开始于第一响应者,结束于application对象。如果一个…...
Go 语言 switch 语句的特点
在 Go 语言中,switch 语句设计得更加简洁和直观,因此不需要显式使用 break 语句来终止一个分支。这种设计决策源于 Go 语言的一些设计哲学和目标,主要包括: 自动终止: Go 语言的 switch 语句会在每个 case 执行完成后自…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
Unity VR/MR开发-VR开发与传统3D开发的差异
视频讲解链接:【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...
