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

【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刷题(数据结构与算法)】:用队列实现栈

请你仅使用两个队列实现一个后入先出&#xff08;LIFO&#xff09;的栈&#xff0c;并支持普通栈的全部四种操作&#xff08;push、top、pop 和 empty&#xff09; 实现 MyStack 类&#xff1a; void push(int x) 将元素 x 压入栈顶 int pop() 移除并返回栈顶元素 int top() 返…...

“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递的方式的区别

“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递方式的主要区别如下&#xff1a; 数据的流动方向&#xff1a; 在“客户端到服务器的数据传递”中&#xff0c;数据是从客户端&#xff08;如浏览器&#xff09;流向服务器。在“服务器上的数据传递”中&…...

LCR 181 字符串中的单词反转

​​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;LCR 181. 字符串中的单词反转 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 倒叙遍历&#xff0c;获得每个单词的起始位置与终止位置&#xff0c;然后将每次遇到的单词插入结果中。 解题…...

百度OCR识别图片文本字符串——物联网上位机软件

一、开发背景 根据项目需求&#xff0c;我们需要完成LED显示屏实时显示歌词的效果。最优的方法是调用歌曲播放器的API获取歌词&#xff0c;但是由于这个开发资格不是很好申请&#xff0c;因此我们采用其他方案&#xff0c;即通过OCR识别获取歌词&#xff0c;并投射到LED显示屏上…...

JAVA学习(6)-全网最详细~

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…...

睿趣科技:未来抖音开网店还有前景吗

随着科技的快速发展&#xff0c;电商平台已经成为了人们生活中不可或缺的一部分。在中国&#xff0c;抖音作为一个短视频平台&#xff0c;近年来迅速崛起&#xff0c;吸引了大量的用户和商家。那么&#xff0c;在未来&#xff0c;抖音是否还能为商家提供一个有效的电商平台呢?…...

第六章 应用层 | 计算机网络(谢希仁 第八版)

文章目录 第六章 应用层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&#xff08;匿名函数&#xff09;是C11引入的一种函数对象&#xff0c;它允许我们在需要函数的地方创建一个临时的、匿名的函数。lambda表达式表示一个可以执行的代码单元&#xff0c;可以理解为一个未命名的内联函数。Lambda函数可以用于简化代码、提高可读性…...

Go语言入门心法(七): 并发与通道

Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言并发与通道...

前端组件封装:构建模块化、可维护和可重用的前端应用

前端组件封装&#xff1a;构建模块化、可维护和可重用的前端应用 前端开发领域的快速演进已经将前端应用的规模和复杂性提升到了一个新的水平。在这个背景下&#xff0c;前端组件封装成为了一项关键实践&#xff0c;旨在构建模块化、可维护和可重用的前端应用。在本文中&#…...

GPT绘制流程图咒语

【咒语】下面是我的一篇论文选取部分&#xff0c;为了让读者更好理解&#xff0c;我准备画一张图&#xff0c;请你阅读后为我设计一下这个图应该怎么画&#xff0c;更有说服力&#xff0c;更容易理解 论文片段&#xff1a; 多模态数据融合研究的基础在于有效的数据采集。首先&a…...

【扩散模型从原理到实战】Chapter1 扩散模型简介

文章目录 1.1 扩散模型的原理生成模型扩散过程DDPM的扩散过程前向过程反向过程优化目标 1.2 扩散模型的发展开始扩散&#xff1a;DDPM加速生成&#xff1a;采样器刷新记录&#xff1a;基于CLIP的多模态图像生成引爆网络&#xff1a;基于CLIP的多模态图像生成再次“出圈”&#…...

使用轮廓分数提升时间序列聚类的表现

我们将使用轮廓分数和一些距离指标来执行时间序列聚类实验&#xff0c;并且进行可视化 让我们看看下面的时间序列: 如果沿着y轴移动序列添加随机噪声&#xff0c;并随机化这些序列&#xff0c;那么它们几乎无法分辨&#xff0c;如下图所示-现在很难将时间序列列分组为簇: 上面…...

蔬菜水果生鲜配送团购商城小程序的作用是什么

蔬菜水果是人们生活所需品&#xff0c;从业者众多&#xff0c;无论小摊贩还是超市商场都有不少人每天光临&#xff0c;当然这些只是自然流量&#xff0c;在实际经营中&#xff0c;蔬菜水果商家还是面临着一些难题。 对蔬菜水果商家而言&#xff0c;线下门店是重要的&#xff0…...

金融用户实践|分布式存储支持数据仓库业务系统性能验证

作者&#xff1a;深耕行业的 SmartX 金融团队 闫海涛 估值是指对资产或负债的价值进行评估的过程&#xff0c;这对于投资决策具有重要意义。每个金融公司资管业务人员都期望能够实现实时的业务估值&#xff0c;快速获取最新的数据和指标&#xff0c;从而做出更明智的投资决策。…...

代码随想录二刷 Day41

509. 斐波那契数 这个题简单入门&#xff0c;注意下N小于等于1的情况就可以 class Solution { public:int fib(int n) {if (n < 1) return n; //这句不写的话test能过但是另外的过不了vector<int> result(n 1); //定义存放dp结果的数组&#xff0c;还要定义大小r…...

C++项目实战——基于多设计模式下的同步异步日志系统-⑪-日志器管理类与全局建造者类设计(单例模式)

文章目录 专栏导读日志器建造者类完善单例日志器管理类设计思想单例日志器管理类设计全局建造者类设计日志器类、建造者类整理日志器管理类测试 专栏导读 &#x1f338;作者简介&#xff1a;花想云 &#xff0c;在读本科生一枚&#xff0c;C/C领域新星创作者&#xff0c;新星计…...

Hadoop3教程(十四):MapReduce中的排序

文章目录 &#xff08;99&#xff09;WritableComparable排序什么是排序什么时候需要排序排序有哪些分类如何实现自定义排序 &#xff08;100&#xff09;全排序案例案例需求思路分析实际代码 &#xff08;101&#xff09;二次排序案例&#xff08;102&#xff09; 区内排序案例…...

测试需要写测试用例吗?

如何理解软件的质量 我们都知道&#xff0c;一个软件从无到有要经过需求设计、编码实现、测试验证、部署发布这四个主要环节。 需求来源于用户反馈、市场调研或者商业判断。意指在市场行为中&#xff0c;部分人群存在某些诉求或痛点&#xff0c;只要想办法满足这些人群的诉求…...

Qt 视口和窗口的区别

视口和窗口 绘图设备的物理坐标是基本的坐标系&#xff0c;通过QPainter的平移、旋转等变换可以得到更容易操作的逻辑坐标 为了实现更方便的坐标&#xff0c;QPainter还提供了视口(Viewport)和窗口(Window)坐标系&#xff0c;通过QPainter内部的坐标变换矩阵自动转换为绘图设…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...