数据结构----队列
一、队列
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 执行完成后自…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
