目录
栈
栈的介绍
栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的结构
栈的实现
初始化栈 StackInit
需要用结构体创建一个栈，这个结构体需要包括栈的基本内容（栈，栈顶，栈的容量）。
typedef int STDataType;//栈中存储的元素类型（这里用整型举例）
typedef struct Stack
{
STDataType* a;//栈
int top;//栈顶
int capacity;//容量，方便增容
}Stack;
然后需要一个初始化函数，对刚创建的栈进行初始化。
//初始化栈
void StackInit(Stack* pst)
{
// 使用断言检查输入指针是否有效，确保不为空
assert(pst);
// 动态分配内存，为栈分配空间，初始可存储4个STDataType类型的元素
pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);
// 初始化栈顶指针为0，表示栈当前为空，没有元素
pst->top = 0;
// 设置栈的初始容量为4，即栈目前最多可以容纳4个元素
pst->capacity = 4;
}
销毁栈 StackDestroy
因为栈的内存空间是动态开辟出来的，当我们使用完后必须释放其内存空间，避免内存泄漏。
void StackDestroy(Stack* pst)
{
// 断言检查传入的栈结构体指针是否有效，确保它是指向一个已初始化的栈
assert(pst != NULL);
// 使用 free 函数释放栈中存储元素的数组所占用的内存防止内存泄漏
free(pst->a);
// 将栈的元素数组指针置为 NULL，这是一种安全措施，避免栈被释放后仍被当作有效指针使用
pst->a = NULL;
// 将栈顶指针 top 置为 0，这表示栈内已无任何元素，栈处于空状态
pst->top = 0;
// 将栈的容量 capacity 置为 0，代表栈当前没有存储能力，明确表示栈已经被销毁
pst->capacity = 0;
}
入栈 StackPush
进行入栈操作前，我们需要检测栈的当前状态，若已满，则需要先对其进行增容，然后才能进行入栈操作。
void StackPush(Stack* pst, STDataType x)
{
// 断言检查栈结构体指针是否有效
assert(pst);
// 判断栈是否已满（栈顶索引等于栈的当前容量）
if (pst->top == pst->capacity)
{
// 如果栈满，则尝试重新分配内存，使栈容量翻倍
STDataType* tmp =(STDataType*)realloc(pst->a,sizeof(STDataType)*pst->capacity * 2);
// 检查重新分配内存是否成功
if (tmp == NULL)
{
// 若失败，输出错误信息，并调用 exit 函数结束程序运行
printf("realloc fail\n");
exit(-1);
}
// 若重新分配内存成功，更新栈的元素数组指针和容量
pst->a = tmp;
pst->capacity *= 2;
}
// 将新元素存入栈顶位置
pst->a[pst->top] = x;
// 更新栈顶索引，表示栈顶已移动至新的元素处
pst->top++;
}出栈 StackPop
出栈操作比较简单，即让栈顶的位置向下移动一位即可。但需检测栈是否为空，若为空，则不能进行出栈操作。
void StackPop(Stack* pst)
{
// 断言检查栈结构体指针是否有效
assert(pst);
// 断言检查栈是否为空，若为空则无法弹出元素
assert(!StackEmpty(pst));
// 栈顶指针向下移一位，相当于删除栈顶元素
// 注意：这里假设移除元素后不需要返回其值，且不涉及内存释放
pst->top--;
// 注：在实际应用中，若栈顶元素包含动态分配的内存，此处还需要额外处理释放该内存
}获取栈顶元素 StackTop
获取栈顶元素，即获取栈的最上方的元素。若栈为空，则不能获取。
STDataType StackTop(Stack* pst)
{
// 断言检查栈结构体指针是否有效
assert(pst);
// 断言检查栈是否为空，若为空则无法获取栈顶元素
assert(!StackEmpty(pst));
// 返回栈顶元素的值，栈顶元素的位置是栈顶指针减1
// 注意：此处只读取栈顶元素而不改变栈的状态
return pst->a[pst->top - 1];
}检查栈是否为空 StackEmpty
检测栈是否为空，即判断栈顶的位置是否是0即可。若栈顶是0，则栈为空。
bool StackEmpty(Stack* pst)
{
// 断言检查栈结构体指针是否有效
assert(pst);
// 根据栈顶指针 top 的值判断栈是否为空
// 当栈顶指针为 0 时，表示栈中没有元素，即栈为空
return pst->top == 0;
}获取栈中有效元素个数 StackSize
因为top记录的是栈顶，使用top的值便代表栈中有效元素的个数。
int StackSize(Stack* pst)
{
// 断言检查栈结构体指针是否有效
assert(pst);
// 栈顶指针 top 的值直接表示栈中有效元素的个数
// 因为每当有元素入栈时，top加1；元素出栈时，top减1
// 所以，top的值就反映了当前栈内实际存储了多少个元素
return pst->top;
}队列
队列的介绍
队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列遵守先进先出 FIFO（First In First Out）的原则。
入队列：队列的插入操作叫做入队列，进行插入操作的一端称为队尾。
出队列：队列的删除操作叫做出队列，进行删除操作的一端称为队头。
队列的结构
队列的应用
队列在生活中的运用非常广泛。很大一部分医院、营业厅以及餐厅等场所都存在队列的应用。
例如，医院的采血环节的流程就运用了队列。在医院，如果我们要去抽血，我们首先要在旁边的抽号机抽取自己的编号，当某一个抽血窗口叫到你时，你便可以去抽血了。
在这个过程中，当你在抽号机抽取到某一个编号，那么这个编号这时就从队尾入队列，当某一窗口抽血结束后，会在该队列中拿走一个编号并叫该编号的人到这个窗口接受抽血，那么这时这个编号就从队头出队列。
队列的实现
首先我们需要创建一个结点类型，类型包含了该结点的数据和指向下一结点的指针。
typedef int QDataType;
typedef struct QListNode
{
// 指向下一个节点的指针
struct QListNode* next;
// 节点所存储的数据
QDataType data;
} QListNode;队列与普通链表又有所不同，普通链表只需要知道链表的头指针，而队列的信息包括了队头和队尾，所以我们需要再创建一个结构体用于存放队列的队头和队尾。
typedef struct Queue
{
// 队列头指针
// 指向队列的第一个节点，当队列为空时，head 和 tail 都指向 NULL
QListNode* head;
// 队列尾指针
// 指向队列的最后一个节点，每次有新元素入队时，都会更新 tail 指针
QListNode* tail;
} Queue;初始化队列 QueueInit
然后需要一个初始化函数，对刚创建的队列进行初始化。
void QueueInit(Queue* pq)
{
// 断言检查传入的队列结构体指针是否有效
assert(pq);
// 将队列的头指针 head 初始化为 NULL，表示队列当前为空，无元素
pq->head = NULL;
// 将队列的尾指针 tail 也初始化为 NULL，与 head 一致，表示队列为空
// 这样设计的原因是，在队列为空时，头尾指针均指向 NULL；而在有元素入队时，tail 指针将指向最后一个元素
pq->tail = NULL;
}销毁队列 QueueDestroy
队列中的每一个结点所占用的内存空间都是动态开辟的，当我们使用完队列后需要及时释放队列中的每一个结点。
void QueueDestroy(Queue* pq)
{
// 断言检查传入的队列结构体指针是否有效
assert(pq);
// 创建一个临时指针 cur，初始化为队列的头节点
QListNode* cur = pq->head;
// 循环遍历队列中的每一个节点
while (cur)
{
// 将 cur 的下一个节点赋值给临时指针 next，保存下一个节点的地址
QListNode* next = cur->next;
// 释放当前节点 cur 的内存
free(cur);
// 移动 cur 指针至下一个节点
cur = next;
}
// 清空队列的头指针和尾指针，将它们都设置为 NULL
pq->head = NULL;
pq->tail = NULL;
}队尾入队列 QueuePush
入队列，即申请一个新结点并将其链接到队尾，然后改变队尾的指针指向即可。需要注意的是：若队列中原本无数据，那么我们只需让队头和队尾均指向这个新申请的结点即可。
void QueuePush(Queue* pq, QDataType x)
{
// 断言检查队列结构体指针是否有效
assert(pq);
// 分配内存创建一个新的节点
QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
// 检查内存分配是否成功
if (newnode == NULL)
{
// 若内存分配失败，输出错误信息并退出程序
printf("malloc fail\n");
exit(-1);
}
// 将新节点的数据域设置为要插入的元素值 x
newnode->data = x;
// 新节点的下一节点指针初始化为 NULL
newnode->next = NULL;
// 判断队列是否为空
if (pq->head == NULL)
{
// 若队列为空，则新节点既是头节点也是尾节点
pq->head = pq->tail = newnode;
}
else
{
// 若队列非空，将现有尾节点的下一节点指向新节点
pq->tail->next = newnode;
// 更新队列尾指针，使之指向新插入的节点
pq->tail = newnode;
}
}队头出队列 QueuePop
出队列，即释放队头指针指向的结点并改变队头指针的指向即可。若队列中只有一个结点，那么直接将该结点释放，然后将队头和队尾置空即可。
void QueuePop(Queue* pq)
{
// 断言检查队列结构体指针是否有效
assert(pq);
// 断言检查队列是否为空，若为空则不能进行出队操作
assert(!QueueEmpty(pq));
// 判断队列中剩余元素数量
if (pq->head->next == NULL)
{
// 如果队列只剩一个元素，则释放该元素，并将头尾指针都设为 NULL
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
// 如果队列中还有多个元素，则释放头节点，然后将头指针指向下一个节点
QListNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}获取队列头部元素 QueueFront
获取队列头部元素，即返回队头指针指向的数据即可。
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;
}检查队列是否为空 QueueEmpty
检测队列是否为空，即判断队头指针指向的内容是否为空。
bool QueueEmpty(Queue* pq)
{
// 断言检查队列结构体指针是否有效
assert(pq);
// 判断队列是否为空的条件是：头指针（pq->head）是否为 NULL
// 如果头指针为 NULL，则队列为空，返回 true
// 否则，队列非空，返回 false
return pq->head == NULL;
}获取队列中有效元素个数 QueueSize
队列中有效元素个数，即队列中的结点个数。我们只需遍历队列，统计队列中的结点数并返回即可。
int QueueSize(Queue* pq)
{
// 断言检查队列结构体指针是否有效
assert(pq);
// 初始化计数器 count 为 0
int count = 0;
// 创建一个临时指针 cur，初始化为队列的头节点
QListNode* cur = pq->head;
// 遍历队列，直到 cur 为空（即遍历完队列）
while (cur)
{
// 计数器加一，表示找到了一个有效节点
count++;
// 将 cur 指针移向下一个节点
cur = cur->next;
}
// 返回计数器 count 的值，即队列中有效元素的个数
return count;
}
