//队列的顺序存储
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 1024

//动态数组结构体
struct dynamic_arr
{
    void **pArry;//指向堆区数据的指针
    int maxsize; //数组容量
    int size; //数组大小
};

//初始化动态数组
struct dynamic_arr * init_arr(int maxsize){
    if (maxsize<=0)
    {
        return  NULL;
    }
    //给数组分配空间
    struct dynamic_arr *arry=malloc(sizeof(struct dynamic_arr)); //arry是指向结构体的指针

    //给数组初始化
    arry->pArry=malloc(sizeof(void *) *maxsize);//把真实的数据开辟到堆区（之所以是void*，是因为不知道存放在数组中的元素类型是什么。）
    arry->maxsize=maxsize;
    arry->size=0;
    return arry;
}

//数组的插入
void insert(struct dynamic_arr *pArr,int pos,void *data){ //pos是插入位置，data是插入的数据
    if (pArr==NULL)
    {
        return;
    }
    if (data==NULL)
    {
        return;
    }
    //插入位置非法就尾插
    if (pos<0||pos>pArr->size)
    {
        pos=pArr->size;
    }
    
    //当前数组满了之后扩容
    if (pArr->size==pArr->maxsize)
    {
        //1.计算新空间大小
        int newMaxsize=pArr->maxsize*2;

        //2.为新数据开辟新空间
        void **newParr=malloc(sizeof(void *)*newMaxsize);

        //3.将原来数据拷贝至新空间
        memcpy(newParr,pArr->pArry,sizeof(void*)*pArr->maxsize);

        //4.释放原有内存空间
        free(pArr->pArry);

        //5.更新新空间指向
        pArr->pArry=newParr;

        //6.更新新容量
        pArr->maxsize=newMaxsize;
        
    }
    //插入新元素
    for (int i = pArr->size-1; i >=pos; i--)
    {
        //数据向后移动
        pArr->pArry[i+1]=pArr->pArry[i];
    }
    pArr->pArry[pos]=data; //插入新元素
    pArr->size++; //更新数组中元素的个数
}

//删除元素
void removeDynamic(struct dynamic_arr *pArr,int pos){
    if (pArr==NULL)
    {
        return;
    }
    if (pos<0||pos>pArr->size-1)
    {
        return;
    }
    
    //数据前移
    for (int i = pos; i < pArr->size-1; i++)
    {
        pArr->pArry[i]=pArr->pArry[i+1];
    }
    pArr->size--; //更新size大小
}

//遍历数组
void foreach(struct dynamic_arr *pArr,void(*myPrint)(void *)){ //第二个参数是回调函数
    if(pArr==NULL)
    return;
    if (myPrint==NULL)
    {
        return;
    }
    
    for (int i = 0; i < pArr->size; i++)
    {
       myPrint(pArr->pArry[i]);
    }
    
}

//销毁数组
void destroy_Dynamic(struct dynamic_arr *pArr){
    if (pArr==NULL)
    {
        return;
    }
    if (pArr->pArry!=NULL)
    {
        free(pArr->pArry);
        pArr->pArry=NULL;
    }
    free(pArr);
    pArr=NULL;
}



typedef void* sqQueue;

//初始化队列
sqQueue init_queue(){
    struct dynamic_arr * arr=init_arr(MAXSIZE);
    return arr;
}

//入队
void push_queue(sqQueue queue,void *data){
    if (queue==NULL||data==NULL)
    {
        return;
    }
    struct dynamic_arr * myqueue=queue;

    if (myqueue->size==MAXSIZE) //队满
    {
        return;
    }
    
    //入队本质就是尾插数组
    insert(myqueue,myqueue->size,data);
}

//出队
void pop_queue(sqQueue queue){
    if (queue==NULL)
    {
        return;
    }
    struct dynamic_arr * myqueue=queue;
    if (myqueue->size<=0) //队空
    {
        return;
    }
    //出队本质就是头删
    removeDynamic(myqueue,0); 
}

//返回队列大小
int size_queue(sqQueue queue){
    if (queue==NULL)
    {
        return -1;
    }
    struct dynamic_arr * myqueue=queue;
    return myqueue->size;
}

//判断队列是否为空
int isEmpty_queue(sqQueue queue){
    if (queue==NULL)
    {
        return -1;
    }
    struct dynamic_arr * myqueue=queue;
    if (myqueue->size==0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

//返回队头元素
void * front_queue(sqQueue queue){
    if (queue==NULL)
    {
        return NULL;
    }
    struct dynamic_arr * myqueue=queue;
    return myqueue->pArry[0];
}

//返回队尾元素
void * rear_queue(sqQueue queue){
    if (queue==NULL)
    {
        return NULL;
    }   
    struct dynamic_arr * myqueue=queue;
    return myqueue->pArry[myqueue->size-1]; 
}

//销毁队列
void destroy_queue(sqQueue queue){
    if (queue==NULL)
    {
        return;
    }   
    destroy_Dynamic(queue);    
}










struct Person
{
	char name[64];
	int age;
};
void test01()
{
	//初始化队列
	sqQueue myQueue= init_queue();

	//准备数据
	struct Person p1 = { "aaa", 10 };
	struct Person p2 = { "bbb", 20 };
	struct Person p3 = { "ccc", 30 };
	struct Person p4 = { "ddd", 40 };


	//入队
	push_queue(myQueue, &p1);
	push_queue(myQueue, &p2);
	push_queue(myQueue, &p3);
	push_queue(myQueue, &p4);
	printf("队列大小为：%d\n", size_queue(myQueue));
	while ( isEmpty_queue(myQueue) == 0)
	{
		//访问队头
		struct Person * pFront = front_queue(myQueue);
		printf("队头元素 -- 姓名：%s  年龄： %d\n", pFront->name, pFront->age);
		//访问队尾
		struct Person * pBack = rear_queue(myQueue);
		printf("队尾元素 -- 姓名：%s  年龄： %d\n", pBack->name, pBack->age);
		//出队
		pop_queue(myQueue);
	}

	printf("队列大小为：%d\n", size_queue(myQueue));

	//销毁队列
	destroy_queue(myQueue);

}
int main()
{   
    test01();
    return 0;
}