栈
分析
栈的数据是栈顶进，栈顶出。
我们用数组和链表都可以，但是链表因为尾插和尾删没有数组方便，所以我们用数组。
例子：如果进去的顺序是1234，出来的顺序就是4321。
我们可以用一个数组来储存数据，然后再定义一个指针指向栈顶的数据，方便出栈和入栈。
typedef int SD;//随时更改数据类型 typedef struct stack { SD* a;//数组 int top;//栈顶的后一个位置 int capacity;//容量 }ST;
这里用指针定义的数组，后面我们可以用扩容增加容量，这样就变成了一个数组。
初始化与销毁栈
一定要初始化空间，不然容易造成野指针的问题。
初始化
void StackInit(ST* ps)//初始化 { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; }
初始化就不开辟空间了。
销毁栈
这里和链表不一样，比较方便，释放掉起始地址就好了。
void StackDestroy(ST* ps)//销毁栈 { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; }
出栈入栈与判断栈为空
入栈
void StackPush(ST* ps, SD x)//入栈 { assert(ps); //扩容 if (ps->capacity == ps->top)//判断是否需要扩容 { int count = (ps->capacity == 0 ? ps->capacity = 4 : ps->capacity * 2);//第一次扩容4个，之后的扩容的容量二倍增加 SD* y = (SD*)realloc(ps->a, count * sizeof(SD)); if (y == NULL) { perror("realloc fail"); exit(-1); } ps->a = y; ps->capacity = count; } ps->a[ps->top] = x;//赋值 ps->top++; }
例：
此时的top是4.
判断栈是否为空
bool StackEmpty(ST* ps)//判断 { assert(ps); return ps->top == 0;//如果为空就返回1，不为空返回0 }
出栈
void StackPop(ST* ps)//出栈 { assert(ps); assert(!StackEmpty(ps)); ps->top--; }
出栈就很简单了，因为top是末尾的数据，如果想再入栈，入栈的地方是top指向的地方，会覆盖掉原来的数据。
获取栈顶元素
SD StackTop(ST* ps)//获取栈顶元素 { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
获取栈中有效元素个数
top也就等于栈中数据的数量。
int StackSize(ST* ps)//获取栈中有效的元素 { assert(ps); return ps->top; }
队列
分析
队列是从队头出，队尾入，数组就没有链表好用了，所以我们用单向链表。
结点
typedef int SD; typedef struct QListNode { struct QListNode* next; SD data; }QL;
因为我们需要的是头删尾插，所以不仅仅需要头结点，还需要一个尾结点，这样更方便操作。
typedef struct Queue { QL* head;//头结点，指向队列的队头 QL* tail;//尾结点，指向队列的队尾 int siz;//计算有多少个结点 }Qu;
初始化与销毁队列
初始化
头结点和尾结点的指向空即可，siz初始化为0用来记录结点数量。
void QueueInit(Qu* q)//初始化 { assert(q); q->head = q->tail = NULL; q->siz = 0; }
销毁队列
void QueueDestroy(Qu* q)//销毁队列 { assert(q); QL* cur = q->head;//这里要注意数据类型 while (cur) { QL* del = cur -> next; free(cur); cur = del; } q->head = q->tail = NULL; q->siz = 0; }
入列，出列与判断队列是否为空
入列
这里需要考虑队列是否为空的尾插。
void QueuePush(Qu* q, SD x)//入队 { assert(q); QL* w = (QL*)malloc(sizeof(QL));//新开辟结点 if (w == NULL) { perror("malloc tail"); exit(-1); } else { w->data = x; w->next = NULL; } if (q->head == NULL)//如果队列为空 { q->head = q->tail = w; } else//如果队列不为空 { q->tail->next = w; q->tail = w; } q->siz++; }
判断
不为空返回0，为空返回非零。
bool QueueEmpty(Qu* q)//判断 { assert(q); return q->head == NULL; }
出列
这里就是典型的头删了，只不过需要注意的是，tail是不会在这个函数中移动的，所以当释放掉tail指向的结点时，要把tail置为空，不然会成为野指针。
void QueuePop(Qu* q)//出队 { assert(q); assert(!QueueEmpty(q)); if (q->head == NULL)//防止tail成为野指针 { free(q->head); q->head = q->tail = NULL; } QL* cur = q->head; q->head = q->head->next; free(cur); cur = NULL; q->siz--; }
获取队列头部，尾部元素
这里就体现了head和tail的好处。
头部
SD QueueFront(Qu* q)//获取队头元素 { assert(q); assert(!QueueEmpty(q)); return q->head->data; }
尾部
SD QueueBack(Qu* q)//获取队尾元素 { assert(q); assert(!QueueEmpty(q)); return q->tail->data; }
获取队列中有效元素个数
直接返回之前用于记录数量的siz就可以了。
int QueueSize(Qu* q)//获取队列中有效元素个数 { assert(q); return q->siz; }
