【数据结构】--- 栈和队列

前言前面学习了数据结构的顺序表、单链表、双向循环链表这些结构现在就来学习栈和队列这里可以简单的说栈和队列是具有特殊化的线性表一、栈1.1、栈的概念和结构栈是一种遵循先入后出逻辑的线性数据结构。栈是一种特殊的线性表它只允许在固定的一端进行插入和删除元素操作进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵循先进后出LIFO的原则也就是所谓的后来者居上如图所示我们把堆叠元素的顶部称为“栈顶”底部称为“栈底”。将元素添加到栈顶的操作叫做“入栈”删除栈顶的元素叫做“出栈”。从图中我们可以看出栈数据的出栈和入栈都在栈顶这就是栈数据先进后出的原则。1.2、栈的实现栈的实现可以使用数组来实现当然也可以使用链表来实现这里就用数组来实现栈。用数组来实现栈就和之前顺序表的实现有些相似对顺序表不了解的话可以看一下前面的【数据结构】--- 顺序表首先先来看一下栈这个数据结构都要实现哪些功能#includestdio.h #includestdlib.h #includeassert.h #includestdbool.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; }感谢各位大佬支持并指出问题如果本篇内容对你有帮助可以一键三连支持以下感谢支持