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

server/2024/10/21 11:54:54/

一，队列的概念

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

队列（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.ppmy.cn/server/19916.html

相关文章

Linux驱动开发——（八）Linux异步通知

Linux驱动开发——（八）Linux异步通知

目录 一、异步通知简介 二、信号处理 2.1 驱动程序中的处理 2.1.1 fasync_struct结构体 2.1.2 fasync操作函数 2.1.3 kill_fasync函数 2.2 应用程序中的处理 三、驱动代码 一、异步通知简介 异步通知的核心就是信号。信号类似于硬件上使用的中断&#xff0c;只不过信号…
阅读更多...
【Day 8】MySQL 多表查询 + Mybatis 基础

【Day 8】MySQL 多表查询 + Mybatis 基础

1 多表查询 笛卡尔积&#xff1a;在数学中&#xff0c;两个集合(A集合 和 B集合)的所有组合情况 在多表查询时&#xff0c;需要消除无效的笛卡尔积 select * from tb_emp,tb_dept where dept_id tb_dept.id;多表查询分为&#xff1a; 连接查询 内连接&#xff1a;相当于查…
阅读更多...
【ARMv9 DSU-120 系列 5 -- CHI Interface】

【ARMv9 DSU-120 系列 5 -- CHI Interface】

请阅读【Arm DynamIQ™ Shared Unit-120 专栏 】 文章目录 DSU-120 CHI BUSAddress Target Groups配置步骤映射和管理Hashing for CHI transaction distribution散列过程和地址目标组识别散列函数定义两个地址目标组的散列四个地址目标组的散列八个地址目标组的散列架构框图
阅读更多...
什么是ISP，为什么跨境推荐ISP？

什么是ISP，为什么跨境推荐ISP？

ISP&#xff0c;全称Internet Service Provider&#xff0c;即“互联网服务提供商”。它是为个人或企业提供访问、使用或参与互联网服务的组织&#xff0c;主要为用户提供互联网接入业务、信息业务和增值业务。ISP是经国家主管部门批准的正式运营企业&#xff0c;享受国家法律保…
阅读更多...
【bugfix】error in chunk.js from uglifyjs

【bugfix】error in chunk.js from uglifyjs

检查是否是因为新安装的包不支持es5&#xff0c;通过babel 或者 fork 打包输出 es5以兼容老项目。
阅读更多...
每日算法之两两交换链表中的节点

每日算法之两两交换链表中的节点

题目描述 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4] 输出&…
阅读更多...
100290. 使矩阵满足条件的最少操作次数

100290. 使矩阵满足条件的最少操作次数

https://leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/description/ 正难则反。 暴力的遍历每一修改的情况&#xff0c;0-9&#xff1b;根据前一列的状态进行转移过来&#xff0c; 下面是状态转移方程 f ( i , j ) m a x ( f ( i , j ) , f ( i…
阅读更多...
《HCIP-openEuler实验指导手册》1.7 Apache虚拟主机配置

《HCIP-openEuler实验指导手册》1.7 Apache虚拟主机配置

知识点 配置步骤 需求 域名访问目录test1.com/home/source/test1test2.com/home/source/test2test3.com/home/source/test3 创建配置文件 touch /etc/httpd/conf.d/vhost.conf vim /etc/httpd/conf.d/vhost.conf文件内容如下 <VirtualHost *.81> ServerName test1.c…
阅读更多...
最新文章

Copyright @ 2022~2023