前言
前面学习了数据结构的顺序表、单链表、双向循环链表这些结构；现在就来学习栈和队列，这里可以简单的说栈和队列是具有特殊化的线性表
一、栈
1.1、栈的概念和结构
栈是一种遵循先入后出逻辑的线性数据结构。
栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作；进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵循先进后出（LIFO）的原则；也就是所谓的后来者居上
如图所示，我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将元素添加到栈顶的操作叫做“入栈”，删除栈顶的元素叫做“出栈”。
从图中我们可以看出，栈数据的出栈和入栈都在栈顶；这就是栈数据先进后出的原则。
1.2、栈的实现
栈的实现可以使用数组来实现，当然也可以使用链表来实现，这里就用数组来实现栈。
用数组来实现栈就和之前顺序表的实现有些相似，对顺序表不了解的话可以看一下前面的
首先先来看一下，栈这个数据结构都要实现哪些功能：
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int SType; typedef struct Stack { SType* arr; int size; //栈顶 int num; //空间大小 }Stack; //初始化 void STInit(Stack* ps); //判断栈是否为空 bool STEmpty(Stack* ps); //入栈 void STPush(Stack* ps, SType x); //出栈 void STPop(Stack* ps); //取栈顶数据 SType STtop(Stack* ps); //获取栈中数据个数 int STSize(Stack* ps); //栈的销毁 void STDesTroy(Stack* ps);
1.2.1、初始化
//初始化 void STInit(Stack* ps) { assert(ps); ps->arr = NULL; ps->size = ps->num = 0; }
1.2.2、判断栈是否为空
判断栈是否为空？如果为空，就返回true；如果不为空，就返回false。
//判断栈是否为空 bool STEmpty(Stack* ps) { assert(ps); return ps->size == 0; }
1.2.3、入栈
入栈，在栈顶插入数据（和顺序表尾插相似）
//入栈 void STPush(Stack* ps, SType x) { assert(ps); //判断空间大小是否足够 if (ps->num <= ps->size) { int newnum = (ps->num == 0) ? 4 : 2 * ps->num; SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack)); if (tmp == NULL) { perror("realloc filed"); exit(1); } ps->arr = tmp; ps->num = newnum; } ps->arr[ps->size++] = x; }
1.2.4、出栈
出栈，删除栈顶的数据（和顺序表尾删相似）
//出栈 void STPop(Stack* ps) { assert(ps); //不能传NULL assert(!STEmpty(ps)); //栈不能为空 ps->size--; }
1.2.5、取栈顶数据
取栈顶数据，将栈顶的数据返回即可
//取栈顶数据 SType STtop(Stack* ps) { assert(ps); //不能传NULL assert(!STEmpty(ps)); //栈不能为空 return ps->arr[ps->size - 1]; }
1.2.6、获取栈中数据个数
获取栈中数据个数，这里size就是栈的数据个数
//获取栈中数据个数 int STSize(Stack* ps) { assert(ps); return ps->size; }
1.2.7、销毁栈
这里，动态开辟的空间要进行释放，养成好习惯
//栈的销毁 void STDesTroy(Stack* ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->size = ps->num = 0; }
二、队列
2.1、队列的概念和结构
队列，是一种遵循先入先出规则的线性数据结构。
顾名思义，队列模拟了现实生活中排队现象，即新来的人不断加入队列队尾，而位于对头的人逐个离开
队列只允许在一端进行插入数据操作，在另一端进行删除数据操作
如图，我们将队列头部称为“对头（队首）”，尾部称为“队尾”；
将把元素插入到队尾操作称为“入队”，删除队首的数据的操作称为“出队”
2.2、队列的实现
队列的实现，这里也是即可以使用数组来实现，也可以使用链表来实现；这里使用链表来实现队列
用链表来实现队列就和之前链表的实现有些相似，对单链表不了解的话可以看一下前面的
先来卡看队列的基本功能
typedef int QType; typedef struct QueueNode //队列节结构 { QType data; struct QueueNode* next; }QueueNode; typedef struct Queue //队列结构 { int size; //队列中的数据个数 QueueNode* phead; //队头 QueueNode* ptial; //队尾 }Queue; //初始化 void QueueInit(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //入队列--从队尾删除数据 void QueuePush(Queue* pq); //出队列--从对头删除数据 void QueuePop(Queue* pq); //取队头数据 QType QueueFront(Queue* pq); //取队尾数据 QType QueueBack(Queue* pq); //获取队列数据个数 int QueueSize(Queue* pq); //销毁队列 void QueueDesTroy(Queue* pq);
2.2.1、初始化
//初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptial = NULL; pq->size = 0; }
2.2.2、判断队列是否为空
如果队列为空，返回true；如果不为空，返回false
//判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }
2.2.3、入队列
从队列尾部插入数据，与单链表尾插类似
//入队列--从队尾插入数据 void QueuePush(Queue* pq, QType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (QueueEmpty(pq)) // 队列为空 { pq->phead = pq->ptial = newnode; } else { //队列不为空 pq->ptial->next = newnode; pq->ptial = newnode; } pq->size++; }
2.2.4、出队列
从队头删除数据，与链表头删类似
//出队列--从对头删除数据 void QueuePop(Queue* pq) { assert(pq); //不能传NULL assert(!QueueEmpty(pq)); //队列不能为空 QueueNode* del = pq->phead; pq->phead = pq->phead->next; if (pq->size == 1) //队列只有一个节点 { pq->ptial = NULL; } pq->size--; free(del); del = NULL; }
2.2.5、取队头数据
取队头的数据返回
//取队头数据 QType QueueFront(Queue* pq) { assert(pq); //不能传NULL assert(!QueueEmpty(pq)); //队列不能为空 return pq->phead->data; }
2.2.6、取队尾数据
取队尾数据返回
//取队尾数据 QType QueueBack(Queue* pq) { assert(pq); //不能传NULL assert(!QueueEmpty(pq)); //队列不能为空 return pq->ptial->data; }
2.2.7、获取队列数据个数
获取队列数据个数，这里实现队列时，定义了一个结构体成员size记录队列数据个数。
//获取队列数据个数 int QueueSize(Queue* pq) { assert(pq); //不能传NULL return pq->size; }
2.2.8、销毁队列
队列是由链表实现的，而链表是动态开辟的内存，记得释放。
//销毁队列 void QueueDesTroy(Queue* pq) { assert(pq); //不能传NULL assert(!QueueEmpty(pq)); //队列不能为空 QueueNode* pcur = pq->phead; while (pcur) { QueueNode* del = pcur; pcur = pcur->next; free(del); del = NULL; } pq->phead = pq->ptial = NULL; pq->size = 0; }
感谢各位大佬支持并指出问题，
如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！
