一,队列的概念
队列是一种特殊的受限制的线性表。
队列(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;}