目录
栈（Stack）
栈的结构体
初始化
销毁
入栈
判空
出栈
取栈顶元素
获取栈个数
测试：
队列（Queue）
队列的结构体
单个结点
队列
初始化
销毁
入队列，队尾
判空
出队列，队头
取队头数据
取队尾数据（非标准操作）
获取队列个数
测试：
栈（Stack）
栈是一种特殊的线性表，其只允许在特定的一端进行插入和删除操作。
进行插入和删除操作的一端叫做栈顶
另一端称为栈底
栈中的数据元素遵循后进先出LIFO（Last In First Out ）的原则
压栈：栈的插入操作也被称为进栈、入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
因为栈只在一端进行操作，所以栈的实现使用数组更加优越。
栈的结构体
//重命名，方便统一修改
typedef int STDataType;typedef struct stack {STDataType* arr;int capacity;//栈的容量int top;//栈顶位置（有效元素个数）
}ST;
初始化
//初始化
void STInit(ST* ps) {assert(ps);//不能传入NULLps->arr = NULL;ps->capacity = ps->top = 0;
}
销毁
//销毁
void STDestory(ST* ps) {assert(ps);//不能传入NULLif (ps->arr) {//防止对NULL指针的引用（即栈为空的情况）free(ps->arr);}ps->arr = NULL;ps->capacity = 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;//若栈容量为0，给定初始值，否则以两倍大小增长STDataType* p = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (!p) {//申请失败，直接返回perror("realloc fail!");exit(1);}ps->arr = p;ps->capacity = newcapacity;//改变原容量大小}ps->arr[ps->top++] = x;//先给栈顶赋值，在加加
}
判空
//判空
bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;//返回bool值，直接返回比较运算符的返回值
}出栈
//出栈
void STPop(ST* ps) {assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空ps->top--;//出栈,让栈顶减减
}
取栈顶元素
//取栈顶元素
STDataType STTop(ST* ps) {assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空return ps->arr[ps->top - 1];//返回栈顶元素，让栈顶减减
}
获取栈个数
//获取栈有多少元素
int STSize(ST* ps) {assert(ps);return ps->top;//直接返回栈顶下标（即元素个数）
}测试：
队列（Queue）
队列也是一种特殊的线性表，其在一端进行插入操作，另一端进行删除操作。
进行插入操作的一端叫做队尾（rear）。
进行删除操作的一端叫做队头（front）。
队列中的数据元素遵循后进先出FIFO（Frist In First Out ）的原则
入队：队列的插入操作，一般发生在队尾
出队：队列的删除操作，一般发生在队头
因为队列在头部删除数据，使用数组，移动数据的时间复杂比较高，所以使用链表更优越。
队列的结构体
单个结点
//重命名，方便统一修改
typedef int QDataType;//队列单个结点结构
typedef struct QueueNode {QDataType data;//数据struct QueueNode* next;//下一个结点
}QN;队列
//队列结构
typedef struct queue {QN* front;//队头QN* rear;//队尾int size;//结点数
}Q;初始化
//初始化队列
void QueueInit(Q* pq) {assert(pq);pq->front = pq->rear = NULL;pq->size = 0;
}
销毁
//销毁
void QueueDestory(Q* pq) {assert(pq);assert(!QueueEmpty(pq));//队列为空，不用销毁QN* pcur = pq->front;while (pcur) {QN* next = pcur->next;free(pcur);//依次释放每一个结点pcur= next;}pq->rear = pq->front = NULL;//置队头队尾pq->size = 0;
}入队列，队尾
//入队列，队尾
void QueuePush(Q* pq, QDataType x) {assert(pq);QN* node = (QN*)malloc(sizeof(QN));//开辟一个新结点if (!node) {//防止为空perror("malloc fail!");exit(1);}node->data = x;//data元素node->next = NULL;//next指针if (pq->front == NULL) {//若队列为空，队头队尾都要改变pq->front = pq->rear = node;}else {//若不为空,则改变尾结点指向pq->rear->next = node;pq->rear = node;}pq->size++;//队列元素++
}判空
//判空
bool QueueEmpty(Q* pq) {assert(pq);return pq->size == 0;
}出队列，队头
//出队列，队头
void QueuePop(Q* pq) {assert(pq);assert(!QueueEmpty(pq));//不能为空if (pq->front->next == NULL) {//若只有一个元素，队尾的指向也要发生改变free(pq->front);pq->front = pq->rear = NULL;}else {//若有多个元素，只用改变队头指向QN* del = pq->front;pq->front = pq->front->next;free(del);del = NULL;}pq->size--;
}取队头数据
//取队头数据
QDataType QueueFront(Q* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->front->data;
}取队尾数据（非标准操作）
//取队尾数据
QDataType QueueRear(Q* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->rear->data;
}获取队列个数
//队列有效个数
int QueueSize(Q* pq) {assert(pq);return pq->size;
}测试：
