顶峰相见！
大家好，我是纪宁。这篇文章给大家介绍栈和队列，以及详细的实现个过程 。
1.栈
1.1 栈的概念及结构
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
1.2 栈的实现
栈一般可以用链表或者顺序表（数组实现），相对于链表，数组实现效率更优。
数组实现栈，尾插尾删
实现栈的标识索引
| STDataType | 重命名后的栈内数据类型 |
| Stack | 栈的结点结构 |
| STInit | 栈的初始化 |
| STpush | 入栈（压栈） |
| STPop | 出栈 |
| STTop | 获取栈顶元素 |
| STDestroy | 栈的销毁 |
| STSize | 求栈元素个数 |
| STEmpty | 判空（判断栈空间是否为空） |
数组实现栈
由于我们是用数组实现栈的，所以要先选择使用静态数组还是动态数组，由于静态数组的可用性较低，这里采用动态数组。
栈的结构定义
将栈空间元素数据类型重命名为 STDataType ，这样在改变栈的数据类型后，数据结构依然可以使用；a 为栈空间的首地址，top 为栈顶位置，出栈就相当于尾删，栈顶位置前移，入栈相当于尾插。
栈空间数据的初始化和销毁
将栈空间的指针指向初始化为 NULL，栈顶的下一个位置 top 为下标 0 ，栈空间大小初始化为 0。
销毁栈空间，将开辟的空间释放，并让指针指向空；将栈空间的栈顶的下一个位置 top 和 占空间容量置空。
入栈和出栈
入栈即将数据尾插在实现栈的数组后面，当栈顶的下一个位置下标 top 与栈空间大小相同时，说明栈空间已经满了，需要扩容；当第一次入栈时，栈空间本来就初始化为 0，因此第一次入栈要扩容（由0扩容到一个值，这个值可以自己定），用三目运算符来控制第一次和第N次扩容的不同：第一次扩容到固定值，第N次则扩容到原空间的 2 倍。
需要强调的是 realloc 函数在空间大小为 0 的时候作用于 malloc 函数相同。扩容/开辟空间后，栈空间的指针指向新开辟/扩容后的地址；栈的容量大小改为扩容后的大小；top 位置的元素改为入栈元素，再将 top 后移。
出栈的时候，要先断言栈中是否有元素你，没有元素才能出栈。
获取栈顶元素、计算栈空间元素个数、判空
先断言，首先保证栈中有元素。由于 top 是栈顶的下一个位置的下标，那么就但会 top-1 位置的元素，就是栈顶元素。
由于 top 是栈顶的下一个位置的下标，而下标是从 0 开始的，因此 top 的值与栈内元素的个数相等。
当 top 等于0时，说明栈顶元素的下一个位置下标为0，那么栈中就没有元素，栈为空。
2.队列
2.1 队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出。FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
2.2 链表的实现
栈可以使用数组和链表两种方式实现，但由于队列的性质是先进先出，先出要进行头删，数组头删要将所有元素移动，效率较低，所以这里采用链表实现队列。
用链表实现队列：入队尾插，出队头删
实现链表的标识索引
| QDataType | 重命名后的队列元素数据类型 |
| QueueNode | 队列的结点结构 |
Queue |
结点和size的结合结构 |
| QueueInit | 队列的初始化 |
| QueueDestroy | 队列的销毁 |
| QueuePush | 入队 |
| QueuePop | 出队 |
| QueueFront | 获取队头元素 |
| QueueBack | 获取队尾元素 |
| QueueEmpty | 队列判空 |
| QueueSize | 获取队列元素个数 |
链表实现队列
定义队列的相关结构
正常定义一个单链表的结构，但由于要进行头删、尾插，定义一个指针 tail，用来指向尾结点，为了不使用二级指针，再多定义一个结构体，存储链表头指针、尾指针，顺便存储队列的元素个数。
队列的初始化和销毁
队列的初始化就是将队列的链表头指针和尾指针都置空，元素个数置空。由于队列是由链表定义的，所以销毁的时候要释放每次开辟的结点空间，定义一个 cur 指针来负则遍历。将所有空间都释放后，将链表头指针和尾指针置空，元素个数改为 0。
入队、出队
入队
入队的时候，因为是链表，所以要先开辟一个结点的空间，然后改链表指向。当队列中没有数据时，要单独处理，将链表头指针和尾指针都指向新节点。
出队
链表出队列的要判断的东西比较多。首先得判断是否有数据，还要判断是否只有一个数据，当只要一个数据的时候，释放掉空间后，tail 指针和 head 指针都要置空。当有多个数据时，只需要将头指针后移即可。
最后，将元素个数减1。
队列判空和数据个数计算
队列判空只需要判断头指针是否为空即可，而元素个数在每次入队或出队的时候都进行了改变，只需要返回即可。
获取队头和队尾元素
直接返回即可，唯一要注意的就是必须保证队列里有元素，因此需要断言队列是否为空。
3.源码
3.1 数组实现栈
Stack.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top;//栈顶位置 int capacity;//栈空间大小 }ST; void STInit(ST* ps); void STPush(ST* ps,STDataType x); void STPrint(ST* ps); void STPop(ST* ps); void STDestroy(ST* ps); STDataType STTop(ST* ps); int STSize(ST* ps); bool STEmpty(ST* ps);
Stack.c
#include "Stack.h" void STInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } void STPush(ST* ps, STDataType x) { assert(ps); if (ps->capacity==ps->top) { int newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(ps->a)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->capacity = newcapacity; ps->a = tmp; } ps->a[ps->top] = x; ps->top++; } void STPrint(ST* ps) { assert(ps); int i = 0; for (i = 0; i < ps->top; i++) { printf("%d ", ps->a[i]); } printf("\n"); } void STPop(ST* ps) { assert(ps); assert(ps->top>0); (ps->top)--; } void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } STDataType STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } int STSize(ST* ps) { assert(ps); return ps->top; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }
3.2 链表实现队列
Queue.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { QDataType Data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Que; void QueueInit(Que* pq); void QueueDestroy(Que* pq); void QueuePush(Que* pq,QDataType x); void QueuePop(Que* pq); QDataType QueueFront(Que* pq); QDataType QueueBack(Que* pq); int QueueSize(Que* pq); bool QueueEmpty(Que* pq);
Queue.c
#include "Queue.h" void QueueInit(Que* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->tail =pq->head= NULL; pq->size = 0; } void QueuePush(Que* pq,QDataType x) { assert(pq); QNode* nownode = (QNode*)malloc(sizeof(QNode)); if (nownode == NULL) { perror("malloc fail"); exit(-1); } nownode->Data = x; nownode->next = NULL; if (pq->head = NULL) { pq->head = pq->tail = nownode; } else { pq->tail->next = nownode; pq->tail = nownode; } pq->size++; } void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next==NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->Data; } QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->Data; } bool QueueEmpty(Que* pq) { assert(pq); return pq->head == NULL; } int QueueSize(Que* pq) { assert(pq); return pq->size; }
