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 要创建栈的大小
//创建失败返回NULL
	SeqQueue* 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;





}