栈
栈的概念及其结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。 栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。所以也有被称为后进先出的顺序结构。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的顺序结构（杯子）
~~就像上述图片一样，像个”杯子“，只能从上面进出，后进先出；栈底是固定的，无法插入于删除。
栈的相关接口
我们来到cplusplus这个网站，查找库中的栈的接口。（这里我们只讲解C语言的哈，C++涉及的emplace和swap就暂不讲解）
栈的实现
栈，我们可以用顺序表实现，也可以用链表实现，各有各的优势，接下来我们就具体用C语言代码来实现下顺序栈和链栈。
顺序栈
顺序栈，也就是用顺序表来实现，顺序表也就是用了数组这一结构。动态内存管理，开辟一个空间大小固定的数组（当然可以扩容）。这一结构地址相连，方便访问。接下来我们先定义一个栈。
定义栈结构：
定义栈分为三部分：动态开辟数组（a）、top下标、容量（capacity）
typedef int STDataType; //栈的定义 typedef struct Stack { STDataType* a; int top; int capacity; }S;
头文件 (Stack.h)
我们进行一个简单的分装，把库头文件、接口函数声明、结构体定义封装到头文件中。
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //定义初始空间大小 #define A_INIT 2 //定义栈元素类型：这里是为了我们的栈更兼容其他类型元素，比如我们现在想变为存储double的栈，只需要在这里把int改成double就可以。 typedef int STDataType; //栈的定义 typedef struct Stack { STDataType* a; int top; int capacity; }S; //初始化栈 void StackInit(S* stack); //栈的销毁 void StackDestroy(S* stack); //压栈 void StackPush(S* stack, STDataType x); //出栈 void StackPop(S* stack); //读取栈顶元素 STDataType StackTop(S* stack); //判断是否空栈 bool StackEmpty(S* stack); //栈的元素个数 int StackSize(S* stack);
初始化 (StackInit)
初始化：我们根据栈结构来初始化，所以也分为三部分：
1.对a，进行空间开辟，用malloc来开辟空间。
2.容量（便于后续扩容操作）
3.top下标。这里我们有两种主流的：初始化为0或者初始化为-1.
（ps：初始化为0，则表示top指向的是栈顶上一个元素，我们访问的时候就需要-1；初始化为-1，则表示top指针指向栈顶元素，直接访问即可。这里我便是采用初始化为-1）
void StackInit(S* stack) { assert(stack);//断言 stack->a = (STDataType*)malloc(sizeof(STDataType) * A_INIT); stack->capacity = A_INIT; stack->top = -1; }
销毁 (StackDestroy)
同上，根据定义来，malloc的动态空间，调用free()函数来释放空间，以防内存泄漏。
void StackDestroy(S* stack) { free(stack->a); stack->a = NULL; stack->capacity = 0; stack->top = -1; }
压栈 (StackPush)
- 压栈：只需要把top指针上移，赋值新插入元素即可，也就是对应最后两段代码。
- ps：但我们插入要考虑我们开辟的容量问题，当容量空间不够我们需要扩容操作。
- 扩容：调用realloc函数进行空间的扩容。这里也有两个问题:原地扩容和异地扩容，这个详细我们在realloc函数那篇解释。这里影响并不是很大。
void StackPush(S* stack, STDataType x) { //扩容 assert(stack); if (stack->top + 1 == stack->capacity) { STDataType* tmp = (STDataType*)realloc(stack->a, sizeof(STDataType) * 2 * stack->capacity); if (tmp == NULL)//判断是否扩容成功 { perror("realloc error"); return; } stack->a = tmp; stack->capacity = 2 * stack->capacity; } stack->top++; stack->a[stack->top] = x; }
出栈(StackPop)
出栈就十分简单，先判断是否为空栈，若不是，只需要收回栈顶访问权，让栈顶指针指向下一个位置。
void StackPop(S* stack) { assert(stack); assert(stack->top != -1); stack->top--; }
读取栈顶元素 (StackTop)
这里值得注意的是top的初始化是0还是-1问题。
STDataType StackTop(S* stack) { assert(stack); assert(stack->top + 1 != 0); return stack->a[stack->top]; }
判断空栈(StackEmpty)
判断栈顶top是否为默认初始值即可。
bool StackEmpty(S* stack) { assert(stack); return stack->top == -1; }
栈元素个数(StackSize)
这里也是需要注意top初始值问题。
int StackSize(S* stack) { assert(stack); return stack->top+1; }
队列
队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)像个管道只允许一个数据通过，所以不能插队，先进先出。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列的相关接口
我们同样登录cplusplus网站去看下Queue的接口。
队列的实现
队列的定义：
队列的定义我们采用链表来定义，这里队列整体存在两个指针，和前面的双向循环的链表一样，我们最好把两个外部指针封装一下。
1.队列单独结点的定义有值和next指针。
2.队列整体的话有两个指向队列单独结点的head和tail指针，为了方便我这边也定义了size来定义队列结点个数。
typedef int Datatype; //定义队列 typedef struct Queue { struct Queue* next; Datatype data; }qnode; typedef struct { qnode* head; qnode* tail; int size; }queue;
头文件（Queue.h）
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int Datatype; //定义队列 typedef struct Queue { struct Queue* next; Datatype data; }qnode; typedef struct { qnode* head; qnode* tail; int size; }queue; void QueueInit(queue* pq); void QueueDestroy(queue* pa); void QueuePush(queue* pq, Datatype x); void QueuePop(queue* pq); bool QueueEmpty(queue* pq); int QueueSize(queue* pq); Datatype QueueFront(queue* pq); Datatype QueueBack(queue* pq);
初始化（QueueInit）
队列的初始化，因为没有结点，直接初始化外部指针即可。
void QueueInit(queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; }
销毁（QueueDestroy）
遍历指针，在释放即可。
void QueueDestroy(queue* pq) { assert(pq); qnode* cur = pq->head; while (cur) { qnode* next = cur->next; free(cur); cur = next; } pq->head = NULL; pq->tail = NULL; }
入队列（QueuePush）
入队列先进先出，单道通行。
1.首先是申请结点空间，然后赋值。
2.如果是队列为空，直接给head和tail指针赋值新节点地址；如果不为空，就赋值给tail的next指针。接在后方。
3.最后size计数，加加即可。
void QueuePush(queue* pq, Datatype x) { qnode* node = (qnode*)malloc(sizeof(qnode)); if (node == NULL) { perror("malloc error!"); return; } node->next = NULL; node->data = x; if (pq->head == NULL) { pq->head = pq->tail = node; } else { pq->tail->next = node; pq->tail = node; } pq->size++; }
出队列（QueuePop）
出队列先入先出
1.注意断言队列是否为空。
2.若队列只有一个结点，直接释放，双指针置空即可；若队列不止一个结点，保存head的next指针，释放head指针，在head指针赋值新的head位置。
3.最后size减减即可。
void QueuePop(queue* 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--; }
判断队列是否为空（QueueEmpty）
bool QueueEmpty(queue* pq) { assert(pq); return pq->head == NULL; }
返回队列的结点个数（QueueSize）
这里直接返回size即可，若前方定义没有加size，就需要遍历计数返回。
int QueueSize(queue* pq) { assert(pq); return pq->size; }
队列首结点（QueueFront）
Datatype QueueFront(queue* pq) { assert(pq); return pq->head->data; }
队列尾结点（QueueBack）
Datatype QueueBack(queue* pq) { assert(pq); return pq->tail->data; }
