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

LeetCode-232. 用栈实现队列(C++)

目录捏

  • 一、题目描述
  • 二、示例与提示
  • 三、思路
  • 四、代码


一、题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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 次 pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 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++)

目录捏 一、题目描述二、示例与提示三、思路四、代码 一、题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xff1a; 实现 MyQueue 类&#xff1a; void push(int x) 将元素 x 推到队列的…...

无人机红外相机的畸变矫正

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

C++编程案例讲解-基于结构体的控制台通讯录管理系统

基于结构体的控制台通讯录管理系统 通讯录是一个可以记录亲人、好友信息的工具&#xff0c;系统中需要实现的功能如下&#xff1a; 添加联系人&#xff1a;向通讯录中添加新人&#xff0c;信息包括&#xff08;姓名、性别、年龄、联系电话、家庭住址&#xff09;最多记录1000人…...

ASP.NETCore6开启文件服务允许通过url访问附件(图片)

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

python爬取Web of science论文信息

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

本地域名 127.0.0.1 / localhost

所谓本地域名就是 只能在本机使用的域名 &#xff0c;一般在开发阶段使用。 编辑文件 C:\Windows\System32\drivers\etc\hosts。 127.0.0.1 www.baidu.com如果修改失败,可以修改该文件的权限。 原理&#xff1a; 在地址栏输入 域名 之后&#xff0c;浏览器会先进行 DNS…...

Python —— 不同类型的数据长度计算方式

在Python 中&#xff0c;不同类型的数据长度计算方式&#xff0c;有何不同&#x1f447; 字符串&#xff08;String&#xff09; my_string "Hello, World!" string_length len(my_string) print("字符串的长度是&#xff1a;", string_length) //输出…...

NowCoder | 环形链表的约瑟夫问题

NowCoder | 环形链表的约瑟夫问题 OJ链接 思路&#xff1a; 创建带环链表带环链表的删除节点 代码如下&#xff1a; #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&#xff0c;CloudEngine 8800系列交换机是面向数据中心推出的新一代高性能、高密度、低时延灵活插卡以太网交换机&#xff0c;可以与华为CloudEngine系列数据中心…...

多门店自助点餐+外卖二合一小程序源码系统 带完整搭建教程

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

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键值对类型的数据库&#xff0c;我们所说的数据类型指的是value的数据类型&#xff0c;key的数据类型都是字符串。 1.1 字符串&#xff08;String&#xff09; string是redis最基本的类型&#xff0c;一个key对应一个val…...

1.HTML中网页介绍

1.网页 1.1 什么是网页 网站是指在因特网上根据一定的规则&#xff0c;使用HTML等制作的用于展示特定内容的相关的网页集合 网页是网站中的一“页”&#xff0c;通常是HTML格式文件&#xff0c;它要通过浏览器来阅读。 网页是构成网站的基本元素&#xff0c;它通常是有图片&am…...

执行sql报错only_full_group_by的解决方法

一、前言 最近老项目换新数据库&#xff08;都是mysql&#xff09;&#xff0c;有些在老数据库可以执行的sql&#xff0c;在新数据库执行就会报错sql_modeonly_full_group_by 意思是说数据库的模式是sql_modeonly_full_group_by&#xff0c;group by的字段必须和查询字段一致…...

不学51直接学stm32可以吗?学stm32需要哪些基础?

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

6.1二叉树的递归遍历(LC144,LC15,LC94)

什么是递归函数&#xff1f; 递归函数是一种函数调用自身的编程技巧。 在递归函数中&#xff0c;函数通过不断调用自身来解决一个问题&#xff0c;直到达到基本情况&#xff08;递归终止条件&#xff09;并返回结果。 递归函数在解决一些问题时非常有用&#xff0c;特别是那些…...

Spring基础(3):复习

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

Java-Hbase介绍

1.1. 概念 base 是分布式、面向列的开源数据库&#xff08;其实准确的说是面向列族&#xff09;。HDFS 为 Hbase 提供可靠的 底层数据存储服务&#xff0c;MapReduce 为 Hbase 提供高性能的计算能力&#xff0c;Zookeeper 为 Hbase 提供 稳定服务和 Failover 机制&#xff0c…...

【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…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...