当前位置： 首页 > news >正文

【LeetCode刷题指南】--队列实现栈，栈实现队列

news 2025/7/27 11:36:02

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。 

 前言：我们学完了队列和栈之后，还是需要通过做题来检验和巩固我们所学知识的，今天想给大家分享一下队列实现栈，栈实现队列这两个经典的力扣题。

目录

1.队列实现栈 

解题过程：

代码演示： 

 2.栈实现队列

解题过程： 

代码演示：

1.队列实现栈 

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

题目描述： 

题目示例： 

思路： 

  • 入栈：往不为空的队列插入数据(能保证后续插入数据后最后也是先进后出)
  • 出栈：非空队列中的前size-1个数据挪到另一个队列中，再将最后一个数据出队列
  • 取栈顶：(不出数据)返回非空队列中的队尾数据

解题过程：

1.先定义一个结构，两个队列，再创建栈，动态申请一个空间，再初始化两个队列直接调用队列的方法就可以

2.入栈：往不为空的队列中插入数据，分情况讨论，q1不为空就往q1里插入数据，q2不为空就往q2里插入数据

3.出栈：先假设一个为空，再用一个if语句进行确定，假设错了就在if语句里面改过来。将非空队列中前size-1个数据挪到另一个队列中即空队列，所以当非空队列中的数据个数大于1时进行循环，重复取非空队列队头数据，插入到空队列中，再出数据的操作。循环结束后，非空队列中就剩下一个数据，因为返回类型为int，我们先利用取队头数据的方法将它保存下来，再出队列然后返回保存下来的数据

4.取栈顶：取栈顶数据不用出栈，所以谁为空我们直接取它的队尾数据然后返回就可以了

5.判空和销毁：全为空即为空，销毁的话先调用队列的销毁方法销毁掉两个队列，最后将栈释放掉后置空就可以了 

具体过程图示如下： 

代码演示： 

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* phead;QueueNode* ptail;//int size;//队中有效数据个数
}Queue;//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;//pq->size = 0;
}//入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请新节点QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));if (newcode == NULL){perror("malloc fail!");exit(1);}newcode->data = x;newcode->next = NULL;//如果队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newcode;//pq->size++;}else{pq->ptail->next = newcode;pq->ptail = pq->ptail->next;//pq->size++;}
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出队
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//如果队伍中只有一个节点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;//pq->size--||pq->size=0}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;//pq->size--;}
}//取队首数据
QDataType QueueHead(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueTail(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列有效数据个数
int QueueSize(Queue* pq)
{//如果使用了size记录直接返回就可以了//return pq->size;//如果没有就遍历QueueNode* pcur = pq->phead;int size = 0;while (pcur){++size;pcur=pcur->next;}return size;
}//队列的销毁
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;
}//----------------------以上是队列结构的定义和常用方法----------------------------
typedef struct {Queue q1;Queue q2;
} MyStack;//创建一个栈
MyStack* myStackCreate() {MyStack*pter=(MyStack*)malloc(sizeof(MyStack));QueueInit(&pter->q1);QueueInit(&pter->q2);return pter;
}void myStackPush(MyStack* obj, int x) {//如果q1为空，往q1里插入数据，反之则是往q2里插入数据if(!QueueEmpty(&obj->q1)){//q1QueuePush(&obj->q1,x);}else{//q2QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {//先假设一个为空Queue*emp=&obj->q1;Queue*nonemp=&obj->q2;if(QueueEmpty(&obj->q2)){emp=&obj->q2;nonemp=&obj->q1;}//将非空队列中前size-1个数据挪到另一个队列中while(QueueSize(nonemp)>1){//取队头数据，插入空队列中QueuePush(emp,QueueHead(nonemp));//出数据QueuePop(nonemp);}//将非空队列中最后一个数据出队列,注意返回类型为int出之前先存一下int top=QueueHead(nonemp);QueuePop(nonemp);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){//取q1的队尾数据,并返回return QueueTail(&obj->q1);}else{//取q2的队尾数据,并返回return QueueTail(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {//全为空即为空return (QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2));
}void myStackFree(MyStack* obj) {QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);obj=NULL;
}/*** 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);
*/

写这个题之前由于我们是用的C语言，所以需要把之前我们实现好的队列结构拷贝一份上去

 2.栈实现队列

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

题目描述： 

题目示例： 

思路： 

  • 入队列：往PushST里面插入数据
  • 出队列：PopST不为空直接出数据，为空就把PushST的数据先导入过来再出数据
  • 取队首：(不出数据)和出队列类似，但是不出数据，PopST不为空直接取栈顶数据，为空就把PushST的数据先导入过来再取

解题过程： 

1.定义两个栈，创建一个队列，申请一块空间，初始化两个栈，再返回

2.入队列：往PushST里面插入数据

3.出队列：如果PopST不为空直接出数据，注意返回类型，所以要先把PopST的栈顶数据存下来，再出数据，最后直接返回就可以了，但是如果PopST为空，我们先要将PushST的数据全部导入过来，直达PushST为空(重复取PushST栈顶元素，导入到PopST中，再出PushST的栈的操作)，循环完后PopST就不为空了可以直接出数据

4.取队首：操作和出队列一样，就是不用出数据，只用把最后那个PopST出栈的操作去掉就可以

5.判空和销毁：全为空即为空，销毁的话就是先调用栈的方法销毁掉两个栈，最后释放掉队列并置为空

具体过程图示如下：

代码演示：

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//检查空间//空间不够就增容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//空间足够ps->arr[ps->top++] = x;
}//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//出栈
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return 	ps->arr[ps->top - 1];;
}//求栈中有效数据个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//--------------------以上是栈结构的定义和常用方法-----------------------------
typedef struct {ST PushST;ST PopST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*pq=(MyQueue*)malloc(sizeof(MyQueue));STInit(&pq->PushST);STInit(&pq->PopST);return pq;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->PushST,x);
}int myQueuePop(MyQueue* obj) {//PopST为空，先将PushST(不为空)的数据导入过来，再出栈if(STEmpty(&obj->PopST)){//取PushST栈顶数据，导入到PopST中，再出栈while(!STEmpty(&obj->PushST)){STPush(&obj->PopST,STTop(&obj->PushST));STPop(&obj->PushST);}}//PopST不为空直接出数据int top=STTop(&obj->PopST);STPop(&obj->PopST);return top;
}int myQueuePeek(MyQueue* obj) {//PopST为空，先将PushST(不为空)的数据导入过来if(STEmpty(&obj->PopST)){//取PushST栈顶数据，导入到PopST中，再出栈while(!STEmpty(&obj->PushST)){STPush(&obj->PopST,STTop(&obj->PushST));STPop(&obj->PushST);}}//PopST不为空直接取数据int top=STTop(&obj->PopST);return top;
}bool myQueueEmpty(MyQueue* obj) {//全为空即为空return (STEmpty(&obj->PushST)&&STEmpty(&obj->PopST));
}void myQueueFree(MyQueue* obj) {STDestory(&obj->PopST);STDestory(&obj->PushST);free(obj);obj=NULL;
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

往期回顾：

【LeetCode刷题指南】--随机链表的复制

【LeetCode刷题指南】--有效的括号

结语：本篇文章就到此结束了，《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目，肯定会更加复杂一些。而且题目形式也不一样，大家需要注意一下。这篇中的栈实现队列，队列实现栈都很经典，大家下去可以多做一下试试。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持

http://www.lryc.cn/news/600815.html

相关文章：

  • MySQL 8.0 OCP 1Z0-908 题目解析(37)
  • mysql group by 多个行转换为一个字段
  • 数据结构（4）单链表算法题（上）
  • 图解网络-小林coding笔记（持续更新）
  • 期货资管软件定制开发流程
  • write`系统调用
  • 宝塔面板如何升级OpenSSL
  • 哈尔滨←→南昌的铁路要道
  • IC测试之pogo pin学习与总结-20250726
  • 鲲鹏服务器部署Kafka2.8.1
  • 微服务springcloud http客户端feign
  • 【资讯】2025年软件行业发展趋势：AI驱动变革，云原生与安全成核心
  • 【Spring Cloud】微服务学习
  • LeetCode——1717. 删除子字符串的最大得分
  • 秋招Day20 - 微服务 - 概念
  • 【机器学习深度学习】模型微调：多久才算微调完成？——如何判断微调收敛，何时终止训练
  • 二维数组相关学习
  • 大模型蒸馏(distillation)---从DeepseekR1-1.5B到Qwen-2.5-1.5B蒸馏
  • UniappDay03
  • 【Canvas与旗帜】条纹版大明三辰旗
  • AI是否会终结IT职业？深度剖析IT行业的“涌现”与重构
  • 慧星云新增大模型服务：多款大模型轻松调用
  • C++：STL中vector的使用和模拟实现
  • MySQL的底层原理--InnoDB数据页结构
  • 人大金仓 kingbase 连接数太多, 清理数据库连接数
  • 基于匿名管道的多进程任务池实现与FD泄漏解决方案
  • VUE2 学习笔记7 v-model、过滤器
  • 6.数组和字符串
  • ChatIm项目文件上传与获取
  • 拉普拉斯方程的径向解法