C++11 数据结构5 队列的概念,队列的顺序存储,实现,测试

一,队列的概念

队列是一种特殊的受限制的线性表。  

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

队列是一种先进先出的t(First In First Out)的线性表,简称FIFO。允许插入的一端为队尾,允许删除的一端为队头。队列不允许在中间部位进行操作!假设队列是q=(a1,a2,……,an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,总是在队列最后。这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后来的当然排在队伍最后。如下图:

二,队列的顺序存储

那么如果用数组来模拟队列,情况说明如下,我们这里采用 尾部插入,头部删除的case进行处理

三,  队列顺序存储的代码实现

#ifndef __005SEQQUEUE_H__#define __005SEQQUEUE_H__//这两个是要给 所有人公开的
typedef void SeqQueueNode;
typedef void SeqQueue;//对外提供的方法//初始化队列,要动态的创建SeqQueue,根据user设定的大小创建
//int stacksize ,表示user 要创建队列的大小
//创建失败返回NULL
SeqQueue* createSeqQueue(int queuesize);//入队列 ,给队列的头部插入一个元素,插入点是在数组的尾部
//参数queue 表示要插入的栈
//参数 seqQueueNode 表示要插入的 节点
//成功 返回 1
//失败 返回<0
int push_SeqQueue(SeqQueue* queue, SeqQueueNode * seqQueueNode);//出队列 将队列的头部的第一个元素删除,删除点是在数组的头部
//参数stack 表示要删除第一个元素的栈
//成功 返回 1
//失败 返回<0
//说明,最开始的时候,让删除栈顶元素,返回int,但是这个设计是不合理的。
//因为假设上层是Teacher,这个Teacher里的元素有 char *,char**,且这两个空间也是malloc的,那么上层需要释放这两个malloc出来的元素。
//这意味着我们需要将 pop_SeqStack中的元素返回上去,上层才有机会释放,底层怎么知道上层搞的是个啥存的?因此一定要给上层,让上层去释放。//出队列 将队列的头部的第一个元素删除,删除点是在数组的头部
//参数seqqueue 表示要删除第一个元素的队列
//成功 返回 删除的第一个元素
//失败 返回 NULL
SeqQueueNode* pop_SeqQueue(SeqQueue* seqqueue);//返回队列元素,将队列头部的第一个元素返回
//失败返回NULL
//成功返回节点
SeqQueueNode* top_SeqQueue(SeqQueue* seqqueue);//返回队列大小
//成功 返回 队列的大小
//失败 返回<0
int size_SeqQueue(SeqQueue* seqqueue);//返回user对队列分配的大小
//成功 返回 队列的大小
//失败 返回<0 
int capacity_SeqQueue(SeqQueue* seqqueue);//判断队列是否为空
//成功 返回1 表示队列为空 
//成功 返回0 表示队列不为空
//失败 返回-1 表示该函数执行的时候有问题
int isEmpty_SeqQueue(SeqQueue* seqqueue);//销毁队列
//成功 返回1 表示成功销毁队列 
//失败 返回-1 表示该函数执行的时候有问题
int Destory_SeqQueue(SeqQueue* seqqueue);#endif

#include "005seqqueue.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"//栈的内部结构,不用写在.h文件中,一会要移动位置
typedef struct SeqQueue {//队列中的数组,存储的是数据的指针,假设我们的数据是Teacher,那么arr[0] 中的数据就应该是&Tea1,//也就是说,这是一个数组,数组的每一个成员里面都存放的是指针。//本质上是一个  void * arr[], 也可以看成是 int * arr[],因为实际上放的就是 Teacher的指针 SeqQueueNode **data;int m_QueueSize;//队列的实际大小int m_QueueCapacity;//队列的总大小,也就是user给定的大小
}TSeqQueue;//对外提供的方法//初始化队列,要动态的创建SeqQueue,根据user设定的大小创建
//int stacksize ,表示user 要创建队列的大小
//创建失败返回NULL
SeqQueue* createSeqQueue(int queuesize) {TSeqQueue* ss = NULL;ss = (TSeqQueue*)malloc(sizeof(TSeqQueue));if (ss == NULL) {printf("createSeqQueue func error\n");return ss;}memset(ss, 0, sizeof(TSeqQueue));ss->m_QueueSize = 0;ss->m_QueueCapacity = queuesize;ss->data = (SeqQueueNode**)malloc(sizeof(SeqQueueNode *) * queuesize);if (ss->data == NULL) {printf("createSeqQueue func error ss->data == NULL \n");return NULL;}memset(ss->data, 0, sizeof(ss->data));return ss;
}//入队列 ,给队列的头部插入一个元素,插入点是在数组的尾部
//参数queue 表示要插入的栈
//参数 seqQueueNode 表示要插入的 节点
//成功 返回 1
//失败 返回<0
int push_SeqQueue(SeqQueue* queue, SeqQueueNode * seqQueueNode) {int ret = 1;if (queue == NULL) {ret = -1;printf("push_SeqQueue func error because stack==NULL ret=-1 and return\n");return ret;}if (seqQueueNode == NULL) {ret = -2;printf("push_SeqQueue func error because seqQueueNode==NULL ret=-2 and return\n");return ret;}TSeqQueue* st = (TSeqQueue*)queue;if (st->m_QueueCapacity == st->m_QueueSize) {ret = -3;printf("push_SeqQueue func error because st->m_StackCapccity == st->m_StackSize ret = -3 and return st->m_StackSize = %d, st->m_StackCapccity = %d\n",st->m_QueueSize,st->m_QueueCapacity);return ret;}//前面检查都完毕了,到这里就真的可以插入了,实行的是尾插法st->data[st->m_QueueSize] = seqQueueNode;st->m_QueueSize++;return ret;
}//出队列 将队列的头部的第一个元素删除,删除点是在数组的头部
//参数stack 表示要删除第一个元素的栈
//成功 返回 1
//失败 返回<0
//说明,最开始的时候,让删除栈顶元素,返回int,但是这个设计是不合理的。
//因为假设上层是Teacher,这个Teacher里的元素有 char *,char**,且这两个空间也是malloc的,那么上层需要释放这两个malloc出来的元素。
//这意味着我们需要将 pop_SeqStack中的元素返回上去,上层才有机会释放,底层怎么知道上层搞的是个啥存的?因此一定要给上层,让上层去释放。//出队列 将队列的头部的第一个元素删除,删除点是在数组的头部
//参数seqqueue 表示要删除第一个元素的队列
//成功 返回 删除的第一个元素
//失败 返回 NULL
SeqQueueNode* pop_SeqQueue(SeqQueue* seqqueue) {SeqQueueNode* ret = NULL;if (seqqueue == NULL) {ret = NULL;printf("pop_SeqQueue func error because stack==NULL and return\n");return ret;}TSeqQueue * tq = (TSeqQueue *)seqqueue;if (tq->m_QueueSize == 0) {ret = NULL;printf("pop_SeqQueue func error because tq->m_QueueSize == 0 and return\n");return ret;}//执行到这里,说明可以删除ret = tq->data[0];//这里有移动的操作。因为删除的是 数组的第一个元素for (int i = 0; i < tq->m_QueueSize; ++i) {tq->data[i] = tq->data[i + 1];}tq->m_QueueSize--;return ret;
}//返回队列元素,将队列头部的第一个元素返回
//失败返回NULL
//成功返回节点
SeqQueueNode* top_SeqQueue(SeqQueue* seqqueue) {SeqQueueNode* ret = NULL;if (seqqueue == NULL) {ret = NULL;printf("top_SeqQueue func error because stack==NULL and return\n");return ret;}TSeqQueue * tq = (TSeqQueue *)seqqueue;if (tq->m_QueueSize == 0) {ret = NULL;printf("top_SeqQueue func error because tq->m_QueueSize == 0 and return\n");return ret;}//执行到这里,说明队列是有元素的ret = tq->data[0];return ret;
}//返回队列大小
//成功 返回 队列的大小
//失败 返回<0
int size_SeqQueue(SeqQueue* seqqueue){int ret = 0;if (seqqueue == NULL) {ret = -1;printf("size_SeqQueue func error because stack==NULL and return\n");return ret;}TSeqQueue * tq = (TSeqQueue *)seqqueue;return tq->m_QueueSize;}//返回user对队列分配的大小
//成功 返回 队列的大小
//失败 返回<0 
int capacity_SeqQueue(SeqQueue* seqqueue) {int ret = 0;if (seqqueue == NULL) {ret = -1;printf("capacity_SeqQueue func error because stack==NULL and return\n");return ret;}TSeqQueue * tq = (TSeqQueue *)seqqueue;return tq->m_QueueCapacity;
}//判断队列是否为空
//成功 返回1 表示队列为空 
//成功 返回0 表示队列不为空
//失败 返回-1 表示该函数执行的时候有问题
int isEmpty_SeqQueue(SeqQueue* seqqueue) {int ret = 0;if (seqqueue == NULL) {ret = -1;printf("isEmpty_SeqQueue func error because stack==NULL and return\n");return ret;}TSeqQueue * tq = (TSeqQueue *)seqqueue;if (tq->m_QueueSize ==0) {ret = 1;}else {ret = 0;}return ret;
}//销毁队列
//成功 返回1 表示成功销毁队列 
//失败 返回-1 表示该函数执行的时候有问题
int Destory_SeqQueue(SeqQueue* seqqueue) {int ret = 1;if (seqqueue == NULL) {ret = -1;printf("isEmpty_SeqQueue func error because stack==NULL and return\n");return ret;}TSeqQueue * tq = (TSeqQueue *)seqqueue;if (tq->data!=NULL) {free(tq->data);}tq->data = NULL;free(tq);seqqueue = NULL;return ret;}

#define _CRT_SECURE_NO_WARNINGS
#define _CRTDBG_MAP_ALLOC
#include "iostream"
#include <stdio.h>
#include <stdlib.h>extern "C" {
#include "005seqqueue.h"
}typedef struct Teacher {int age;char name[128];char *othername;char **stuname; //一个老师下面有5个学生
}Teacher;int main() {_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口int ret = 0;//初始化队列,要动态的创建SeqStack,根据user设定的大小创建
//int stacksize ,表示user 要创建栈的大小
//创建失败返回NULLSeqQueue* seqqueue = createSeqQueue(1024);if (seqqueue == NULL) {ret = -1;printf("func createSeqQueue error because seqstack = NULL return ret =-1\n");return ret;}ret = isEmpty_SeqQueue(seqqueue);printf("isEmpty_SeqQueue = ret %d\n", ret);ret = size_SeqQueue(seqqueue);printf("size_SeqQueue = ret %d\n", ret);ret = capacity_SeqQueue(seqqueue);printf("capacity_SeqQueue = ret %d\n", ret);Teacher tea1;tea1.age = 20;strcpy(tea1.name, (const char*)"tea1");tea1.othername = (char *)malloc(sizeof(char) * 128);memset(tea1.othername, 0, sizeof(char) * 128);strcpy(tea1.othername, (const char*)"tea1othername");tea1.stuname = (char **)malloc(sizeof(char *) * 5);memset(tea1.stuname, 0, sizeof(char *) * 5);for (size_t i = 0; i < 5; i++){tea1.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符memset(tea1.stuname[i], 0, sizeof(char) * 128);sprintf(tea1.stuname[i], "tea1stuname%d", i + 1);}Teacher tea2;tea2.age = 22;strcpy(tea2.name, (const char*)"tea2");tea2.othername = (char *)malloc(sizeof(char) * 128);memset(tea2.othername, 0, sizeof(char) * 128);strcpy(tea2.othername, (const char*)"tea2othername");tea2.stuname = (char **)malloc(sizeof(char *) * 5);memset(tea2.stuname, 0, sizeof(char *) * 5);for (size_t i = 0; i < 5; i++){tea2.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符memset(tea2.stuname[i], 0, sizeof(char) * 128);sprintf(tea2.stuname[i], "tea2stuname%d", i + 1);}Teacher tea3;tea3.age = 33;strcpy(tea3.name, (const char*)"tea3");tea3.othername = (char *)malloc(sizeof(char) * 128);memset(tea3.othername, 0, sizeof(char) * 128);strcpy(tea3.othername, (const char*)"tea3othername");tea3.stuname = (char **)malloc(sizeof(char *) * 5);memset(tea3.stuname, 0, sizeof(char *) * 5);for (size_t i = 0; i < 5; i++){tea3.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符memset(tea3.stuname[i], 0, sizeof(char) * 128);sprintf(tea3.stuname[i], "tea3stuname%d", i + 1);}ret = push_SeqQueue(seqqueue, &tea1);if (ret < 0) {printf("push_SeqQueue(seqqueue, (SeqStackNode * )&tea1) func error ret =%d \n", ret);return ret;}push_SeqQueue(seqqueue, &tea2);if (ret < 0) {printf("push_SeqQueue(seqqueue, (SeqStackNode * )&tea2) func error ret =%d \n", ret);return ret;}push_SeqQueue(seqqueue, &tea3);if (ret < 0) {printf("push_SeqQueue(seqqueue, (SeqStackNode * )&tea3) func error ret =%d \n", ret);return ret;}printf("-after-\n");ret = isEmpty_SeqQueue(seqqueue);printf("isEmpty_SeqQueue = ret %d\n", ret);ret = size_SeqQueue(seqqueue);printf("size_SeqQueue = ret %d\n", ret);ret = capacity_SeqQueue(seqqueue);printf("capacity_SeqQueue = ret %d\n", ret);while (size_SeqQueue(seqqueue) > 0) {Teacher * temptea = (Teacher *)top_SeqQueue(seqqueue);if (temptea == NULL) {printf("can not get find teacher\n");}printf("temptea->age = %d,temptea->name = %s,temptea->othername=%s\n",temptea->age,temptea->name,temptea->othername);for (size_t j = 0; j < 5; j++){printf("temptea->stuname[%d] = %s,  ",j, temptea->stuname[j]);}Teacher * deltea = (Teacher *)pop_SeqQueue(seqqueue);if (deltea == NULL) {printf("pop_SeqStack seqstack error\n");}if (deltea->othername != NULL) {free(deltea->othername);}if (deltea->stuname != NULL) {for (size_t i = 0; i < 5; i++){if (deltea->stuname[i] != NULL) {free(deltea->stuname[i]);}}free(deltea->stuname);deltea->stuname = NULL;}printf("\n");}printf("sss\n");//销毁栈//成功 返回1 表示成功销毁栈 //失败 返回-1 表示该函数执行的时候有问题ret = Destory_SeqQueue(seqqueue);return 0;}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数组和指针经典笔试题讲解

目录 创作不易&#xff0c;如对您有帮助&#xff0c;还望一键三连&#xff0c;谢谢&#xff01;&#xff01;&#xff01; 1.sizeof和strlen的对比 1.1sizeof 1.2strlen 1.3sizeof和strlen对比 2.数组笔试题讲解 数组名的理解 2.1一维数组 2.2字符数组 题目一&#x…

【skill】usbwebserver的几个问题

试了几个云服务器&#xff08;华为云、移动10086云&#xff09;&#xff0c;使用usbwebserver均会出现问题。 以前都是找缺少的对应的dll文件&#xff0c;不仅搜索半天、解压、移动复制、同时还要考虑文件的位数 有人说C:\Windows\System32存放的是64位的东西有人说C:\Windows…

Axure设计美观友好的后台框架页

使用Axure设计后台框架页 优点介绍&#xff1a; **1、使用中继器灵活配置菜单项&#xff1b; 2、二级菜单面板跟随一级菜单位置显示&#xff1b; 3、菜单链接打开后&#xff0c;联动添加tab标签&#xff1b; 4、标签页与iframe内容联动&#xff0c;可关闭&#xff1b; 5、左侧…

车道分割YOLOV8-SEG

车道分割YOLOV8-SEG&#xff0c;训练得到PT模型&#xff0c;然后转换成ONNX&#xff0c;OPENCV的DNN调用&#xff0c;支持C,PYTHON,ANDROID开发 车道分割YOLOV8-SEG

Xline中区间树实现小结

Table of Contents 实现区间树的起因区间树实现简介 插入/删除查询重叠操作使用Safe Rust实现区间树 问题Rc<RefCell<T>> i. 线程安全问题其他智能指针 i. Arc<Mutex<T>>? ii. QCell数组模拟指针总结 01、实现区间树的起因 在Xline最近的一次重构中…

苍穹外卖学习笔记(8.用户端历史订单模块,商家端订单管理模块)

目录 一、商家端订单管理模块1、查看历史订单2、查询订单详情3、取消订单4、再来一单5、代码开发6、测试 二、用户端历史订单模块1、订单搜索2、各个状态的订单数量统计3、查询订单详情4、接单5、拒单6、取消订单7、派送订单8、完成订单9、代码开发10、测试 三、校验收货地址是…

逆向案例二十九——复杂扣代码,七某数据(一)

网址&#xff1a;aHR0cHM6Ly93d3cucWltYWkuY24vcmFuaw 抓包分析载荷中有加密参数analysis&#xff1a; 获取数据代码&#xff0c;经过分析&#xff0c;发现analysis确实是校验参数cai&#xff1a; import requestscookies {qm_check: A1sdRUIQChtxen8pI0dAMRcOUFseEHBeQF0JT…

31.Gateway网关-跨域问题

跨域 1.域名不同&#xff1a;www.baidu.com和www.taobao.com,www.taobao.org 2.域名相同&#xff0c;端口不同。localhost:8080和localhost:8081 跨域问题 浏览器禁止请求的发起者与服务端发生跨域ajax请求&#xff0c;请求被浏览器拦截的问题。 解决方案 CORS 浏览器询…

安全开发实战(2)---域名反查IP

目录 安全开发专栏 前言 域名与ip的关系 域名反查ip的作用 1.2.1 One 1.2.2 Two 1.2.3 批量监测 ​总结 安全开发专栏 安全开发实战http://t.csdnimg.cn/25N7H 这步是比较关键的一步,一般进行cdn监测后,获取到真实ip地址后,或是域名时,然后进行域名反查IP地址,进行进…

PySide6 GUI 学习笔记——Python文件编译打包

前面编写的软件工具都必须运行在Python环境中&#xff0c;且通过命令行的方式运行&#xff0c;通过Python打包工具&#xff0c;我们可以把.py文件封装成对应平台的运行文件&#xff0c;供用户执行。 常见Python打包工具 工具简介官网/文档地址py2exe将Python脚本转换为Window…

速卖通自养号测评:如何规避安全风险?

对于初涉电商领域的新卖家而言&#xff0c;进行销量测评显得尤为关键。由于速卖通新店铺往往难以获得平台活动的支持&#xff0c;流量也相对匮乏&#xff0c;因此&#xff0c;开店的首要任务便是进行测评&#xff0c;通过积累一定的评论和销售数据。 测评的益处颇多&#xff0…

【大语言模型LLM】- Meta开源推出的新一代大语言模型 Llama 3

&#x1f525;博客主页&#xff1a;西瓜WiFi &#x1f3a5;系列专栏&#xff1a;《大语言模型》 很多非常有趣的模型&#xff0c;值得收藏&#xff0c;满足大家的收集癖&#xff01; 如果觉得有用&#xff0c;请三连&#x1f44d;⭐❤️&#xff0c;谢谢&#xff01; 长期不…

Unity对应的c#版本

本文主要是记录一下unity已经开始兼容c#的版本和.net版本&#xff0c;以便更好的利用c#的特性。 c#和.net对应情况 微软已经将.net开发到.net 9了&#xff0c;但是unity的迭代速度远没有c#迭代速度快&#xff0c;已知unity最新的LTS版本unity2023已经兼容了c#9 可以在unity手册…

【深度学习】yolo-World,数据标注,zeroshot,目标检测

仓库&#xff1a;https://github.com/AILab-CVC/YOLO-World 下载权重&#xff1a; 仓库下载和环境设置 下载仓库&#xff1a;使用以下命令从 GitHub 上克隆仓库&#xff1a; git clone --recursive https://github.com/AILab-CVC/YOLO-World.git创建并激活环境&#xff1a…

网络安全新挑战:通用人工智能(AGI)等级保护指南

通用人工智能&#xff08;AGI&#xff09;的发展现状及趋势 随着2023年大语言模型应用的划时代突破&#xff0c;以ChatGPT为杰出代表的此类技术犹如一股洪流&#xff0c;彻底颠覆了人类与机器智能交互的疆界&#xff0c;引领通用人工智能&#xff08;AGI&#xff09;步入一个崭…

【继承和多态】

闭上眼睛&#xff0c;什么都不听.............................................................................................................. 文章目录 前言 一、【继承】 1.1【继承的概念】 1.2【 继承的定义】 1.2.1【定义格式】 1.2.2【继承关系和访问限定符】 1.2…

回归预测 | Matlab实现SA-BP模拟退火算法优化BP神经网络多变量回归预测

回归预测 | Matlab实现SA-BP模拟退火算法优化BP神经网络多变量回归预测 目录 回归预测 | Matlab实现SA-BP模拟退火算法优化BP神经网络多变量回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab实现SA-BP模拟退火算法优化BP神经网络多变量回归预测&#xff0…

OGG extract进程占据大量虚拟内存导致服务器内存异常增长分析

现象 oracle服务器一节点内存&#xff0c;一个月来持续升高&#xff0c;近一月上涨10%左右。 问题分析 OS内存使用情况 使用内存最大的10个进程如下&#xff0c;PID为279417占用最大的内存。 查询279417&#xff0c;发现是ogg相关进程。 发现ogg的extract进程占用了大量的虚拟内…

27 - 数据传送指令

---- 整理自B站UP主 踌躇月光 的视频 文章目录 1. CPU 电路2. 数据传送指令的几种情况3. 实验工程4. 实验结果 1. CPU 电路 2. 数据传送指令的几种情况 # program.asm; 1. ; MOV A, 5;; 2. ; MOV A, B;; 3. ; MOV A, [5];; 4. ; MOV B, 6 ; MOV A, [B]; 5. ; MOV [0x2f], 5;; …

Apache RocketMQ ACL 2.0 全新升级

作者&#xff1a;徒钟 引言 RocketMQ 作为一款流行的分布式消息中间件&#xff0c;被广泛应用于各种大型分布式系统和微服务中&#xff0c;承担着异步通信、系统解耦、削峰填谷和消息通知等重要的角色。随着技术的演进和业务规模的扩大&#xff0c;安全相关的挑战日益突出&am…