LeetCode 232. 用栈实现队列
LeetCode 232. 用栈实现队列
难度:easy\color{Green}{easy}easy
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpushpush、poppoppop、peekpeekpeek、emptyemptyempty):
实现 MyQueueMyQueueMyQueue 类:
- voidpush(intx)void push(int x)voidpush(intx) 将元素 x 推到队列的末尾
- intpop()int pop()intpop() 从队列的开头移除并返回元素
- intpeek()int peek()intpeek() 返回队列开头的元素
- booleanempty()boolean empty()booleanempty() 如果队列为空,返回 truetruetrue ;否则,返回 falsefalsefalse
说明:
- 你 只能 使用标准的栈操作 —— 也就是只有 pushtotoppush to toppushtotop, peek/popfromtoppeek/pop from toppeek/popfromtop, sizesizesize, 和 isemptyis emptyisempty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 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<=91 <= x <= 91<=x<=9
- 最多调用 100100100 次 pushpushpush、poppoppop、peekpeekpeek 和 emptyemptyempty
- 假设所有操作都是有效的 (例如,一个空的队列不会调用 poppoppop 或者 peekpeekpeek 操作)
进阶:
- 你能否实现每个操作均摊时间复杂度为 O(1)O(1)O(1) 的队列?换句话说,执行 nnn 个操作的总时间复杂度为 O(n)O(n)O(n) ,即使其中一个操作可能花费较长时间。
算法
(栈,队列)
我们用一个栈来存储队列中的元素,另外还需要一个辅助栈,用来辅助实现 pop() 和 peek() 操作。
四种操作的实现方式如下:
push(x)– 直接将x插入栈顶;pop()– 即需要弹出栈底元素,我们先将栈底以上的所有元素插入辅助栈中,然后弹出栈底元素,最后再将辅助栈中的元素重新压入当前栈中;peek()– 返回栈顶元素,同理,我们先将栈底以上的所有元素插入辅助栈中,然后输出栈底元素,最后再将辅助栈中的元素重新压入当前栈中,恢复当前栈原状;empty()– 返回当前栈是否为空;
复杂度分析
-
时间复杂度:
push(x)和emtpy()均只有一次操作,时间复杂度是 O(1)O(1)O(1),pop()和peek()涉及到 nnn 次操作,所以时间复杂度是 O(n)O(n)O(n) -
空间复杂度 : O(n)O(n)O(n)
C++ 代码
class MyQueue {
public:stack<int> stk1;stack<int> stk2;MyQueue() {}void push(int x) {stk1.push(x);}int pop() {while (stk1.size() > 1) {int t = stk1.top();stk1.pop();stk2.push(t);}int ans = stk1.top();stk1.pop();while (stk2.size()) {stk1.push(stk2.top());stk2.pop();}return ans;}int peek() {while (stk1.size() > 1) {int t = stk1.top();stk1.pop();stk2.push(t);}int ans = stk1.top();while (stk2.size()) {stk1.push(stk2.top());stk2.pop();}return ans;}bool empty() {if (stk1.empty()) return true;return false;}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/
相关文章:
LeetCode 232. 用栈实现队列
LeetCode 232. 用栈实现队列 难度:easy\color{Green}{easy}easy 题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpushpush、poppoppop、peekpeekpeek、emptyemptyempty): 实现 MyQueueM…...
AI算法创新赛-人车目标检测竞赛总结04
队伍:AI000038 小组成员:杨志强,林松 1. 算法介绍 1.1 相关工作 当前流行的目标检测算法主要分为三种,一阶段算法:SSD,FCOS,Scaled,YOLO系列等;二阶段算法:…...
【C语言进阶】动态内存管理详解与常见动态内存错误以及柔性数组使用与介绍
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:C语言进阶 🎯长路漫漫浩浩,万事皆有期待 文章目录1.动态内存1.1 概述…...
【C++】string的模拟实现
文章目录1. string的模拟实现1.构造函数使用new开辟空间优化成全缺省的构造函数2. C_str3. operator[]4.拷贝构造浅拷贝深拷贝5. 赋值三种情况6. 迭代器7.比较(ASCII值)大小8. reserve(扩容)9. push_back(尾插字符)10. append(尾插字符串)11. (字符/字符串)12. insert在pos位置…...
前端借助Canvas实现压缩base64图片两种方法
一、具体代码 1、利用canvas压缩图片方法一 // 第一种压缩图片方法(图片base64,图片类型,压缩比例,回调函数)// 图片类型是指 image/png、image/jpeg、image/webp(仅Chrome支持)// 该方法对以上三种图片类型都适用 压缩结果的图片base64与原类型相同// …...
用ChatGPT生成Excel公式,太方便了
ChatGPT 自去年 11 月 30 日 OpenAI 重磅推出以来,这款 AI 聊天机器人迅速成为 AI 界的「当红炸子鸡」。一经发布,不少网友更是痴迷到通宵熬夜和它对话聊天,就为了探究 ChatGPT 的应用天花板在哪里,经过试探不少人发现,…...
【Kubernetes 企业项目实战】09、Rancher 2.6 管理 k8s-v1.23 及以上版本高可用集群
目录 一、Rancher 介绍 1.1Rancher简介 1.2 Rancher 和 k8s 的区别 1.3 Rancher 企业使用案例 二、安装 Rancher 2.1 初始化环境 2.2 安装 Rancher 2.3 登录 Rancher 平台 三、通过 Rancher 管理已存在的 k8s 集群 3.1 配置 rancher 3.2 导入 k8s 四、通过 Ranc…...
在Excel中按条件筛选数据并存入新的表
案例 老板想要看去年每月领料数量大于1000的数据。手动筛选并复制粘贴出来,需要重复操作12次,实在太麻烦了,还是让Python来做吧。磨刀不误砍柴工,先整理一下思路: 1读取原表,将数量大于1000的数据所对应的行整行提取(如同在excel表中按数字筛选大于1000的) 2将提取的数…...
【面试题】MySQL索引相关知识点
1.什么是索引 索引是存储引擎快速查找记录的一种数据结构,就类似书的目录,通过目录可以快速的查找到想要查找的内容 2.索引的特点 特点:索引是基于数据引擎的,不同的数据引擎实现索引的方式不一定相同 好处:通过索引…...
MySQL索引类型及原理?一文读懂
一、什么是MySQL索引? MySQL索引是一种数据结构,用于提高数据库查询的性能。它类似于一本书的目录,通过在表中存储指向数据行的引用,使得查询数据的速度更快。 在MySQL中,索引通常是在表上定义的,它们可以…...
【C语言】字符分类函数+内存函数
目录 1.字符函数 1.1字符分类函数 1.2.字符转换函数 //统一字符串中的大小写 2.内存处理函数 2.1内存拷贝函数memcpy //模拟实现memcpy 2.2内存移动函数memmove //模拟实现memmove 2.3内存比较函数memcmp 2.4内存设置函数memset 1.字符函数 1.1字符分类函数 头文…...
高通平台开发系列讲解(SIM卡篇)SIM卡基础概念
文章目录 一、SIM卡基本定义二、卡的类型三、SIM卡的作用三、SIM卡基本硬件结构四、SIM卡的内部物理单元五、卡文件系统沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇文章将介绍SIM的相关组件。 一、SIM卡基本定义 SIM卡是一种智能卡(ICC Card/UICC Card) SIM…...
记录一次ubuntu下配置ssh登录出现的问题
现象描述: 1. 配置完服务器端公钥和本地的私钥之后,ssh登录始终会让输入密码,用ssh -vvv rootip 查看发现发送密钥之后就没反应了。 本机debug info: debug1: Trying private key: C:\Users\wangc/.ssh/id_xxxx (私钥文件) debug3…...
深度剖析数据在内存中的存储(下)(适合初学者)
上篇讲解了整形在内存中的存储方式,这篇文章就来继续讲解浮点数在内存中的存储方式。 上篇地址: (5条消息) 深度剖析数据在内存中的存储(上)_陈大大陈的博客-CSDN博客 目录: 3.浮点型在内存中的存储 3.1.浮点数的…...
智慧物联网系统源码:一个用于数据的收集、处理、可视化、设备管理、设备预警、报警的平台
项目简介: 一个用于数据的收集、处理、可视化、设备管理、设备预警、报警的平台,通过平台将所有设备连接起来,为上层应用提供设备的管理、数据收集、远程控制等核心物联网功能。 支持支持远程对设备进行实时监控、故障排查、远程控制&#…...
2023年,拥有软考证书在这些地区可以领取福利补贴
众所周知,软考的含金量很高,比如可以入户、领取技能补贴、抵扣个税、以考代评、招投标加分,入专家库… 今天小编给大家收集了拥有软考证书可以领取软考福利的地区,希望对大家有所帮助! 【深圳】 入户 ①核准类入户:…...
使用Unity在材质球上实现绘画:详细解释每一行Shader代码!
在Unity中实现在材质球上绘画可以使用下面这个步骤:创建一个基础的材质球:在Unity的项目面板中创建一个新材质球,然后将其分配给您要绘画的对象。创建一个Shader:为了实现在材质球上绘画,您需要使用一种特殊的Shader。…...
Tesseract 4.0训练字库并且识别训练后的图片
各个工具下载链接在文章底部! 重要!!自己先创建一个空文件夹(名字随意),用来保存训练后的模型 ,还需要在里面创建一个 名称为tessdata 的文件夹 ,必须叫这个名 可以先使用下载后的进行测试训练(只需要把ja…...
ChatGPT热潮背后,金融行业大模型应用路在何方?——金融行业大模型应用探索
ChatGPT近两个月以来不断引爆热点,对人工智能应用发展的热潮前所未有地高涨,ChatGPT所代表的大模型在语义理解、多轮交互、内容生成中所展现的突出能力令人惊喜。而人工智能技术在金融行业的落地应用仍然面临挑战,虽然已经让大量宝贵的人力从…...
【怎么预防sql注入,以及还有预防其他的什么网络攻击】
SQL注入是一种常见的Web攻击,通过在Web应用程序中注入恶意SQL语句来获取或修改数据库中的数据。为了防止SQL注入,开发者可以采取以下措施: 1、使用参数化查询(Prepared Statement)或存储过程(Stored Proce…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
