手把手教你实现书上的队列,进来试试?
一.队列的基本概念
队列的定义
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。
队头(Front):允许删除的一端,又称队首。
队尾(Rear):允许插入的一端。
空队列:不包含任何元素的空表。
2.队列的常见基本操作
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
一.队列设计
1.队列的顺序存储类型
#define MAXSIZE 50 //定义队列中元素的最大个数
typedef struct{dataType a[MAXSIZE]; //存放队列元素int front,rear;
}SeqQueue;
初始状态(队空条件):Q->front == Q->rear == 0。
进队操作:队不满时,先送值到队尾元素,再将队尾指针加1。
出队操作:队不空时,先取队头元素值,再将队头指针加1。
设计一个链式的队列
2.队列的链式存储类型
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
queue.h
#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
queue.c
初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
判断是否栈空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}
入栈
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
出栈
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;
}
获取队首元素/获取队尾元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
获取队列中元素的个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);//del = NULL;}pq->head = pq->tail = NULL;pq->size = 0;
}
二.循环队列
解决假溢出的方法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
当队首指针Q->front = MAXSIZE-1后,再前进一个位置就自动到0,这可以利用除法取余运算(%)来实现。
初始时:Q->front = Q->rear=0。
队首指针进1:Q->front = (Q->front + 1) % MAXSIZE。
队尾指针进1:Q->rear = (Q->rear + 1) % MAXSIZE。
队列长度:(Q->rear - Q->front + MAXSIZE) % MAXSIZE。
但是这种把循环队列存满数据的方式,会让我们不能通过Q->front == Q->rear来具体判断是否是队满还是队空,如图
(1)牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是种较为普遍的做法,约定以“队头指针在队尾指针的下一位置作为队满的标志”,如图
队满条件: (Q->rear + 1)%Maxsize == Q->front
队空条件仍: Q->front == Q->rear
队列中元素的个数: (Q->rear - Q ->front + Maxsize)% Maxsize
(2)类型中增设表示元素个数的数据成员。这样,队空的条件为 Q->size == O ;队满的条件为 Q->size == Maxsize 。这两种情况都有 Q->front == Q->rear
(3)类型中增设tag 数据成员,以区分是队满还是队空。tag 等于0时,若因删除导致 Q->front == Q->rear ,则为队空;tag 等于 1 时,若因插入导致 Q ->front == Q->rear ,则为队满。
下面针对第一种方法来设计一个循环顺序队列
三.双端队列
1、定义
双端队列是指允许两端都可以进行入队和出队操作的队列,如下图所示。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端,两端都可以入队和出队。
在双端队列进队时,前端进的元素排列在队列中后端进的元素的前面,后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时,无论是前端还是后端出队,先出的元素排列在后出的元素的前面。
2、特殊的双端队列
在实际使用中,根据使用场景的不同,存在某些特殊的双端队列。
输出受限的双端队列:允许在一端进行插入和删除, 但在另一端只允许插入的双端队列称为输出受限的双端队列,如下图所示。
输入受限的双端队列:允许在一端进行插入和删除,但在另一端只允许删除的双端队列称为输入受限的双端队列,如下图所示。若限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻接的栈。
相关文章:
手把手教你实现书上的队列,进来试试?
一.队列的基本概念队列的定义队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允…...
【springboot】springboot介绍
学习资料 SpringBoot 语雀 (yuque.com)【尚硅谷】SpringBoot2零基础入门教程(spring boot2干货满满)_哔哩哔哩_bilibiliSpringBoot2核心技术与响应式编程: SpringBoot2核心技术与响应式编程 (gitee.com) Spring 和Springboot 1、Spring能做什么 1.1…...
PMP项目管理项目整合管理
目录1 项目整合管理概述2 制定项目章程3 制定项目管理计划4 指导与管理项目工作5 管理项目知识6 监控项目工作7 实施整体变更控制8 结束项目或阶段1 项目整合管理概述 项目整合管理包括对隶属于项目管理过程组的各种过程和项目管理活动进行识别、定义、组合、统一和协调的各个…...
ADS中导入SPICE模型
这里写目录标题在官网中下载SPICE模型ADS中导入SPICE模型在官网中下载SPICE模型 英飞凌官网 ADS中导入SPICE模型 点击option,设置导入选项 然后点击ok 如果destination选择当前的workspace,那么导入完成之后如下: (推荐使用…...
C++:异常
在学习异常之前,来简单总结一下传统的处理错误的方式: 1. 终止程序,如assert,缺陷:用户难以接受。如发生内存错误,除0错误时就会终止程序。 2. 返回错误码,缺陷:需要程序员自己去查找…...
3.初识Vue
目录 1 vue 浏览器调试工具 1.1 安装 1.2 配置 2 数据驱动视图与双向数据绑定 3 简单使用 3.1 下载 3.2 将信息渲染到DOM上 4 使用vue浏览器调试工具 5 vue指令 1 vue 浏览器调试工具 chrome可能是我浏览器的原因,装上用不了,我们使…...
【C语言复习】程序的编译与链接
程序的编译与链接写在前面程序的编译与链接编译的过程程序编译环境程序执行过程编译链接的过程预处理预处理符号#define条件编译写在前面 程序的编译与链接是C语言中非常重要的一节。关键点在于详解C语言的程序编译和链接、宏的定义和与函数的区别、条件编译等知识。 程序的编…...
Golang sql 事务如何进行分层
在写代码过程中遇到了需要使用gorm执行sql事务的情况,研究了一下各位大佬的实现方案,结合了自身遇到的问题,特此记录。 代码架构介绍 . ├── apis ├── config ├── internal │ ├── constant │ ├── controller │ ├──…...
linux系统openssh升级
linux系统openssh升级 说明 整个过程不需要卸载原先的openssl包和openssh的rpm包。本文的环境都是系统自带的openssh,没有经历过手动编译安装方式。如果之前有手动编译安装过openssh,请参照本文自行测试是否能成功。 如果严格参照本文操作,保…...
力扣-求关注者的数量
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:1729. 求关注者的数量二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.正确…...
近红外荧光染料修饰氨基IR 825 NH2,IR 825-Amine,IR-825 NH2
IR 825 NH2,IR 825-NH2,IR825 Amine,IR825-Amine,新吲哚菁绿-氨基,荧光染料修饰氨基产品规格:1.CAS号:N/A2.包装规格:10mg,25mg,50mg,包装灵活&am…...
Android Crash和ANR监控
文章目录一、Crash1.1 概念1.2 类型二、ANR2.1 概念2.2 类型2.2.1 KeyDispatchTimeout(常见)2.2.2 BroadcastTimeout2.2.3 ServiceTimeout2.2.4 ContentProviderTimeout三、测试中如何关注3.1 Crash测试关注方法3.2 ANR测试关注方法四、如何记录与处理4.…...
【02 赖世雄英语语法:复句的语法】
复句的语法复句:把单句 连在一起(标点符号,连词,关系词)1. 连接符号1.1 破折号 — :补充说明,同位语1.2 冒号 : (同位语)1.3 分号 ; ( , 连词)&am…...
北斗导航 | 多参考一致性监测算法(MRCC)(附伪码)—— B值计算
===================================================== github:https://github.com/MichaelBeechan CSDN:https://blog.csdn.net/u011344545 ===================================================== MRCC 用于接收机失效检查与排除。在进行 MRCC 之前,先判断 4 台接收机…...
数字孪生与 UWB 人员定位:双剑合璧的智能物联新时代
人员定位是指利用各种定位技术对人员在特定场所的位置进行准确定位的技术。人员定位技术主要应用于需要实时监控、管理和保障人员安全的场所,如大型厂区、仓库、医院、学校、商场等。人员定位技术的应用范围非常广泛,例如:-在工厂生产线上&am…...
奇点云DataSimba发版全解析:“企业级”版本升级,提供最佳组合
近日,奇点云发布数据云产品商业化版本的全新升级:DataSimba(数据云平台)提供极速版、专业版、旗舰版、红旗版,可靠性、可用性、可服务性再进阶,四大版本满足不同企业选择。 「乐高式DIY」or「最佳组合」&am…...
2-7 SpringCloud快速开发入门: Eureka 注册中心高可用集群搭建
接上一章节Eureka 服务注册中心发现与消费服务,这里讲讲Eureka 注册中心高可用集群搭建 Eureka 注册中心高可用集群搭建 Eureka 注册中心高可用集群就是各个注册中心相互注册 Eureka Server的高可用实际上就是将自己作为服务向其他服务注册中心注册自己,…...
STL中的函数对象
STL-函数对象 函数对象概念 重载函数调用操作符的类,其对象常称为函数对象函数对象使用重载的()时,行为类似函数调用,也叫仿函数 本质 函数对象(仿函数)是一个类,不是一个函数—修改算法策略—采用虚拟对象调用 函数对象的使用理…...
linux下libevent的编译安装
1,官网下载最新的,https://libevent.org/2,将文件解压,虚拟机可以右键解压,也可以用命令解压,tar zxvf libevent.tar.gz,进行解压缩。这里压缩包的名称只是举例,实际它还会带上版本号…...
深度学习部署笔记(十): CUDA RunTime API-2.2流的学习
1. 流的定义 流(Stream)是一个基于上下文(Context)的任务管道抽象,是一组由GPU依次执行的CUDA操作序列,其中每个操作可能会使用或产生数据。在一个上下文中可以创建多个流,每个流都拥有自己的任…...
[ROC-RK3568-PC] [Firefly-Android] 10min带你了解I2C的使用
🍇 博主主页: 【Systemcall小酒屋】🍇 博主追寻:热衷于用简单的案例讲述复杂的技术,“假传万卷书,真传一案例”,这是林群院士说过的一句话,另外“成就是最好的老师”,技术…...
工作记录:举步维艰的在线 word 之旅 - tinymce
项目中需要实现 “在线编辑 word 模板” 的功能,我打算使用富文本组件 tinymce ,因为业务需求比较特殊,研究一下 tinymce 是否能实现。 如何在 vue 项目中引用 tinymce,可以看另一篇文章 《在 vue 项目中使用 tinymce》 &#x…...
动态规划编译距离
583. 两个字符串的删除操作方法:dp状态表示:以i-1和j-1为结尾的字符串world1和world2,抵达相同的字符串所需的最少操作数属性:最小值状态计算:world1[i-1]和world2[j-1]相同dp[i][j] dp[i-1][j-1];world1[i-1]和world…...
Netty 教程 – 解码器详解
TCP以流的方式进行数据传输,上层的应用为了对消息进行区分,往往采用如下方式 固定消息长度,累计读取到长度和定长LEN的报文后,就认为读取到了个完整的消息,然后将计数器位置重置在读取下一个报文内容将回车换行符作为…...
Allegro如何自动添加测试点操作指导
Allegro如何自动添加测试点操作指导 在做PCB设计的时候,在一些应用场合下需要给PCB上的网络添加测试点,如下图 测试点除了可以手动逐个添加之外,Allegro还支持自动添加测试点,具体操作如下 点击Manufacture点击Testprep...
【CSS】CSS 背景设置 ③ ( 背景位置-长度值设置 | 背景位置-长度值方位值同时设置 )
文章目录一、背景位置-长度值设置二、背景位置-长度值方位值同时设置三、完整代码示例一、背景位置-长度值设置 长度值设置 效果展示 : 设置背景位置为具体值 10px 50px : 粉色区域是盒子的区域 , 图片背景位于盒子位置 x 轴方向 10 像素 , y 轴方向 50 像素 ; 在水平方向上 ,…...
AbTest —— 不同场景下的应用模式
文章目录不同人群眼中的 AbTestAbTest 不同的功能倚重用户关联性弱,经典场景为 Feed - 部门组织形式大多非垂直业务用户关联性强,经典场景为 垂类/工具类APP;部门组织形式大多为垂直业务康为定律-组织决定产品形态不同应用模式下服务构建开机…...
fast-api 一款快速将spring的bean发布成接口并生产对应swagger文档调试的轻量级工具
fast-api简介背景开发痛点:分析需求实战fast-api快速上手1. 引入依赖2. FastApiMapping标记service对象3. swagger2/knife4j 在线测试进阶使用开启调试模式支持指定类或包目录发布如何关闭fast-api自定义fast-api的前缀写在最后简介 fast-api 一款快速将spring的bean(service)发…...
以公益之名 让人类发现数学之美
目录 1.品牌理念高举高打 2.创新赛制 赋能品牌 3.全球化的品牌传播 9月26日,2022阿里巴巴全球数学竞赛获奖名单公布,4座金杯分别由平均年龄25岁,来自美国麻省理工学院、美国布朗大学、北京大学在读数学博士斩获。77位获奖者中00后超五成引热…...
JUC并发编程之HashMap(jdk1.7版本)-底层源码探究
目录 JUC并发编程之HashMap(jdk1.7版本)-底层源码探究 HashMap底层源码 - jdk1.7 基本概念 -采取层层递进,问答式 存储Key-Value的结构 常量和成员变量 构造方法 put方法 inflateTable方法 hash方法 indexFor方法 addEntry方法 resize方法 createEntry…...
QT Q_OBJECT 和 signals/slots
Q_OBJECT宏展开 #define Q_OBJECT \ public: \QT_WARNING_PUSH \Q_OBJECT_NO_OVERRIDE_WARNING \static const QMetaObject staticMetaObject; \virtual const QMetaObject *metaObject() const; \virtual void *qt_metacast(const char *); \virtual int qt_metacall(QMetaOb…...
APM新添加UAVCAN设备
简介 UAVCAN是一种轻量级协议,旨在通过CAN总线在航空航天和机器人应用中实现可靠通信。要实现通信,最基本需要data_type_ id, signature、数据结构、设备程序初始化。 添加设备数据结构文件(.uavcan格式) 1.在以下路径添加设备数据结构文件,根据设备类…...
【C++】string类基本用法
文章目录string类基本用法1. 为什么要学习string类?1.1 C语言中的字符串2. 标准库中的string类2.1 string类2.2 string类的常用接口说明小试牛刀1. 仅仅反转字母2. 字符串中第一个唯一字符3. 字符串中最后一个单词的长度string类基本用法 1. 为什么要学习string类&…...
KDZD耐电压高压击穿强度测试仪
一、技术参数 01、输入电压: 交流 220 V。 02、输出电压: 交流 0--50KV ; 直流 0—50kv 。 03、电器容量:3KVA。 04、高压分级:0—50KV,(全程可调)。 05、升压速率:0.1KV/s-…...
数组和指针面试题的补充(细的抠jio)
生命是一条艰险的峡谷,只有勇敢的人才能通过。 ——米歇潘 说明:用的vs都是x86的环境,也就是32位平台。 建议:对于难题来说,一定要配合画图来解决问题。 第一题: #include<stdio.h> int…...
Java多线程基础
文章目录Java多线程基础一、什么是进程与线程?二、线程和进程的区别【重点】三、线程的创建方式【重点】1. 继承Thread类2. 实现Runnable接口3. lambda 表达式四、Thread的常见属性线程中断自己定义一个标志位Thread类提供的静态方法线程的状态Java多线程基础 一、…...
爆品分析第5期 | 一条视频带货3700+,这款斋月不锈钢厨具套装火了!
俗话说民以食为天,吃在任何一种文化中都占据重要的位置,要做出一道美味佳肴,除了食材、烹饪者的自身厨艺之外,还少不了一口好锅。新冠疫情以来,全世界范围内的封闭让很多人养成了居家做饭的习惯,不仅为厨具…...
团队管理的七个要点
要掌握团队管理的要点和做好团队管理工作,不是一件容易的事,但也远非想象中那么难。首先,我个人比较推荐所有团队管理者都能阅读下《经理人参阅:团队管理》(注意该书仅可其官网获得)这本佳作。相信会为你带…...
Go语言容器之map、list和nil
一、map map和C中map一样,里面存放的是key-value键值对在Go中map是引用类型,声明语法:var map变量名 map[key的类型]value的类型package mainimport "fmt"func main() {var mp map[string]intmpls : map[string]int{"one&quo…...
软件测试的案例分析 - 闰年1
(这是关于博客质量分的测试 https://www.csdn.net/qc) 我们谈了不少测试的名词, 软件是人写的, 测试计划和测试用例也是人写的, 人总会犯错误。错误发生之后, 总有人问: 为什么这个bug 没有测出来啊?! 我们看看一类简单的bug是如何发生的,以及如何预防…...
【强化学习】强化学习数学基础:值函数近似
值函数近似Value Function ApproximationMotivating examples: curve fittingAlgorithm for state value estimationObjective functionOptimization algorithmsSelection of function approximatorsIllustrative examplesSummary of the storyTheoretical analysisSarsa with …...
JVM系列——Java与线程,介绍线程原理和操作系统的关系
并发不一定要依赖多线程(如PHP中很常见的多进程并发)。 但是在Java里面谈论并发,基本上都与线程脱不开关系。因此我们讲一下从Java线程在虚拟机中的实现。 线程的实现 线程是比进程更轻量级的调度执行单位。 线程的引入,可以把一个进程的资源分配和执行调…...
C++打开文件夹对话框之BROWSEINFO
头文件 #include <shlobj.h> #include <windows.h> #include <stdio.h> using namespace std; 案例 string chooseFile(void) {//用户选择的路径,可以是TCHAR szBuffer[MAX_PATH] {0};然后再使用TCHAR 转char字符串,此处可以直接使…...
Nuxt项目配置、目录结构说明-实战教程基础-Day02
Nuxt项目配置、目录结构说明-实战教程基础-Day02一、Nuxt项目结构1.1资源目录1.2 组件目录1.3 布局目录1.4 中间件目录1.5 页面目录1.6 插件目录1.7 静态文件目录1.8 Store 目录1.9 nuxt.config.js 文件1.10 package.json 文件其他:别名二、项目配置2.1 build2.2 cs…...
单链表的头插,尾插,头删,尾删等操作
前言顺序表要求是具有连续的物理空间,并且数据的话是在这些空间当中是连续的存储。但这样会带来很多问题,比如说在头部或者说中间插入的话,效率不是很高;并且申请空间可能需要扩容,并且越往后一般来说都是异地扩容&…...
Qt扫盲-QProcess理论总结
QProcess理论使用总结一、概述二、使用三、通过 Channel 通道通信四、同步进程API五、注意事项1. 平台特性2. 不能实时读取一、概述 QProcess 其实更多的是与外面进程进行交互的一个工具类,通过这个类来启动外部进程,获取这个进程的标准输出,…...
JAVA进阶 —— Steam流
目录 一、 引言 二、 Stream流概述 三、Stream流的使用步骤 1. 获取Stream流 1.1 单列集合 1.2 双列集合 1.3 数组 1.4 零散数据 2. Stream流的中间方法 3. Stream流的终结方法 四、 练习 1. 数据过滤 2. 数据操作 - 按年龄筛选 3. 数据操作 - 演员信息要求…...
Ubuntu Protobuf 安装(测试有效)
安装流程 下载软件 下载自己要安装的版本:https://github.com/protocolbuffers/protobuf 下载源码编译: 系统环境:Ubuntu16(其它版本亦可),Protobuf-3.6.1 编译源码 cd protobuf# 当使用 git clone 下来的…...
驱动程序开发:FTP服务器和OpenSSH的移植与搭建、以及一些笔记
目录一、FTP服务器移植与搭建1、在ubuntu下安装vsftpd2、在window下安装FileZilla3、移植vsftpd到开发板上4、Filezilla 连接测试5、注意点二、开发板 OpenSSH 移植与使用1、移植 zlib 库2、移植 openssl 库3、移植 openssh 库4、openssh 使用测试三、关于u-boot上的操作及根文…...
优化改进YOLOv5算法之添加GIoU、DIoU、CIoU、EIoU、Wise-IoU模块(超详细)
目录 1、IoU 1.1 什么是IOU 1.2 IOU代码 2、GIOU 2.1 为什么提出GIOU 2.2 GIoU代码 3 DIoU 3.1 为什么提出DIOU 3.2 DIOU代码 4 CIOU 4.1 为什么提出CIOU 4.2 CIOU代码 5 EIOU 5.1 为什么提出EIOU 5.2 EIOU代码 6 Wise-IoU 7 YOLOv5中添加GIoU、DIoU、CIoU、…...