栈和队列
栈
概念与结构
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。(先进的后出，后进的先出)
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的底层结构选型：链表 or 数组？
使用链表来说，栈顶是经常操作的一端，为了降低时间复杂度，将链表的头看作栈顶，尾看作栈底，入栈的时间复杂度则为O(1),出栈时间复杂度O(1)。
使用数组来说，尾部看作栈顶，头部看作栈顶，入栈、出栈时间复杂度为O(1)。
他们的入栈、出栈操作时间复杂度都一样，但是我们选择数组更好，因为链表是独立的结点，每次操作都要申请一个新的结点，8个字节，空间的消耗更大，所以底层选择数组。所以物理、逻辑结构都是是线性的。
栈的实现
栈的初始化
首先定义栈的结构，然后定义一个初始化函数，因为对形参的改变需要影响实参，所以传址调用，且在函数中用一级指针接收。
头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义栈的结构
typedef int StackDataType;
typedef struct Stack {
StackDataType* arr;
int top; //指向栈顶的位置
int capacity;//栈的容量
}Stack;
//初始化
void StcakInit(Stack* ps);//形参的变化要影响实参，所以要传传址，用一级指针接受
实现文件
#include"Stack.h"
//初始化
void StcakInit(Stack* ps) //ps是形参，形参的初始化要改变实参，所以传址
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
测试文件
#include"Stack.h"
void test01()
{
Stack st;
StackInit(&st);//传址，st是实参
}
int main()
{
test01();
return 0;
}
栈的销毁
//销毁栈
void StackDestroy(Stack* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
判断栈是否为空
bool 函数是一种返回 布尔值（true 或 false） 的函数，通常用于逻辑判断。在 C 语言中，bool 类型需要包含 <stdbool.h> 头文件才能使用。
检查栈是否为空：
如果 ps->top == 0（栈空），返回 true。
否则返回 false。
//判断栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0; //如果 top == 0，返回 true（栈空）；否则返回 false
}
入栈
定义一个入栈的函数，一个保存结构体地址的指针变量，一个需要插入的数据，因为进行了初始化，所以要进行增容，这里需要使用realloc(指向之前分配的内存块的指针，新的内存块大小（字节数）)，然后将新增容的空间和重新分配内存块的大小赋值给原来的capacity和arr。
//插入数据-栈顶入数据
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
//增容
int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;
StackDataType * tmp = (StackDataType*)realloc(ps->arr, newCapacity * sizeof(StackDataType));
if (tmp == NULL)
{
perror("relloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
出栈
因为栈为空返回的是true，所以这里要取反
//出栈-后进的先出，先进的后出
void StackPop(Stack* ps)
{
assert(!StackEmpty(ps));
--ps->top;
}
取栈顶元素
不同于出栈的是不会减少栈中的元素个数
//取栈顶元素
StackDataType* StcakTop(Stack* ps)
{
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
栈中有效元素个数
int StackSize(ST* ps)
{
return ps->top;
}
队列
概念与结构
概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
⼊队列：进⾏插⼊操作的⼀端称为队尾
出队列：进⾏删除操作的⼀端称为队头
队列的底层结构如何选型？
数组：选择最后为队尾时->入队O(1),出队O(N)
选择第一个数据为队尾时->入队O(N),出队O(1)
链表：单链表时，第一个结点为队头，尾结点为队尾时，入队O(N)（因为需要找尾结点），出队O(1)
双向链表时，这时入队，出队的时间复杂度都为O(1)，但是每个结点的空间消耗的太大。
优化单链表：在定义第一个结点的指针为phead的基础上，定义尾结点的指针为ptail，入队时候直接再ptail后面插入结点，这样也入队，出队时间复杂度都为O(1)。
队列的实现
队列结点结构
typedef int QNDataType;
//队列结点的结构
typedef struct QueueNode {
QNDataType data;
struct QueueNode* next;
}QNode;
队列结构
//队列的结构
typedef struct Queue {
QNode* phead;
QNode* ptail;
}Q;
初始化队列
//队列的初始化
void QueueInit(Q* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
}
队列判空
//判空
bool QueueEmpty(Q* pq)
{
assert(pq);
return pq->phead == NULL;
}
销毁队列
pcur从头开始遍历（条件：pcur不为空），然后将pcur的下一个结点存起来。释放pcur，将存起来的结点赋给pcur，最后手动将phead和ptail置空。
//销毁队列
void QueueDestroy(Q* pq)
{
assert(pq);
QNode* pcur = pq->phead;
while(pcur)
{
QNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
//pq->size = 0;
}
入队列，队尾
队列不为空：pq->ptail->next = newnode，然后将pq->ptail = pq->ptail->next
为空的时候：
phead = ptail = newnode
//队尾入数据
void QueuePush(Q* pq, QNDataType x)
{
assert(pq);
//申请结点空间
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else {
pq->ptail->next = newnode;
}
pq->ptail = newnode;
}
出队列，队头
先将phead->next保存下来，然后释放phead，然后phead = phead->next ，只有一个结点（头，尾都指向同一个节点）phead和ptail都需要置空
//队头出数据
void QueuePop(Q* pq)
{
//判空
assert(!QueueEmpty(pq));
//只有一个结点
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else {
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
}
取队头数据
//取队头数据
QNDataType QueueFront(Q* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
取队尾数据
//取队尾数据
QNDataType QueueBack(Q* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
队列有效数据个数
第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景
//队列有效元素个数
int QueueSize(Q* pq)
{
assert(pq);
//第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景
QNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
size++;
pcur = pcur->next;
}
return size;
}
第二种方式：遍历链表——适用于频繁调用队列有效数据个数的场景（完整代码）
//return pq->size;
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QNDataType;
typedef struct QueueNode {
QNDataType data;
struct QueueNode* next;
} QNode;
typedef struct Queue {
QNode* phead;
QNode* ptail;
int size; // 新增：记录队列元素个数
} Q;
void QueueInit(Q* pq);
bool QueueEmpty(const Q* pq);
void QueuePush(Q* pq, QNDataType x);
void QueuePop(Q* pq);
QNDataType QueueFront(const Q* pq);
QNDataType QueueBack(const Q* pq);
int QueueSize(Q* pq); // 新增：O(1) 方式
void QueueDestroy(Q* pq);
#include "Queue.h"
void QueueInit(Q* pq) {
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
bool QueueEmpty(const Q* pq) {
assert(pq);
return pq->size == 0; // 直接判断 size
}
void QueuePush(Q* pq, QNDataType x) {
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL) {
pq->phead = pq->ptail = newnode;
} else {
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++; // 更新 size
}
void QueuePop(Q* pq) {
assert(!QueueEmpty(pq));
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
if (pq->phead == NULL) {
pq->ptail = NULL;
}
pq->size--; // 更新 size
}
QNDataType QueueFront(const Q* pq) {
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QNDataType QueueBack(const Q* pq) {
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize(Q* pq) {
assert(pq);
return pq->size; // O(1) 直接返回
}
void QueueDestroy(Q* pq) {
assert(pq);
QNode* pcur = pq->phead;
while (pcur) {
QNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0; // 重置 size
}