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…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...