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

LeetCode 232. 用栈实现队列

LeetCode 232. 用栈实现队列

难度:easy\color{Green}{easy}easy


题目描述

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

实现 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
  • 最多调用 100100100pushpushpushpoppoppoppeekpeekpeekemptyemptyempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 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. 用栈实现队列 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;pushpushpush、poppoppop、peekpeekpeek、emptyemptyempty&#xff09;&#xff1a; 实现 MyQueueM…...

AI算法创新赛-人车目标检测竞赛总结04

队伍&#xff1a;AI000038 小组成员&#xff1a;杨志强&#xff0c;林松 1. 算法介绍 1.1 相关工作 当前流行的目标检测算法主要分为三种&#xff0c;一阶段算法&#xff1a;SSD&#xff0c;FCOS&#xff0c;Scaled&#xff0c;YOLO系列等&#xff1b;二阶段算法&#xff1a…...

【C语言进阶】动态内存管理详解与常见动态内存错误以及柔性数组使用与介绍

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;C语言进阶 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录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压缩图片方法一 // 第一种压缩图片方法&#xff08;图片base64,图片类型,压缩比例,回调函数&#xff09;// 图片类型是指 image/png、image/jpeg、image/webp(仅Chrome支持)// 该方法对以上三种图片类型都适用 压缩结果的图片base64与原类型相同// …...

用ChatGPT生成Excel公式,太方便了

ChatGPT 自去年 11 月 30 日 OpenAI 重磅推出以来&#xff0c;这款 AI 聊天机器人迅速成为 AI 界的「当红炸子鸡」。一经发布&#xff0c;不少网友更是痴迷到通宵熬夜和它对话聊天&#xff0c;就为了探究 ChatGPT 的应用天花板在哪里&#xff0c;经过试探不少人发现&#xff0c…...

【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.什么是索引 索引是存储引擎快速查找记录的一种数据结构&#xff0c;就类似书的目录&#xff0c;通过目录可以快速的查找到想要查找的内容 2.索引的特点 特点&#xff1a;索引是基于数据引擎的&#xff0c;不同的数据引擎实现索引的方式不一定相同 好处&#xff1a;通过索引…...

MySQL索引类型及原理?一文读懂

一、什么是MySQL索引&#xff1f; MySQL索引是一种数据结构&#xff0c;用于提高数据库查询的性能。它类似于一本书的目录&#xff0c;通过在表中存储指向数据行的引用&#xff0c;使得查询数据的速度更快。 在MySQL中&#xff0c;索引通常是在表上定义的&#xff0c;它们可以…...

【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. 配置完服务器端公钥和本地的私钥之后&#xff0c;ssh登录始终会让输入密码&#xff0c;用ssh -vvv rootip 查看发现发送密钥之后就没反应了。 本机debug info: debug1: Trying private key: C:\Users\wangc/.ssh/id_xxxx &#xff08;私钥文件&#xff09; debug3…...

深度剖析数据在内存中的存储(下)(适合初学者)

上篇讲解了整形在内存中的存储方式&#xff0c;这篇文章就来继续讲解浮点数在内存中的存储方式。 上篇地址&#xff1a; (5条消息) 深度剖析数据在内存中的存储&#xff08;上&#xff09;_陈大大陈的博客-CSDN博客 目录&#xff1a; 3.浮点型在内存中的存储 3.1.浮点数的…...

智慧物联网系统源码:一个用于数据的收集、处理、可视化、设备管理、设备预警、报警的平台

项目简介&#xff1a; 一个用于数据的收集、处理、可视化、设备管理、设备预警、报警的平台&#xff0c;通过平台将所有设备连接起来&#xff0c;为上层应用提供设备的管理、数据收集、远程控制等核心物联网功能。 支持支持远程对设备进行实时监控、故障排查、远程控制&#…...

2023年,拥有软考证书在这些地区可以领取福利补贴

众所周知&#xff0c;软考的含金量很高&#xff0c;比如可以入户、领取技能补贴、抵扣个税、以考代评、招投标加分&#xff0c;入专家库… 今天小编给大家收集了拥有软考证书可以领取软考福利的地区&#xff0c;希望对大家有所帮助&#xff01; 【深圳】 入户 ①核准类入户:…...

使用Unity在材质球上实现绘画:详细解释每一行Shader代码!

在Unity中实现在材质球上绘画可以使用下面这个步骤&#xff1a;创建一个基础的材质球&#xff1a;在Unity的项目面板中创建一个新材质球&#xff0c;然后将其分配给您要绘画的对象。创建一个Shader&#xff1a;为了实现在材质球上绘画&#xff0c;您需要使用一种特殊的Shader。…...

Tesseract 4.0训练字库并且识别训练后的图片

各个工具下载链接在文章底部&#xff01; 重要&#xff01;&#xff01;自己先创建一个空文件夹(名字随意)&#xff0c;用来保存训练后的模型 ,还需要在里面创建一个 名称为tessdata 的文件夹 &#xff0c;必须叫这个名 可以先使用下载后的进行测试训练&#xff08;只需要把ja…...

ChatGPT热潮背后,金融行业大模型应用路在何方?——金融行业大模型应用探索

ChatGPT近两个月以来不断引爆热点&#xff0c;对人工智能应用发展的热潮前所未有地高涨&#xff0c;ChatGPT所代表的大模型在语义理解、多轮交互、内容生成中所展现的突出能力令人惊喜。而人工智能技术在金融行业的落地应用仍然面临挑战&#xff0c;虽然已经让大量宝贵的人力从…...

【怎么预防sql注入,以及还有预防其他的什么网络攻击】

SQL注入是一种常见的Web攻击&#xff0c;通过在Web应用程序中注入恶意SQL语句来获取或修改数据库中的数据。为了防止SQL注入&#xff0c;开发者可以采取以下措施&#xff1a; 1、使用参数化查询&#xff08;Prepared Statement&#xff09;或存储过程&#xff08;Stored Proce…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...