前言
本章主要讲解：
数据结构中的栈和队列的知识以及如何实现
栈
- 概念及结构
栈，一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作
进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底
栈中的数据元素遵守后进先出 LIFO （ Last In First Out ）的原则
数据处理方式：
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶
- 图示：
栈的实现
栈的实现一般可以使用数组或者链表实现
相对而言数组的结构实现更优一些（数组在尾上插入数据的代价比较小）
图示：数组栈
接口展示
注：定长的静态栈实际中不实用，所以我们主要实现支持动态增长的数组栈
// 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
栈结构创建
动态数组栈具有三个元素：数组指针（指向开辟的空间），栈顶位置，栈的长度
参考代码：
//栈类型结构 typedef struct Stack { //数组栈（指向数组的指针） STDataType* a; //栈顶位置 int top; //栈容量（数组长度） int capacity; }ST;
栈的初始化
- 注意：
- 栈顶的表示的位置需要考虑好
参考代码：
//栈初始化 void StackInit(ST* ps) { //避免传入空指针 assert(ps); ps->a = NULL; ps->top = 0;//定义top为栈最后数据的后一个位置 //也可以选择让top为当前最后数据的位置 则初始化top=-1; ps->capacity = 0; return; }
栈的销毁
注：动态开辟的空间结束时也需要进行销毁（避免内存泄漏）
- 参考代码：
//栈销毁 void StackDestroy(ST* ps) { //避免传入空指针 assert(ps); free(ps->a);//释放开辟的数组栈空间 ps->a = NULL;//置空，避免造成野指针 }
入栈
- 注意：
- 入栈考虑是否栈满，栈满则进行扩展栈长度
- 入栈成功更新栈顶位置
参考代码：
//入栈 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//栈满的情况 { //如果原来容量为0则让新容量为4，否则为两倍 int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //调整数组栈大小（特别的：当数组指针为NULL时，realloc的作用和malloc的作用一样） STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity); if (tmp == NULL)//tmp为NULL时则表示调整数组空间失败，那么就打印错误并结束进程 { perror("realloc fail:"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x;//存入数据 ps->top++;//top位置更新 return; }
出栈
- 注意：
- 对于空栈不能再进行出栈
- 栈顶位置减减实现出栈的效果
参考代码：
//出栈 void StackPop(ST* ps) { //避免传入空指针 assert(ps); //出栈到数据个数为0结束 if (StackEmpty(ps)) return; ps->top--;//让top减减得到出栈的效果 return; }
注：这里我们封装了一个判断空栈的函数便于调用
空栈判断
注：C语言没有定义bool类型（C99之前），要在C里面使用需要包含头文件 <stdbool.h>
- 参考代码：
//是否为空栈 bool StackEmpty(ST* ps) { //避免传入空指针 assert(ps); return ps->top == 0; }
栈顶数据获取
- 注意：
- 空栈时无法获取数据
注：这采用比较暴力的方式（断言），当然也可以选择if条件判断（比较温柔）
- 参考代码：
//获取栈顶数据 STDataType StackTop(ST* ps) { //避免传入空指针 assert(ps); //空栈（top-1会越界访问） assert(!StackEmpty(ps));//暴力断言不为空栈 return ps->a[ps->top - 1];//这里top-1才是栈顶数据的下标 }
栈存入数据个数
- 参考代码：
//栈使用大小（存入数据个数） int StackSize(ST* ps) { //避免传入空指针 assert(ps); return ps->top; }
栈测试
- 示例代码：
void test() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); printf("%d ", StackTop(&st)); StackPop(&st); printf("%d ", StackTop(&st)); StackPop(&st); StackPush(&st, 5); StackPush(&st, 6); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDestroy(&st); }
结果示图：
队列
- 概念及结构
队列，只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
- 数据处理方式
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
图示：
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些（出队列效率低）
- 图示：链表队列
接口展示
//默认队列数据类型 typedef int QDataType; //队列节点类型（链表队列） typedef struct QueueNode { //址域 struct QueueNode* next; //值域 QDataType data; }QueueNode; //队列类型(记录队头和队尾) typedef struct Queue { QueueNode* head;//记录队列头结点地址 QueueNode* tail;//记录队列尾结点地址 // size_t _size;//记录队列数据个数（可有可无，自己选择） }Queue; //队列初始化 void QueueInit(Queue* pq); //void QueueInit(QueueNode** pphead, QueueNode** pptail); //队列销毁 void QueueDestroy(Queue* pq); //入队列 void QueuePush(Queue* pq, QDataType x); //出队列 void QueuePop(Queue* pq); //队列头结点数据 QDataType QueueFront(Queue* pq); //队列尾节点数据 QDataType QueueBack(Queue* pq); //队列存入数据个数 int QueueSize(Queue* pq); //判断空队列 bool QueueEmpty(Queue* pq);
队列类型创建
首先我们是个链表队列，即需要创建节点类型
然后在队列常用到入栈和出栈操作（与头删和尾插相关），为了便于找到头结点和尾节点，这里创建一个队列结构体，类型成员为两个结点指针，用来记录头结点和尾节点地址
参考代码：
//默认队列数据类型 typedef int QDataType; //队列节点类型（链表队列） typedef struct QueueNode { //址域 struct QueueNode* next; //值域 QDataType data; }QueueNode; //队列类型(记录队头和队尾) typedef struct Queue { QueueNode* head;//记录队列头结点地址 QueueNode* tail;//记录队列尾结点地址 // size_t _size;//记录队列数据个数（可有可无，自己选择） }Queue;
队列初始化
最开始没有数据，即头指针和尾指针都为NULL
- 参考代码：
//队列初始化 void QueueInit(Queue* pq) { //避免传入参数错误 assert(pq); //初始化 pq->head = pq->tail = NULL; return; }
队列销毁
- 注意：
- 结点时一个个开辟的，需要一个个进行释放
- 释放前记得保存下个节点地址，避免地址丢失
参考代码：
//队列销毁 void QueueDestroy(Queue* pq) { //避免传入参数错误 assert(pq); //创建寻址指针 QueueNode* cur = pq->head; while (cur) { //保存下个结点地址 QueueNode* next = cur->next; //释放当前结点 free(cur); //找到下一个结点 cur = next; } return; }
入队
- 注意：
- 入队开辟新结点并初始化
- 尾插考虑空队列的情况
- 参考代码：
//入队列 void QueuePush(Queue* pq, QDataType x) { //避免传入参数错误 assert(pq); //创建结点并初始化 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; //放入队尾 if (pq->head == NULL)//为空栈的特殊情况 { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode;//尾插 pq->tail = newnode;//记录新尾节点 } return; }
出队
- 注意：
- 空队列无法再进行出队
- 出队需要对出队结点释放并更新头指针位置
- 参考代码：
//出队列 void QueuePop(Queue* pq) { //避免传入参数错误 assert(pq); //为空队列无法出队列 assert(!QueueEmpty(pq)); //保存下一个结点 QueueNode* next = pq->head->next; //释放队列头 free(pq->head); //队头更新 pq->head = next; return; }
队列头结点数据
- 注意：
- 空队列没有数据
- 参考代码：
//队列头结点数据 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; }
队列存入数据个数
- 参考代码：
//队列存入数据个数 int QueueSize(Queue* pq) { //避免传入参数错误 assert(pq); int size = 0; //遍历队列 QueueNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }
判断空队列
注：同样的对于C语言使用布尔类型需要包含<stdbool.h>头文件
- 参考代码：
//判断空队列 bool QueueEmpty(Queue* pq) { //避免传入参数错误 assert(pq); return pq->head == NULL; }
队列测试
- 测试代码：
void test() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QDataType front = QueueFront(&q); printf("%d ", front); QueuePop(&q); QueuePush(&q, 3); QueuePush(&q, 4); while (!QueueEmpty(&q)) { QDataType front = QueueFront(&q); printf("%d ", front); QueuePop(&q); } printf("\n"); }
结果示图：
对上述内容有什么问题记得留言呦~可以的话记得留下你的三连哈！~
