【LeetCode刷题(数据结构与算法)】:用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶
int pop() 移除并返回栈顶元素
int top() 返回栈顶元素
boolean empty() 如果栈是空的,返回 true ;否则,返回 false
注意:
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可
示例:
输入:
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]
解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示:
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

这里有一个动图我一会儿上传到评论区大家可以看一下加深理解
为了满足栈的特性,即最后入栈的元素最先出栈,在使用队列实现栈时,应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作,其中 queue1
用于存储栈内的元素,queue2
作为入栈操作的辅助队列
入栈操作时,首先将元素入队到 queue2
然后将 queue1
的全部元素依次出队并入队到 queue2
此时queue2
的前端的元素即为新入栈的元素,再将 queue1
和queue2
互换,则queue1
的元素即为栈内的元素,queue1
的前端和后端分别对应栈顶和栈底
由于每次入栈操作都确保 queue1
的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue1
的前端元素并返回即可,获得栈顶元素操作只需要获得 queue1
的前端元素并返回即可(不移除元素)
由于 queue1
用于存储栈内的元素,判断栈是否为空时,只需要判断 queue1
是否为空即可
动图链接
动图链接
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>typedef int QueueDataType;typedef struct QNode
{struct QNode* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;QueueDataType size;
}Que;
void QueueInit(Que* pq);void QueuePush(Que* pq, QueueDataType x);void QueuePop(Que* pq);void QueueDestroy(Que* pq);QueueDataType QueueFront(Que* pq);QueueDataType QueueBack(Que* pq);bool QueueEmpty(Que* pq);QueueDataType QueueSize(Que* pq);//#include"Queue.h"void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size =0;
}void QueuePush(Que* pq, QueueDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL && pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;//tail指针指向下一个结构体---//--存放地址pq->tail = newnode;//尾节点}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);//assert(!QueueEmpty(Que * pq));//写法错误 不允许使用类命名assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}QueueDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QueueDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}QueueDataType QueueSize(Que* pq)
{assert(pq);return pq->size;
}void QueueDestroy(Que* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* current = pq->head;while (current){QueueNode* next = current->next;free(current);current = next;}pq->head = pq->tail = NULL;pq->size = 0;
}typedef struct {Que q1;Que q2;
}MyStack;MyStack* myStackCreate() {//动态内存开辟函数malloc在堆区 无free不会主动销毁MyStack*pst=(MyStack*)malloc(sizeof(MyStack)*2);QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;//避免野指针NULL
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Que*Empty=&obj->q1;Que*NonEmpty=&obj->q2;if(!QueueEmpty(&obj->q1)){NonEmpty=&obj->q1;Empty=&obj->q2;}while(QueueSize(NonEmpty)>1){QueuePush(Empty,QueueFront(NonEmpty));QueuePop(NonEmpty);}//题目要求移除并返回栈顶元素topint top=QueueFront(NonEmpty);QueuePop(NonEmpty);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else {return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&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);
*/
相关文章:
【LeetCode刷题(数据结构与算法)】:用队列实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty) 实现 MyStack 类: void push(int x) 将元素 x 压入栈顶 int pop() 移除并返回栈顶元素 int top() 返…...
“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递的方式的区别
“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递方式的主要区别如下: 数据的流动方向: 在“客户端到服务器的数据传递”中,数据是从客户端(如浏览器)流向服务器。在“服务器上的数据传递”中&…...
LCR 181 字符串中的单词反转
题目来源: leetcode题目,网址:LCR 181. 字符串中的单词反转 - 力扣(LeetCode) 解题思路: 倒叙遍历,获得每个单词的起始位置与终止位置,然后将每次遇到的单词插入结果中。 解题…...
百度OCR识别图片文本字符串——物联网上位机软件
一、开发背景 根据项目需求,我们需要完成LED显示屏实时显示歌词的效果。最优的方法是调用歌曲播放器的API获取歌词,但是由于这个开发资格不是很好申请,因此我们采用其他方案,即通过OCR识别获取歌词,并投射到LED显示屏上…...
JAVA学习(6)-全网最详细~
🌈write in front🌈 🧸大家好,我是Aileen🧸.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如…...
睿趣科技:未来抖音开网店还有前景吗
随着科技的快速发展,电商平台已经成为了人们生活中不可或缺的一部分。在中国,抖音作为一个短视频平台,近年来迅速崛起,吸引了大量的用户和商家。那么,在未来,抖音是否还能为商家提供一个有效的电商平台呢?…...
第六章 应用层 | 计算机网络(谢希仁 第八版)
文章目录 第六章 应用层6.1 域名系统DNS6.1.1 域名系统概述6.1.2 互联网的域名结构6.1.3 域名服务器 6.2 文件传送协议6.2.1 FTP概述6.2.2 FTP的基本工作原理6.2.3 简单文件传送协议TFTP 6.3 远程终端协议TELNET6.4 万维网www6.4.1 万维网概述6.4.2 统一资源定位符URL6.4.3 超文…...
c++ lambda 表达式
1. 简介 lambda(匿名函数)是C11引入的一种函数对象,它允许我们在需要函数的地方创建一个临时的、匿名的函数。lambda表达式表示一个可以执行的代码单元,可以理解为一个未命名的内联函数。Lambda函数可以用于简化代码、提高可读性…...
Go语言入门心法(七): 并发与通道
Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言并发与通道...
前端组件封装:构建模块化、可维护和可重用的前端应用
前端组件封装:构建模块化、可维护和可重用的前端应用 前端开发领域的快速演进已经将前端应用的规模和复杂性提升到了一个新的水平。在这个背景下,前端组件封装成为了一项关键实践,旨在构建模块化、可维护和可重用的前端应用。在本文中&#…...
GPT绘制流程图咒语
【咒语】下面是我的一篇论文选取部分,为了让读者更好理解,我准备画一张图,请你阅读后为我设计一下这个图应该怎么画,更有说服力,更容易理解 论文片段: 多模态数据融合研究的基础在于有效的数据采集。首先&a…...
【扩散模型从原理到实战】Chapter1 扩散模型简介
文章目录 1.1 扩散模型的原理生成模型扩散过程DDPM的扩散过程前向过程反向过程优化目标 1.2 扩散模型的发展开始扩散:DDPM加速生成:采样器刷新记录:基于CLIP的多模态图像生成引爆网络:基于CLIP的多模态图像生成再次“出圈”&#…...
使用轮廓分数提升时间序列聚类的表现
我们将使用轮廓分数和一些距离指标来执行时间序列聚类实验,并且进行可视化 让我们看看下面的时间序列: 如果沿着y轴移动序列添加随机噪声,并随机化这些序列,那么它们几乎无法分辨,如下图所示-现在很难将时间序列列分组为簇: 上面…...
蔬菜水果生鲜配送团购商城小程序的作用是什么
蔬菜水果是人们生活所需品,从业者众多,无论小摊贩还是超市商场都有不少人每天光临,当然这些只是自然流量,在实际经营中,蔬菜水果商家还是面临着一些难题。 对蔬菜水果商家而言,线下门店是重要的࿰…...
金融用户实践|分布式存储支持数据仓库业务系统性能验证
作者:深耕行业的 SmartX 金融团队 闫海涛 估值是指对资产或负债的价值进行评估的过程,这对于投资决策具有重要意义。每个金融公司资管业务人员都期望能够实现实时的业务估值,快速获取最新的数据和指标,从而做出更明智的投资决策。…...
代码随想录二刷 Day41
509. 斐波那契数 这个题简单入门,注意下N小于等于1的情况就可以 class Solution { public:int fib(int n) {if (n < 1) return n; //这句不写的话test能过但是另外的过不了vector<int> result(n 1); //定义存放dp结果的数组,还要定义大小r…...
C++项目实战——基于多设计模式下的同步异步日志系统-⑪-日志器管理类与全局建造者类设计(单例模式)
文章目录 专栏导读日志器建造者类完善单例日志器管理类设计思想单例日志器管理类设计全局建造者类设计日志器类、建造者类整理日志器管理类测试 专栏导读 🌸作者简介:花想云 ,在读本科生一枚,C/C领域新星创作者,新星计…...
Hadoop3教程(十四):MapReduce中的排序
文章目录 (99)WritableComparable排序什么是排序什么时候需要排序排序有哪些分类如何实现自定义排序 (100)全排序案例案例需求思路分析实际代码 (101)二次排序案例(102) 区内排序案例…...
测试需要写测试用例吗?
如何理解软件的质量 我们都知道,一个软件从无到有要经过需求设计、编码实现、测试验证、部署发布这四个主要环节。 需求来源于用户反馈、市场调研或者商业判断。意指在市场行为中,部分人群存在某些诉求或痛点,只要想办法满足这些人群的诉求…...
Qt 视口和窗口的区别
视口和窗口 绘图设备的物理坐标是基本的坐标系,通过QPainter的平移、旋转等变换可以得到更容易操作的逻辑坐标 为了实现更方便的坐标,QPainter还提供了视口(Viewport)和窗口(Window)坐标系,通过QPainter内部的坐标变换矩阵自动转换为绘图设…...
bilibili_live_stream_code:开源直播推流工具 解锁自定义直播新体验
bilibili_live_stream_code:开源直播推流工具 解锁自定义直播新体验 【免费下载链接】bilibili_live_stream_code 用于在准备直播时获取第三方推流码,以便可以绕开哔哩哔哩直播姬,直接在如OBS等软件中进行直播,软件同时提供定义直…...
【QT】Layout布局间隙优化全攻略(参数调整与实战技巧)
1. 为什么你的QT界面总有"迷之缝隙"? 每次用QT做界面开发时,最让我抓狂的就是那些莫名其妙出现的空白间隙。明明已经按照设计稿精确设置了控件尺寸,但运行起来总会出现几个像素的偏差。后来我发现,这些间隙主要来自三个…...
【Mojo+Python混合部署失效真相】:92%开发者忽略的编译期符号冲突、运行时上下文隔离与调试断点丢失问题
第一章:MojoPython混合部署失效真相全景概览Mojo 作为新兴的高性能系统编程语言,设计初衷是与 Python 生态无缝互操作;然而在真实生产部署中,“Mojo Python 混合部署”常出现静默失败、ABI 不兼容、运行时崩溃或性能断崖式下降等…...
CentOS 7下OnlyOffice离线部署全攻略:从依赖包下载到一键配置(避坑指南)
CentOS 7下OnlyOffice离线部署全攻略:从依赖包下载到一键配置(避坑指南) 在企业内网或安全隔离环境中部署文档协作平台时,OnlyOffice凭借其开源特性和丰富的编辑功能成为首选方案。本文将深入探讨如何在CentOS 7系统中实现完全离线…...
软件外包公司的“末路”:印度同行都慌了?——软件测试从业者的专业视角
在当今数字化浪潮中,软件外包行业曾是全球经济的重要引擎,尤其以印度为代表的外包巨头,凭借低成本人力优势主导了全球市场。然而,随着人工智能(AI)技术的迅猛发展,这一模式正面临前所未有的挑战…...
探索电池2RC等效电路模型:从参数辨识到SOC估计
电池2RC等效电路模型,最小二乘法参数辩识,电池端电压误差小,扩展卡尔曼估计SOC精度高。 有文档,数据,视频,仿真图。在电池研究领域,准确建模和参数估计对于理解电池行为至关重要。今天咱就唠唠电…...
2026年多模态AI前瞻:Qwen3-VL-2B开源生态发展潜力分析
2026年多模态AI前瞻:Qwen3-VL-2B开源生态发展潜力分析 1. 项目概述与核心价值 Qwen3-VL-2B-Instruct作为新一代开源视觉语言模型,代表了多模态AI技术的重要发展方向。这个模型不仅能够理解文本,更重要的是具备了"看"的能力——它…...
像素幻梦工坊实战落地:数字艺术教育机构像素创作课AI教具部署
像素幻梦工坊实战落地:数字艺术教育机构像素创作课AI教具部署 1. 项目背景与教育价值 在数字艺术教育领域,像素艺术作为入门门槛较低但创意空间广阔的艺术形式,正受到越来越多教育机构的青睐。然而传统像素艺术教学面临两大挑战:…...
ESP8266-ESP32 物联网开发入门
ESP8266/ESP32物联网开发入门指南 在智能家居、远程监控和工业自动化等领域,物联网技术正快速改变我们的生活。作为物联网开发的热门选择,ESP8266和ESP32凭借低成本、高性能和丰富的开发资源,成为初学者和工程师的首选。本文将介绍如何快速入…...
translategemma-27b-it部署指南:Ollama模型缓存管理与多版本切换实践
translategemma-27b-it部署指南:Ollama模型缓存管理与多版本切换实践 你是不是也遇到过这样的烦恼:好不容易在Ollama上部署了一个大模型,用了一段时间想试试新版本,结果发现硬盘空间告急,或者不知道旧版本模型文件藏在…...
