LeetCode-232. 用栈实现队列(C++)
目录捏
- 一、题目描述
- 二、示例与提示
- 三、思路
- 四、代码
一、题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
实现 MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
说明:
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
二、示例与提示
示例 1:
输入:
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]
解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示
1 <= x <= 9
- 最多调用 100 次
push
、pop
、peek
和empty
- 假设所有操作都是有效的 (例如,一个空的队列不会调用
pop
或者peek
操作)
进阶:
- 你能否实现每个操作均摊时间复杂度为
O(1)
的队列?换句话说,执行n
个操作的总时间复杂度为O(n)
,即使其中一个操作可能花费较长时间。
三、思路
本题要使用栈来实现队列,所以需要先了解栈和队列分别有什么特性。
栈:先进后出;队列:先进先出
所以,要使用栈来模式队列的行为,如果仅仅用一个栈,是一定不行的,所以需要两个栈一个输入栈,一个输出栈,这里要注意输入栈和输出栈的关系。
在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意:全部导入),再从输出栈弹出数据,如果输出栈不为空,则直接从输出栈弹出数据就可以了。
最后如何判断队列为空呢?如果进栈和出栈都为空的话,说明模拟的队列为空了。
在代码实现的时候,会发现 pop() 和 peek() 两个函数功能类似,代码实现上也是类似的,所以我们可以思考一下如何把代码抽象一下。
我们在实现 peek() 函数时可以直接复用 pop() 函数,只不过最后需要把弹出的值再push进去。
四、代码
class MyQueue {
public:stack<int>stIn; // 定义输入栈stack<int>stOut; // 定义输出栈MyQueue() {}void push(int x) {stIn.push(x);}int pop() {// 分两种情况讨论:输出栈为空、输出栈不为空if(stOut.empty()) {// 只有当stOut为空的时候,再从stIn里导入数据(导入stIn全部数据)while(!stIn.empty()) {// 从stIn导入数据直到stIn为空stOut.push(stIn.top());stIn.pop();}}int res = stOut.top();stOut.pop();return res;}int peek() {int res = this->pop(); // 此处直接复用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res,所以再push回去return res;}bool empty() {// 如果进栈和出栈都为空的话,说明模拟的队列为空return stIn.empty()&&stOut.empty();}
};
复杂度分析
时间复杂度: push和empty为O(1), pop和peek为O(n)
相关文章:
LeetCode-232. 用栈实现队列(C++)
目录捏 一、题目描述二、示例与提示三、思路四、代码 一、题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的…...

无人机红外相机的畸变矫正
在项目开展过程中,发现大疆M30T的红外相机存在比较明显的畸变问题,因此需要对红外图像进行畸变矫正。在资料检索过程中,发现对红外无人机影像矫正的资料较少,对此,我从相机的成像原理角度出发,探索出一种效…...

C++编程案例讲解-基于结构体的控制台通讯录管理系统
基于结构体的控制台通讯录管理系统 通讯录是一个可以记录亲人、好友信息的工具,系统中需要实现的功能如下: 添加联系人:向通讯录中添加新人,信息包括(姓名、性别、年龄、联系电话、家庭住址)最多记录1000人…...

ASP.NETCore6开启文件服务允许通过url访问附件(图片)
需求背景 最近在做一个工作台的文件上传下载功能,主要想实现上传图片之后,可以通过url直接访问。由于url直接访问文件不安全,所以需要手动开启文件服务。 配置 文件路径如下,其中Files是存放文件的目录: 那么&…...

python爬取Web of science论文信息
一、python爬取WOS总体思路 (一)拟实现功能描述 wos里面,爬取论文的名称,作者名称,作者单位,引用数量 要求:英文论文、期刊无论好坏 检索关键词:zhejiang academy of agricultural sciences、 xianghu lab…...

本地域名 127.0.0.1 / localhost
所谓本地域名就是 只能在本机使用的域名 ,一般在开发阶段使用。 编辑文件 C:\Windows\System32\drivers\etc\hosts。 127.0.0.1 www.baidu.com如果修改失败,可以修改该文件的权限。 原理: 在地址栏输入 域名 之后,浏览器会先进行 DNS…...
Python —— 不同类型的数据长度计算方式
在Python 中,不同类型的数据长度计算方式,有何不同👇 字符串(String) my_string "Hello, World!" string_length len(my_string) print("字符串的长度是:", string_length) //输出…...

NowCoder | 环形链表的约瑟夫问题
NowCoder | 环形链表的约瑟夫问题 OJ链接 思路: 创建带环链表带环链表的删除节点 代码如下: #include<stdlib.h>typedef struct ListNode ListNode; ListNode* ListBuyNode(int x) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node…...
华为政企数据中心网络交换机产品集
产品类型产品型号产品说明 核心/汇聚交换机CE8850-EI-B-B0BCloudEngine 8850-64CQ-EI 提供 64 x 100 GE QSFP28,CloudEngine 8800系列交换机是面向数据中心推出的新一代高性能、高密度、低时延灵活插卡以太网交换机,可以与华为CloudEngine系列数据中心…...

多门店自助点餐+外卖二合一小程序源码系统 带完整搭建教程
随着餐饮业的快速发展和互联网技术的不断进步,越来越多的餐厅开始采用自助点餐和外卖服务。市场上许多的外卖小程序APP应运而生。下面罗峰来给大家介绍一款多门店自助点餐外卖二合一小程序源码系统。该系统结合了自助点餐和外卖服务的优势,为餐厅提供了一…...

kafka可视化工具
Offset Explorer kafka可视化工具...

Excel 转 Json 、Node.js实现(应用场景:i18n国际化)
创作灵感来源于在线转换是按照换行符去转换excel内容换行符后很难处理 本文是按单元格转换 const xlsx require(node-xlsx) const fs require(fs) const xlsxData xlsx.parse(./demo.xlsx) // 需要转换的excel文件// 数据处理 方便粘贴复制 const data xlsxData[2].data …...

Redis7--基础篇2(Redis的十大数据类型及常用命令)
1. Redis的十大数据类型及常用命令 Redis是key-value键值对类型的数据库,我们所说的数据类型指的是value的数据类型,key的数据类型都是字符串。 1.1 字符串(String) string是redis最基本的类型,一个key对应一个val…...
1.HTML中网页介绍
1.网页 1.1 什么是网页 网站是指在因特网上根据一定的规则,使用HTML等制作的用于展示特定内容的相关的网页集合 网页是网站中的一“页”,通常是HTML格式文件,它要通过浏览器来阅读。 网页是构成网站的基本元素,它通常是有图片&am…...

执行sql报错only_full_group_by的解决方法
一、前言 最近老项目换新数据库(都是mysql),有些在老数据库可以执行的sql,在新数据库执行就会报错sql_modeonly_full_group_by 意思是说数据库的模式是sql_modeonly_full_group_by,group by的字段必须和查询字段一致…...

不学51直接学stm32可以吗?学stm32需要哪些基础?
不学51直接学stm32可以吗?学stm32需要哪些基础? 不管那些大佬技术多么牛逼,大多数入门都是从51单片机开始。 最近有一些入门的小伙伴问我说看到同学都从直接从STM32开始干了。最近很多小伙伴找我,说想要一些stm32的资料ÿ…...

6.1二叉树的递归遍历(LC144,LC15,LC94)
什么是递归函数? 递归函数是一种函数调用自身的编程技巧。 在递归函数中,函数通过不断调用自身来解决一个问题,直到达到基本情况(递归终止条件)并返回结果。 递归函数在解决一些问题时非常有用,特别是那些…...

Spring基础(3):复习
为了让大家更容易接受我的一些观点,上一篇很多笔墨都用在了思路引导上,所以导致文章可能比较臃肿。 这一篇来总结一下,会稍微精简一些,但整体趣味性不如第二篇。 (上一篇说过了,目前介绍的2种注入方式的说法其实不够…...

Java-Hbase介绍
1.1. 概念 base 是分布式、面向列的开源数据库(其实准确的说是面向列族)。HDFS 为 Hbase 提供可靠的 底层数据存储服务,MapReduce 为 Hbase 提供高性能的计算能力,Zookeeper 为 Hbase 提供 稳定服务和 Failover 机制,…...
【PHP】【Too few arguments to function Firebase\JWT\JWT::encode()。。。。。。。】
1.安装jwt composer require firebase/php-jwtuse Firebase\JWT\JWT;public function hello($name ThinkPHP5){$secret_key "YOUR_SECRET_KEY";$issuer_claim "THE_ISSUER";$audience_claim "THE_AUDIENCE";$issuedat_claim time(); // is…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...

Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...