༺ 个人主页 · 纪念229 ༻我的博客主页༒专栏目录《数据结构》༒༒其它有趣的计算机知识༒༺世上本没有路走的人多了自然就有了༻这篇文章讲述的是利用队列的功能来实现栈的功能个人见解希望对你有所帮助这里我讲述一下我们会看到许多结构体来构成栈和队列但是在我们写代码的时候我建议用顺序表实现栈、用单链表实现队列本文也是如此文章目录1.用队列实现栈1.1QueueNodeQDataType Queue1.2QInit1.3QEmpty(Queue* q)QPush(Queue* q,QDataType x)1.4QPop(Queue* q)QFront(Queue* q)1.5MyStack myStackCreate()1.6myStackPush(MyStack* obj, int x)myStackPop(MyStack* obj)1.7myStackTop(MyStack* obj)1.8myStackEmpty(MyStack* obj)1.9myStackFree(MyStack* obj)我们先看一下题目这里的移除栈顶元素还要返回该元素1.用队列实现栈首先我们要实现队列的功能和队列的结构然后我们用队列的功能来实现栈的功能代码展示#includeassert.h#includestdlib.h#includestdbool.h//实现队列基础结构与操作typedefintQDataType;//队列节点typedefstructQueueNode{QDataType val;structQueueNode*next;}QNode;//队列结构体typedefstructQueue{QNode*phead;QNode*ptail;intsize;}Queue;//队列初始化voidQInit(Queue*q){q-pheadNULL;q-ptailNULL;q-size0;}//判断队列是否为空boolQEmpty(Queue*q){returnq-pheadNULL;}voidQPush(Queue*q,QDataType x){QNode*newnode(QNode*)malloc(sizeof(QNode));if(newnodeNULL){perror(malloc fail);exit(1);}newnode-valx;newnode-nextNULL;//当队列不为空时if(!QEmpty(q)){q-ptail-nextnewnode;q-ptailnewnode;}else{q-pheadq-ptailnewnode;}q-size;}//队头出队voidQPop(Queue*q){if(QEmpty(q))return;QNode*delq-phead;q-pheaddel-next;free(del);delNULL;--q-size;}//获取队头元素QDataTypeQFront(Queue*q){assert(!QEmpty(q));returnq-phead-val;}//以上是对列实现的基本功能//用队列实现栈typedefstruct{//用两个队列实现栈Queue q1;Queue q2;}MyStack;//注意栈里用的是队列而不是队列的地址//栈的初始化MyStack*myStackCreate(){//给与栈空间MyStack*obj(MyStack*)malloc(sizeof(MyStack));QInit(obj-q1);QInit(obj-q2);returnobj;}//入栈voidmyStackPush(MyStack*obj,intx){//向非空队列插入元素保证一个队列为空若都为空就入队obj-q2if(!(QEmpty(obj-q1))){QPush(obj-q1,x);}else{QPush(obj-q2,x);}}//出栈intmyStackPop(MyStack*obj){//默认obj-q1为空队列Queue*EmptyQueueobj-q1;Queue*DataQueueobj-q2;//如果obj-q1不为空就把obj-q1设置为有效队列if(!QEmpty(obj-q1)){EmptyQueueobj-q2;DataQueueobj-q1;}//含有值的队列除了最后一个数都放入空队列中提取最后一个数并删除while(DataQueue-size1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}//剩余最后一个元素就是栈顶返回inttopCalQFront(DataQueue);QPop(DataQueue);returntopCal;}intmyStackTop(MyStack*obj){Queue*EmptyQueueobj-q1;Queue*DataQueueobj-q2;if(!QEmpty(obj-q1)){DataQueueobj-q1;EmptyQueueobj-q2;}// 队列值要交换但有效数不变while(DataQueue-size1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}inttopValQFront(DataQueue);QPop(DataQueue);QPush(EmptyQueue,topVal);returntopVal;}boolmyStackEmpty(MyStack*obj){//两个个队列都栈空returnQEmpty(obj-q1)QEmpty(obj-q2);}voidmyStackFree(MyStack*obj){//先释放队列所有节点while(!QEmpty(obj-q1)){QPop(obj-q1);}while(!QEmpty(obj-q2)){QPop(obj-q2);}//再释放所有结构体free(obj);}/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj myStackCreate(); * myStackPush(obj, x); * int param_2 myStackPop(obj); * int param_3 myStackTop(obj); * bool param_4 myStackEmpty(obj); * myStackFree(obj); */注代码主要讲重要部分如有遗漏请见谅1.1QueueNodeQDataType Queue//实现队列基础结构与操作typedefintQDataType;//队列节点typedefstructQueueNode{QDataType val;structQueueNode*next;}QNode;//队列结构体typedefstructQueue{QNode*phead;QNode*ptail;intsize;}Queue;首先我们知道队列是由单链表的头节点和尾节点构成而队列节点就是单链表节点为了方便后面写的代码我们用typedef简化代码书写这里为什么队列里还有int size是因为用队列实现栈要频繁使用队列的有效个数1.2QInit//队列初始化voidQInit(Queue*q){q-pheadNULL;q-ptailNULL;q-size0;}我们得知道队列初始化就是置为NULL和清空1.3QEmpty(Queue* q)QPush(Queue* q,QDataType x)//判断队列是否为空boolQEmpty(Queue*q){returnq-pheadNULL;}voidQPush(Queue*q,QDataType x){QNode*newnode(QNode*)malloc(sizeof(QNode));if(newnodeNULL){perror(malloc fail);exit(1);}newnode-valx;newnode-nextNULL;//当队列不为空时if(!QEmpty(q)){q-ptail-nextnewnode;q-ptailnewnode;}else{q-pheadq-ptailnewnode;}q-size;}队尾入队分两种情况1.队列为空2.队列不为空所以我们得写一个判断队列为空的函数这里因为用了bool类型所以要加头文件#includestdbool.h判断队列是否为空就是判断ptial队尾是否等于NULL等于返回ture不等于返回false这里因为是入队所以要创建节点要用malloc,即要用头文件#inlcudestdlib.h创建成功后还要判断创建的节点是否成功成功创建后给节点填满内容当队列为空时队列的头节点和尾节点都赋值为newnode节点当队列不为空时将ptial连接newnode然后把ptail赋值为newnode最后既然是入队size就要加加1.4QPop(Queue* q)QFront(Queue* q)//队头出队voidQPop(Queue*q){if(QEmpty(q))return;QNode*delq-phead;q-pheaddel-next;free(del);delNULL;--q-size;}//获取队头元素QDataTypeQFront(Queue*q){assert(!QEmpty(q));returnq-phead-val;}队头出队首先要判断队列里是否头节点为空的话直接返回不为空创建一个队列指针del存下队头然后再将队头赋值给del-next为新的队头然后清空del指针里的内容且置为空既然是出队那么size的个数就要减减获取队头元素先判断队列里是否有数据判空然后直接返回队头元素以上是队列实现的基本功能1.5MyStack myStackCreate()代码展示/用队列实现栈typedefstruct{//用两个队列实现栈Queue q1;Queue q2;}MyStack;//注意栈里用的是队列而不是队列的地址//栈的初始化MyStack*myStackCreate(){//给与栈空间MyStack*obj(MyStack*)malloc(sizeof(MyStack));QInit(obj-q1);QInit(obj-q2);returnobj;}本文讲述的栈是由两个队列实现的栈的初始化首先要给一个栈指针obj给它创建内容然后再用队列的基本功能初始化队列然后返回栈指针1.6myStackPush(MyStack* obj, int x)myStackPop(MyStack* obj)代码展示/入栈voidmyStackPush(MyStack*obj,intx){//向非空队列插入元素保证一个队列为空若都为空就入队obj-q2if(!(QEmpty(obj-q1))){QPush(obj-q1,x);}else{QPush(obj-q2,x);}}//出栈intmyStackPop(MyStack*obj){//默认obj-q1为空队列Queue*EmptyQueueobj-q1;Queue*DataQueueobj-q2;//如果obj-q1不为空就把obj-q1设置为有效队列if(!QEmpty(obj-q1)){EmptyQueueobj-q2;DataQueueobj-q1;}//含有值的队列除了最后一个数都放入空队列中提取最后一个数并删除while(DataQueue-size1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}//剩余最后一个元素就是栈顶返回inttopCalQFront(DataQueue);QPop(DataQueue);returntopCal;}入栈向非空队列插入元素保证一个队列为空若都为空就入队obj-q2用的是队列的入队来实现入栈出栈我们默认q1队列为空队列即有效队列为q2如果q1不为空那么有效队列为q1DataQueue原来存数据的队列数据被大量删除循环里每轮都执行 QPop(DataQueue) 前面所有元素全部弹出只剩最后一个。​EmptyQueue 只是临时中转被挪过去的元素只是暂存下次push新元素直接往这个队列塞不影响逻辑。这里有个循环把有效队列的元素放入空队列中留一个不改变实际队列数据但我们出循环时出队列那么就会改变实际队列数据最后返回栈顶元素为什么删除的是DataQueue会改变实际队列的数据是因为它存的是q1||q2的实际地址这里的出栈实现是出队列时我们把队列的队头和队尾都反转了实际上就是后进先出1.7myStackTop(MyStack* obj)代码实现intmyStackTop(MyStack*obj){Queue*EmptyQueueobj-q1;Queue*DataQueueobj-q2;if(!QEmpty(obj-q1)){DataQueueobj-q1;EmptyQueueobj-q2;}// 队列值要交换但有效数不变while(DataQueue-size1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}inttopValQFront(DataQueue);QPop(DataQueue);QPush(EmptyQueue,topVal);returntopVal;}得到栈顶元素的逻辑与出栈差不多就不在说明了少了个出队操作1.8myStackEmpty(MyStack* obj)代码实现boolmyStackEmpty(MyStack*obj){//两个个队列都栈空returnQEmpty(obj-q1)QEmpty(obj-q2);}栈为空实际上是两个队列为NULL用bool类型直接返回两队列指针即可1.9myStackFree(MyStack* obj)代码展示voidmyStackFree(MyStack*obj){//先释放队列所有节点while(!QEmpty(obj-q1)){QPop(obj-q1);}while(!QEmpty(obj-q2)){QPop(obj-q2);}//再释放所有结构体free(obj);}栈的释放实际上就是将两队列全部出完在将malloc的obj free即可文章写到这里就告一段落看到这里希望你有所收获感谢观看