//静态栈结构 - 很不实用
typedef int STDataType;
#define N 10
typedef struct Stack
{
  STDataType _a[N];
  int _top; // 栈顶
}Stack;
//动态栈结构
typedef int STDataType;
typedef struct Stack
{
  STDataType* array;
  int top;//这代表我们栈顶的位置，top会随着栈空间数据的扩大随之变换
  int capacity;
}ST;

void StackInit(ST* ps)
{
  assert(ps);
  ps->array = NULL;
  ps->top = 0;//ps->top = -1; 我们的top也是可以给-1的
  ps->capacity = 0; 
  //初始化时，top给的是0，意味着top指向栈顶数据的下一个
//我们的top指向的是最后栈顶数据的下一个，因为我们是先插入数据到下标为top的位置，然后top再++
  //初始化时，top给的是-1，意味着top指向栈顶数据
//我们的top指向的是栈顶数据，因为我们要先将top+1，然后再往此时的top位置放数据，下一次也是先将top位置+1再放数据
//这是一个什么问题呢？(就是)是先放数据再移动top呢？还是先移动top再放数据呢？
}

void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->array);
  ps->array = NULL;
  ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)//将元素进行入栈
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->array, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->array = tmp;
    ps->capacity = newCapacity;
  }
  ps->array[ps->top] = x; 
  ps->top++;
}

void StackPop(ST* ps)//将元素进行出栈，删除数据
{
  assert(ps);
  assert(!StackEmpty(ps));//top为0的时候是不能进行删除的
  ps->top--;
}

bool StackEmpty(ST* ps)
{
  assert(ps);
  /*if (ps->top > 0)
  {
    return false;
  }
  else
  {
    return true;
  }*/
  return ps->top == 0;//这里的判断条件的正确与否，正好就对应上我们返回的是逻辑真还是逻辑假。true or false
}

STDataType StackTop(ST* ps)//取栈顶的数据
{
  assert(ps);
  assert(!StackEmpty(ps));//如果栈为空，就会报错
  //我们的栈必须得有数据你才能取数据啊，如果没有数据你还取数据的话，就是访问下标-1的数据了，造成越界访问
  return ps->array[ps->top - 1];
}

int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;//top指向的是栈顶数据的下一个位置，又因为它从0开始增大，所以top的值正好就是栈数据的个数
}

#include "Stack.h"
void TestStack()
{
  ST st;
//1.用我们的结构体类型定义了一个结构体，结构体里面的array指针会指向我们动态开辟的数组栈，用于维护我们的数组栈
//2.我们其实实现的也是动态的数组栈，如果要实现静态的数组栈的话，我们还需在结构体里面定义定长数组，这非常的不方便
//跟个傻瓜一样，太低级了，所以我们选择柔性数组也就是用指针来维护我们的动态数组栈的方式实现，这还是比前者要高级的。
  StackInit(&st);
  //(&st)->array;值得注意的是，我们有时候也不必去创建一个结构体类型的指针来访问结构体成员，可以通过结构体变量本身的地址来
//访问其内部的成员，有意思哈。
  StackPush(&st, 1);
  StackPush(&st, 2);
  StackPush(&st, 3);
  StackPush(&st, 4);
  printf("%d ", StackTop(&st));
  StackPop(&st);
  printf("%d ", StackTop(&st));
  StackPop(&st);
  StackPush(&st, 5);
  StackPush(&st, 6);
  StackPush(&st, 7); 
  while (!StackEmpty(&st))
  {
    printf("%d ", StackTop(&st));
    StackPop(&st);
  }
  //入栈1234出栈4321
  StackDestroy(&st);//如果我们不destroy的话，就会造成内存泄漏。
}
int main()
{
  TestStack();
  return 0;
}

typedef int QDataType;
typedef struct QueueNode//队列结构中的每一个结点
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue//我们的队列结构
{
  QueueNode* head;
  QueueNode* tail;
//这里我们其实也可以将这两个队列结点指针单独定义出来，但是这样不太符合代码的主流风格，所以我们将他们包到一个结构体里。
}Queue;
//单链表那里，我们是单独将单链表的头指针拎出来，独立于结点结构体定义的，这里我们是将两个指针合在一起定义到一个
//队列结构里面

void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}

bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

void QueueDestroy(Queue* pq)//销毁队列
{
  assert(pq);//head和tail可以为空，但我们的队列结构肯定不可以为空，如果队列结构都为空了，那肯定是我们传的参数出了问题
  QueueNode* cur = pq->head;
  //while (cur != pq->tail)
  //{
  //  //我们这里进行释放队列结点
  //  //但这种逻辑其实有问题，因为你最后一个队列结点的空间是没有进行删除的，会造成内存泄漏。
  //}
  while (cur != NULL)//当我们的cur走到NULL时，正好说明队列结点空间已经释放完毕了
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
  //这里我们要分两种情况
  //1.我们的tail和head都是正常的，然后我们直接在tail后面插入队列结点，这就相当于我们的入队列，然后再更新一下tail的位置。
  //2.如果我们的tail和head都为空的话，我们直接将新的队列结点的地址赋值给我们的head和tail，此刻我们的尾和头所指位置是相同的
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;//将我们队列结点初始化
  if (pq->head == NULL) 
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}

QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//断言为假，程序就会崩
  return pq->head->data;
}

int QueueSize(Queue* pq)//我们也可以在队列结构体定义那里加一个成员size_t _size，我们push它就++，pop它就--。
{
  assert(pq);
  QueueNode* cur = pq->head;
  int i = 0;
  while (cur)
  {
    i++;
    cur = cur->next;
  }
  return i;
}