#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义各种结构（不管是顺序表还是链表都是在模仿老师的定义结构的方法），以后在定义结构的时候一定要学会自己去定义结构
//此时这个结构体的定义就很像是单量表实现的定义
typedef int QDataType;
typedef struct QueueNode //这个就是队列中的单链表的结构的定义（用单链表实现队列就一定要有单链表结构的定义）
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue //此时的这个结构体应该才是我（队列）的主结构体，上面那个结构体应该只是一个单量表的结构体（因为此时我是想要用单链表来实现我的队列），上面那个结构体也就是我的单链表中的一个一个的结点而已（就是用上面的这个结构体来设计我的队列中的每一个结点而已，这样就有点像是我的单链表）
{
  QueueNode* head;
  QueueNode* tail;//虽然这个结构体是队列的关键，但是这个结构体中的成员，还是要根据我的需求来定义的
}Queue;
//typedef struct Queue //此时的这个结构体应该才是我（队列）的主结构体，上面那个结构体应该只是一个单量表的结构体（因为此时我是想要用单链表来实现我的队列），上面那个结构体也就是我的单链表中的一个一个的结点而已（就是用上面的这个结构体来设计我的队列中的每一个结点而已，这样就有点像是我的单链表）
//{
//  QueueNode* head;
//  QueueNode* tail;//虽然这个结构体是队列的关键，但是这个结构体中的成员，还是要根据我的需求来定义的
//}Queue;
//并且此时的这个双指针可以不使用结构体定义（但是如果不使用结构体的话，此时的传参就要进行一定的改变了）
//例如：void QueueInit(Queue* pq); 不使用结构体此时就要写成 void QueueInit(QueueNode** pphead,QueueNode** pptail);
//void QueueInit(QueueNode** pphead, QueueNode** pptail);不仅要传二级指针（因为我会改变函数外部的值），而且要进行两个指针参数的传递，可谓是非常的复杂
//此时以上的这些代码的意思（就是创建了两个结构体（也就是两种类型），有了这两种类型，我就可以实现我的队列了），所以这个也就是我的队列的基本的结构体定义
//为什么一定是以下的接口：这个就是性质决定的
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);//这个就是表示取队头数据的意思
QDataType QueueBack(Queue* pq); //这个就是表示取队尾数据的意思
size_t QueueSize(Queue* pq);//这个就是计算队列中的数据个数
bool QueueEmpty(Queue* pq);//这个就是用来判断这个队列是否为空

#include"Stack.h"
//初始化
void QueueInit(Queue* pq)
{
  //此时为什么传参接收参数的时候不需要二级指针呢？
  //原因就是：我使用了两个结构体类型
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
//销毁(此时销毁的就是一个一个动态内存开辟出来的结点，这个结点就是从另一个结构体的定义之中来的)
void QueueDestory(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur != NULL)
  {
    QueueNode* next = cur->next;//保存下一个（因为我是一个链表）
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//插入
void QueuePush(Queue* pq, QDataType x)
{
  //因为此时已经把结构体的地址传过来了，所以此时就可以对结构体进行改变了
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;//这个就是结点是初始化
  //此时先进行队列有无数据的判断
  if (pq->head == NULL)//这个表示无
  {
    //这个就是此时的把我的结构体进行改变，但是要注意进行结构体的改变一定要进行结构体地址的传递，然后要用一级指针接收
    pq->head = pq->tail = newnode;//这个就是表示此时的这个队列一个值都还没有，所以此时就可以把这个newnode给我的head和tail
  }
  else//这个就是有（然后有数据，此时因为是一个队列，所以此时我们就需要在这个队列的后面插入一个新的结点，因为队列的特点（一头进一头出）），然后此时就需要在tail这个表示尾的指针后面进行一个尾插，这样就可以完成队列的插入功能
  {
    pq->tail->next = newnode;
    pq->tail = newnode;//上面那个是主要的完成插入的步骤，下面这个没什么主要的功能（其实就只是想让我的tail继续保持在最后一个结点的位置而已）
  }
}
//删除
void QueuePop(Queue* pq)
{
  //因为队列的特性（队尾入，队头出）
  //所以删除数据是已经规定死了的，只能在队头删
  assert(pq);
  //还是那两种写法：1.温柔的写法  2.暴力的写法
  //if (pq->head == NULL)
  //{
  //  return;
  //}
  //assert(pq->head != NULL);
  //并且下面这个函数 QueueEmpty(pq) 为真就是表示此时的pq->head为空，为假就表示此时的pq->head不为空
  assert(!QueueEmpty(pq));//这个在报错（就是说明此时的这个QueueEmpty(pq)函数为真，然后(!QueueEmpty(pq))加了一个感叹号就表示此时整个为假），所以此时这个断言的意思就是判断这个pq->head不为空，为空就报错
  Queue* next = pq->head->next;
  free(pq->head);
  pq->head = NULL;
  pq->head = next;//完成这些基本的操作，我们一定还要注意几个注意点
  //因为此时可能会把整个队列都给删空，所以此时当删到只有一个数据的时候，此时就要进行tail的置空，不然就有野指针问题
  if (pq->head == NULL)//此时这个为空，就是表示已经删完了（但是此时只是把head给处理完了，这边还剩了一个tail指针（此时如果把最后一个数据也删掉，那么此时的tail就会变成一个野指针），所以我们在删除最后一个数据的时候，一定要注意tail的置空，不然就是野指针）
  {
    pq->tail = NULL;
  }
}
//取队头的数据
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//此时就是表示我的头已经为空了，所以我已经不能再去取头数据了
  return pq->head->data;//这个就是表示队列头的数据
}
//取队尾的数据
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//判断队列不为空
  return pq->tail->data;//此时为了寻找我队列的尾（也就是入口），并且此时的tail就是指向我队列的尾数据，所以想要找尾中的数据，只需要把tail->data给返回去就行了
}
//计算队列中的数据个数
size_t QueueSize(Queue* pq)
{
  assert(pq);
  int n = 0;
  QueueNode* cur = pq->head;
  while (cur != NULL)//想要计算数据个数，自然要遍历我的队列
  {
    n++;
    cur = cur->next;//有了这步上面那步就不需要写成cur->next != NULL;了
  }
  return n;
}
//判断队列是否为空（在删除的时候会用到，因为删除的时候队列是不可以为空的，所以要进行一定的判断）
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}