队列的基本结构体
typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
//函数的声明
void QueueInist(Queue* ps);
void QueueDestory(Queue* ps);
void QueuePush(Queue* ps, QDataType x);
void QueuePopt(Queue* ps);
size_t QueueSize(Queue* ps);
bool QueueEmpty(Queue* ps);
QDataType QueueBack(Queue* ps);
QDataType QueueFront(Queue* ps);
//队列基本功能实现后才可以进行这个题目的解决
void QueueInits(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 QueuePopt(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;
}
//上面是队列功能的实现，下面是具体关于这个题目的解答：
//一定要注意：不能去改变队列的结构，只能去调用队列提供的接口函数实现
//实现栈的队列结构
typedef struct MyStack
{
  Queue q1;  //一个q1队列的结构体
  Queue q2;  //一个q2队列的结构体
  //此时就是用这两个队列去实现我的栈
}MyStack;
MyStack* myStackCreate()//此时的这个函数的作用就是，创建一个结构体然后把这个结构体的地址传给我，这样我就可以使用这个结构体的地址了
{
/*  MyStack st;
  return &st;*///返回结构体的地址（就是相当于我的自己去调用这个结构体创建变量  Queue q; 的意思，反正就是为了拿到结构体）
  //但是此时不能像上面这样去写，因为按照上面这样去写的意思是创建了一个局部的变量（这个变量是随着栈帧的，出了函数这个变量就会消失）
  //所以我此时就不可以使用局部变量（一定要在堆区搞一个变量），所以这变就可以malloc一个变量出来（这样这个变量就不会消失了）
  MyStack* st = (MyStack*)malloc(sizeof(MyStack));//当然有的人说可以在静态区搞一个全局的变量（但是因为全局变量容易出现各种各样的问题，所以这边我们不使用）
  if (st == NULL)
  {
    printf("malloc faile\n");
    exit(-1);
  }
  //此时有了这个新的结构体变量（我们就要对其进行初始化）
  // 但是我们这边进行初始化的时候一定要注意：不能去改变队列的结构，只能去调用队列提供的接口函数实现
  //就是初始化我刚刚创建的那个结构体中的指针（切记不敢直接自己初始化，最后是调用队列实现中的函数）
  QueueInits(&st->q1);//想要初始化结构体中的变量，就要对结构体进行改变（所以改变结构体就要传结构体的地址）
  QueueInits(&st->q1);
  //这边再次强调一遍，当我们在做oj题的时候一定不能去改变队列的结构（要通过去调用我自己实现的队列的接口函数来实现）
}
void myStackPush(MyStack* obj, int x)
{
  //按照解题原理，我们这边可以很好的把这个插入函数给写出来
  if (!QueueEmpty(&obj->q1))//这个就是表示此时的q1不为空
  {
    QueuePush(&obj->q1, x);
  }
  //反正就是保持这个位置的核心原则（一个有数据，一个无数据）
  else
  {
    QueuePush(&obj->q2, x);
  }
}
int myStackPop(MyStack* obj)
{
  int top = 0;
  //此时先默认我的q1为空，q2不为空
  Queue* emptyQ = &obj->q1;
  Queue* noemptyQ = &obj->q2;
  //此时假如假设错了
  if (!QueueEmpty(&obj->q1))//这个就是假设错了，此时的q1是为空，q2是不为空的
  {
    emptyQ = &obj->q2;//此时就把这个逻辑反过来
    noemptyQ = &obj->q1;
  }
  else
  {
    //这里就表示我假设对了
    while (QueueSize(noemptyQ) > 1)
    {
      //此时就可以将数据进行转换了
      QueuePush(emptyQ, QueueFront(noemptyQ));
      QueuePopt(noemptyQ);
    }
      top = QueueFront(noemptyQ);//保存最后一个数据
    QueuePopt(noemptyQ);
  }
  return top;
}
int myStackTop(MyStack* obj)
{
  if (!QueueEmpty(&obj->q1))
  {
    return QueueBack(&obj->q1);
  }
  else
  {
    return QueueBack(&obj->q2);
  }
}
bool myStackEmpty(MyStack* obj)
{
  return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
  //此时的free一定要小心，因为我的结构体中还有一个结构体所以这边的free一定要进行两次的free
  QueueDestory(&obj->q1);
  QueueDestory(&obj->q2);
  //记住此时是全程都不会使用队列中的结构，都是在调用我自己实现的那个队列中的结构（这个一定要注意，因为这个是一个oj题）
  free(obj);
}
int main()
{
  MyStack* st = myStackCreate();
  myStackPush(st, 1);
  myStackPush(st, 2);
  myStackPush(st, 3);
  myStackPush(st, 4);
  myStackPush(st, 5);
  QueueDestory(st);
  return 0;
}

typedef struct Stack
{
  int* a;
  int top;
  int capacity;
}Stack;
void StackInit(Stack* ps);
//销毁
void StackDestory(Stack* ps);
//栈顶插入
void StackPush(Stack* ps, int x);
//栈顶删除
void StackPop(Stack* ps);
//寻找栈顶(这个肯定是有返回值的)
int StackTop(Stack* ps);
//还有一个就是计算栈的大小
int StackSize(Stack* ps);
//判断栈是否为空
int StackEmpty(Stack* ps);
void StackInit(Stack* ps)//错误
{
  //int* a = NULL;
  //int top = 0;
  //int caapcity = 0;
  //又在犯这种一直犯的错误
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
void StackPush(Stack* ps, int x)
{
  //首先我要插入数据第一步就是要弄一个新的结点出来
  if (ps->capacity == ps->top)//此时这个就是表示我的容量的大小等于我的此时的数组的大小
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapacity);
    if (tmp == NULL)
    {
      printf("realloc faile\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
  ps->a[ps->top] = x;//这里的两个ps->top 的意思是不一样的，一个是起着下标的作用，一个是起记录个数的作用
  ps->top++;
}
void StackDestory(Stack* ps)
{
  //while (ps->top != NULL)
  //free(ps->top);
  //我真的很不理解为什么这边要这样去写
  //真的要搞清楚这个东西（只是一个数组而已，因为此时的a指针指向的就是我的我开辟出来的那块空间，所以直接把这个a指针释放掉就是把所有的栈给释放掉了）
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPop(Stack* ps)
{
  //对是对了，但是没有进行条件的判断，这边一定要进行一步不为空的判断
  assert(ps->top > 0);
  ps->top--;
}
int StackTop(Stack* ps)
{
  assert(ps->top > 0);
  return ps->a[ps->top - 1];//这个位置一定要理解（因为我的top一直都只是栈顶，这个top是不会改变位置的，top++的意思只是数值加加了而已，并且在括号中的top也就只是起下标的作用而已）
}
//我真的是人才，栈你找栈底的位置干嘛
//int  StackBack(Stack* ps)
//{
//  return ps->a[ps->top - 1];
//}
int StackSize(Stack* ps)
{
  return ps->top;
}
int StackEmpty(Stack* ps)
{
  return ps->top == 0;
}
typedef struct {
  Stack pushST;
  Stack popST;
} MyQueue;
MyQueue* myQueueCreate() {
  MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
  StackInit(&q->pushST);
  StackInit(&q->popST);//这边就还是那句话（想要改变结构体你就一定要传这个结构体的地址，不然你改个屁）
  return q;//这个的注意点已经是写过了，就是要注意局部变量出了函数会销毁（变成一个空指针）
  //所以我们这边就算是传地址也是没有用的，所以这边一定要malloc一块空间，不然随着栈帧的改变，这个变量就会销毁
  //所以这变一定要用上面这个方式，不能用返回地址的方式
}
void myQueuePush(MyQueue* obj, int x) {
  StackPush(&obj->pushST, x);  //这步就是不管三七二十一，入数据就是往pushST里面入
}
int myQueuePop(MyQueue* obj) {
  //如果popST中没有数据就把pushST中的数据导过去
  //popST中的数据就符合先进先出的顺序了
  if (StackEmpty(&obj->popST))
  {
    while (!StackEmpty(&obj->pushST))
    {
      StackPush(&obj->popST, StackTop(&obj->pushST));//这步就是函数的嵌套（就是为了把pushST中的数据导入到popST之中），看不明白就多看几遍
      StackPop(&obj->pushST);
    }
  }
  int front = StackTop(&obj->popST);
  StackPop(&obj->popST);
  return front;
}
int myQueuePeek(MyQueue* obj) {   //获得最头上的数据
  //如果popST中没有数据就把pushST中的数据导过去
//popST中的数据就符合先进先出的顺序了
  if (StackEmpty(&obj->popST))
  {
    while (!StackEmpty(&obj->pushST))
    {
      StackPush(&obj->popST, StackTop(&obj->pushST));//这步就是函数的嵌套（就是为了把pushST中的数据导入到popST之中），看不明白就多看几遍
      StackPop(&obj->pushST);
    }
  }
  return StackTop(&obj->popST);//一定要记住这个popST是一个栈，是栈，所以我在使用函数时，要按照栈的方式去使用，不然完蛋
}
bool myQueueEmpty(MyQueue* obj) {
  return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
  //只是是两层
  StackDestory(&obj->pushST);
  StackDestory(&obj->popST);
  free(obj);
}

typedef struct stack
{
  int* a;
  int capacity;
  int top;
}stack;
void StackPush(stack* ps, int x);
void StackInit(stack* ps);
int StackTop(stack* ps);
int StackSize(stack* ps);
int StackEmpty(stack* ps);
int StackPop(stack* ps);
void StackDestory(stack* ps);
int myQueueFront(MyQueue* ps);
void myQueuePush(MyQueue* ps, int x);
void myQueueDestory(MyQueue* ps);
int myQueueEmpty(MyQueue* ps);
//1.
void StackPush(stack* ps, int x)
{
  if (ps->capacity == ps->top)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapacity);
    if (tmp == NULL)
    {
      printf("realloc faile\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackInit(stack* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
int StackTop(stack* ps)
{
  assert(ps);
  return ps->a[ps->top - 1];
}
void StackDestory(stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
}
int StackPop(stack* ps)
{
  assert(ps->top > 0);
  ps->top--;
}
int StackSize(stack* ps)
{
  return ps->top;
}
int StackEmpty(stack* ps)
{
  return ps->top == 0;
}
typedef struct MyQueue
{
  stack Push;
  stack Pop;
}MyQueue;
MyQueue* myQueueCreate()
{
  MyQueue* q = malloc(sizeof(MyQueue));
  StackInit(&q->Pop);
  StackInit(&q->Push);
  return q;
}
void myQueuePush(MyQueue* ps,int x)
{
  StackPush(&ps->Push, x);
}
void myQueuePop(MyQueue* ps)
{
  if (StackEmpty(&ps->Pop))
  {
    while (!StackEmpty(&ps->Push))
    {
      StackPush(&ps->Pop, StackTop(&ps->Push));
    }
  }
  int front = StackTop(&ps->Pop);
  StackPop(&ps->Pop);
  return front;
}
int myQueueEmpty(MyQueue* ps)
{
  return StackEmpty(&ps->Pop) && StackEmpty(&ps->Push);
}
int myQueueFront(MyQueue* ps)
{
  if (StackEmpty(&ps->Pop))
  {
    while (!StackEmpty(&ps->Push))
    {
      StackPush(&ps->Pop, StackTop(&ps->Push));
    }
  }
  return StackTop(&ps->Pop);
}
void myQueueDestory(MyQueue* ps)
{
  StackDestory(&ps->Pop);
  StackDestory(&ps->Push);
  free(ps);
  ps = NULL;
}
int main()
{
  MyQueue* q;
  myQueuePush(&q, 1);
  myQueuePush(&q, 2);
  //myQueuePush(&q->Pop, 3);
  while (!myQueueEmpty(&q))
  {
    printf("%d", myQueueFront(&q));
    myQueuePop(&q->Pop);
  }
  myQueueDestory(&q);
  return 0;
}