算法（用队列实现栈）

༺ 个人主页 · 纪念229 ༻

🏠我的博客主页🏠

༒专栏目录：《数据结构》༒

༒其它有趣的计算机知识༒

༺世上本没有路，走的人多了自然就有了༻

这篇文章讲述的是利用队列的功能来实现栈的功能，个人见解希望对你有所帮助

这里我讲述一下，我们会看到许多结构体来构成栈和队列，但是在我们写代码的时候我建议用顺序表实现栈、用单链表实现队列（本文也是如此）

这里的移除栈顶元素还要返回该元素

1.用队列实现栈

首先我们要实现队列的功能和队列的结构
然后我们用队列的功能来实现栈的功能
代码展示

#include<assert.h>#include<stdlib.h>#include<stdbool.h>//实现队列基础结构与操作typedefintQDataType;//队列节点typedefstructQueueNode{QDataType val;structQueueNode*next;}QNode;//队列结构体typedefstructQueue{QNode*phead;QNode*ptail;intsize;}Queue;//队列初始化voidQInit(Queue*q){q->phead=NULL;q->ptail=NULL;q->size=0;}//判断队列是否为空boolQEmpty(Queue*q){returnq->phead==NULL;}voidQPush(Queue*q,QDataType x){QNode*newnode=(QNode*)malloc(sizeof(QNode));if(newnode==NULL){perror("malloc fail");exit(1);}newnode->val=x;newnode->next=NULL;//当队列不为空时if(!QEmpty(q)){q->ptail->next=newnode;q->ptail=newnode;}else{q->phead=q->ptail=newnode;}++q->size;}//队头出队voidQPop(Queue*q){if(QEmpty(q))return;QNode*del=q->phead;q->phead=del->next;free(del);del=NULL;--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->q2）if(!(QEmpty(&obj->q1))){QPush(&obj->q1,x);}else{QPush(&obj->q2,x);}}//出栈intmyStackPop(MyStack*obj){//默认obj->q1为空队列Queue*EmptyQueue=&obj->q1;Queue*DataQueue=&obj->q2;//如果obj->q1不为空就把obj->q1设置为有效队列if(!QEmpty(&obj->q1)){EmptyQueue=&obj->q2;DataQueue=&obj->q1;}//含有值的队列除了最后一个数都放入空队列中，提取最后一个数并删除while(DataQueue->size>1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}//剩余最后一个元素就是栈顶返回inttopCal=QFront(DataQueue);QPop(DataQueue);returntopCal;}intmyStackTop(MyStack*obj){Queue*EmptyQueue=&obj->q1;Queue*DataQueue=&obj->q2;if(!QEmpty(&obj->q1)){DataQueue=&obj->q1;EmptyQueue=&obj->q2;}// 队列值要交换但有效数不变while(DataQueue->size>1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}inttopVal=QFront(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.1QueueNode&&QDataType&& Queue

//实现队列基础结构与操作typedefintQDataType;//队列节点typedefstructQueueNode{QDataType val;structQueueNode*next;}QNode;//队列结构体typedefstructQueue{QNode*phead;QNode*ptail;intsize;}Queue;

首先我们知道队列是由单链表的头节点和尾节点构成，而队列节点就是单链表节点
为了方便后面写的代码我们用typedef简化代码书写

这里为什么队列里还有int size是因为用队列实现栈要频繁使用队列的有效个数

1.2QInit

//队列初始化voidQInit(Queue*q){q->phead=NULL;q->ptail=NULL;q->size=0;}

我们得知道队列初始化就是置为NULL和清空

1.3QEmpty(Queue* q)&&QPush(Queue* q,QDataType x)

//判断队列是否为空boolQEmpty(Queue*q){returnq->phead==NULL;}voidQPush(Queue*q,QDataType x){QNode*newnode=(QNode*)malloc(sizeof(QNode));if(newnode==NULL){perror("malloc fail");exit(1);}newnode->val=x;newnode->next=NULL;//当队列不为空时if(!QEmpty(q)){q->ptail->next=newnode;q->ptail=newnode;}else{q->phead=q->ptail=newnode;}++q->size;}

队尾入队分两种情况：
1.队列为空
2.队列不为空

所以我们得写一个判断队列为空的函数
这里因为用了bool类型所以要加头文件#include<stdbool.h>
判断队列是否为空就是判断ptial（队尾）是否等于NULL
等于返回ture不等于返回false

这里因为是入队所以要创建节点要用malloc,即要用头文件#inlcude<stdlib.h>
创建成功后还要判断创建的节点是否成功（成功创建后给节点填满内容）
当队列为空时队列的头节点和尾节点都赋值为newnode节点，当队列不为空时将ptial连接newnode然后把ptail赋值为newnode
最后既然是入队size就要加加

1.4QPop(Queue* q)&&QFront(Queue* q)

//队头出队voidQPop(Queue*q){if(QEmpty(q))return;QNode*del=q->phead;q->phead=del->next;free(del);del=NULL;--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->q2）if(!(QEmpty(&obj->q1))){QPush(&obj->q1,x);}else{QPush(&obj->q2,x);}}//出栈intmyStackPop(MyStack*obj){//默认obj->q1为空队列Queue*EmptyQueue=&obj->q1;Queue*DataQueue=&obj->q2;//如果obj->q1不为空就把obj->q1设置为有效队列if(!QEmpty(&obj->q1)){EmptyQueue=&obj->q2;DataQueue=&obj->q1;}//含有值的队列除了最后一个数都放入空队列中，提取最后一个数并删除while(DataQueue->size>1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}//剩余最后一个元素就是栈顶返回inttopCal=QFront(DataQueue);QPop(DataQueue);returntopCal;}

入栈
向非空队列插入元素，保证一个队列为空（若都为空就入队obj->q2）
用的是队列的入队来实现入栈

出栈
我们默认q1队列为空队列即有效队列为q2
如果q1不为空那么有效队列为q1

1. DataQueue（原来存数据的队列）数据被大量删除
   循环里每轮都执行 QPop(DataQueue) ，前面所有元素全部弹出，只剩最后一个。
   ​
2. EmptyQueue 只是临时中转
   被挪过去的元素只是暂存，下次push新元素直接往这个队列塞，不影响逻辑。
   这里有个循环
   把有效队列的元素放入空队列中留一个不改变实际队列数据
   但我们出循环时出队列那么就会改变实际队列数据
   最后返回栈顶元素

为什么删除的是DataQueue会改变实际队列的数据是因为它存的是
q1||q2的实际地址
这里的出栈实现是出队列时我们把队列的队头
和队尾都反转了，实际上就是后进先出

1.7myStackTop(MyStack* obj)

代码实现

intmyStackTop(MyStack*obj){Queue*EmptyQueue=&obj->q1;Queue*DataQueue=&obj->q2;if(!QEmpty(&obj->q1)){DataQueue=&obj->q1;EmptyQueue=&obj->q2;}// 队列值要交换但有效数不变while(DataQueue->size>1){QPush(EmptyQueue,QFront(DataQueue));QPop(DataQueue);}inttopVal=QFront(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即可

文章写到这里就告一段落，看到这里希望你有所收获，感谢观看！