【LeetCode】No.232. 用栈实现队列 -- Java Version

news/2024/3/28 16:38:56/文章来源:https://blog.csdn.net/qq_41071754/article/details/129123078

题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/

1. 题目介绍(232. 用栈实现队列)

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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) ,即使其中一个操作可能花费较长时间。

2. 题解

相同题目:【LeetCode】剑指 Offer 09. 用两个栈实现队列 p68 – Java Version
相似题目:【LeetCode】No.225. 用队列实现栈 – Java Version

2.1 用两个栈实现队列 – O(1)

时间复杂度O(1),空间复杂度O(n)

class MyQueue {// 1. 定义两个栈对象private Stack<Integer> stack1;private Stack<Integer> stack2;// 2. 构造方法创建栈对象public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}// 3. 入栈方法(直接进stack1)public void push(int x) {stack1.push(x);}// 4. 出栈方法(stack2不空,直接返回栈顶)//    stack2空,判断stack1空不空,然后把stack1中元素压入stack2public int pop() {if (!stack2.empty()) return stack2.pop();else {while (!stack1.empty()){stack2.push(stack1.pop());}return stack2.empty() ? -1 : stack2.pop();}}// 5. 返回栈顶元素方法,内容大致同4public int peek() {if (!stack2.empty()) return stack2.peek();else {while (!stack1.empty()){stack2.push(stack1.pop());}return stack2.empty() ? -1 : stack2.peek();}}// 6. 判空方法,stack1和stack2同时为空则为空public boolean empty() {if (stack1.empty() && stack2.empty()) return true;else 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();* boolean param_4 = obj.empty();*/

在这里插入图片描述

3. 参考资料

[1] 用栈实现队列(官方题解)
[2] 【LeetCode】剑指 Offer 09. 用两个栈实现队列 p68 – Java Version (相同题目)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_71676.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【前端】小程序开发入门:安装开发工具、目录结构与项目配置

文章目录前期准备目录结构app.jsonpageswindow其他前期准备 开发小程序要先申请一个对应的AppID&#xff1a;微信小程序 (qq.com) 微信官方小程序开发文档&#xff1a;微信开放文档 (qq.com) 然后安装一个小程序开发工具&#xff1a; 选择稳定版&#xff1a; 安装后打开&…

如何在SpringBoot项目上让接口返回数据脱敏,一个注解即可

1 背景需求是某些接口返回的信息&#xff0c;涉及到敏感数据的必须进行脱敏操作2 思路①要做成可配置多策略的脱敏操作&#xff0c;要不然一个个接口进行脱敏操作&#xff0c;重复的工作量太多&#xff0c;很显然违背了“多写一行算我输”的程序员规范。思来想去&#xff0c;定…

【linux】——gcc/g++,make/makefile的简单使用

目录 1.gcc的基本使用 2.Linux下的静态库和动态库的理解 3.Linux项目自动化构建工具——make/makefile 1.gcc的基本使用 gcc是专门用来编译c语言的 g是专门用来编译c的&#xff0c;但是g也能够用来编译c语言 预处理&#xff08;进行宏替换&#xff09; 预处理功能主要包括宏…

【前端提效】-- VsCode 实用插件推荐

EditorConfig for VS Code ***** 作用&#xff1a;多人协同开发&#xff0c;规范缩进风格&#xff0c;缩进大小&#xff0c;tab长度以及字符集等&#xff0c;解决不同IDE的编码范设置&#xff0c;在这里配置&#xff08;.editorconfig&#xff09;的代码规范规则优先级高于编辑…

java诊断与调优常用命令jmap、jstack、jstat使用实战

java应用运行过程中难免会出现问题&#xff0c;特别是在生产环境&#xff0c;发生异常或宕机情况&#xff0c;需要诊断与分析&#xff0c;定位原因&#xff0c;进行优化&#xff0c;避免下次再次出现问题。 虽然现在有很多可视化工具&#xff0c;使用起来比命令行更方便&#x…

Julia 语言环境安装

Julia 语言支持以下系统&#xff1a; LinuxFreeBSDmacOSWindowsAndroid Julia 安装包下载地址为&#xff1a;Download Julia。 Github 源码地址&#xff1a;GitHub - JuliaLang/julia: The Julia Programming Language。 国内镜像地址&#xff1a;Index of /julia-releases/…

逻辑回归—二元分类问题的操作顺序

对于二元分类问题来说&#xff0c;分类的结果和数据的特征之间仍呈现相关关系&#xff0c;但是y的值不再是连续的&#xff0c;是0&#xff5e;1的跃迁。但是在这个过程中&#xff0c;什么仍然是连续的呢&#xff1f;”是概率&#xff0c;概率是逐渐升高的&#xff0c;当达到一个…

AI制药 - TMScore(US-align)、RMSD、Sequence 源码

欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://blog.csdn.net/caroline_wendy/article/details/129125467 参考文档:Nature Methods | 蛋白、RNA、DNA及其复合物结构的比对算法US-align 官网地址:https://zhanggroup.org/US-align/ TMScore TMScore,…

文件系统与动静态库的基本了解

目录文件系统与动静态库的基本了解文件系统了解Access Modify Changeinode硬链接软链接静态库与动态库概念静态库的制作使用静态库动态库的制作使用动态库总结如何制作文件系统与动静态库的基本了解 文件系统 了解Access Modify Change 当文件没有被打开时&#xff0c;他们存…

数据挖掘,计算机网络、操作系统刷题笔记50

数据挖掘&#xff0c;计算机网络、操作系统刷题笔记50 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;可能很多算法学生都得去找开发&#xff0c;测开 测开的话&#xff0c;你就得学数据库&#xff0c;sql&#xff0c;orac…

(考研湖科大教书匠计算机网络)第五章传输层-第八节1:TCP连接管理理论部分(三次握手与四次挥手)

获取pdf&#xff1a;密码7281专栏目录首页&#xff1a;【专栏必读】考研湖科大教书匠计算机网络笔记导航此部分内容借鉴博主【小林coding】 &#xff0c;其对计算机网络内容的图解可以说是深入浅出&#xff0c;尤其是三次握手和四次挥手这一部分&#xff0c;堪称全网最佳。所这…

webpack5打包工具的使用

目录 -----------------------------基础篇------------------------------- 一、为什么需要打包工具 二、基本使用 1、模式 2、使用步骤 三、基本配置 1、五大核心概念 2、准备 Webpack 配置文件 3、运行指令 四、开发模式 五、处理样式资源 1、处理CSS资源 2、处…

100份简历才找一个合适的,2023,软件测试岗位饱和了吗?

各大互联网公司的接连裁员&#xff0c;政策限制的行业接连消失&#xff0c;让今年的求职雪上加霜&#xff0c;想躺平却没有资本&#xff0c;还有人说软件测试岗位饱和了&#xff0c;对此很多求职者深信不疑&#xff0c;因为投出去的简历回复的越来越少了。 另一面企业招人真的…

闪光桐人の实习日记(2023年2月20-27日)

前往闪闪の小窝以获得更好的阅读和评论体验 文章目录2023年2月20日&#xff08;Vue入门&#xff09;概念Vue基础Vue中的MVVMVue的体验Vue的生命周期Vue指令Vue组件VueRouter前后端路由的区别工作原理两种模式比较route跟router的区别路由属性导航守卫Vuex概述5种基本对象基本使…

Qt线程QThread详解

目录前言1.QThread介绍2.QThread示例一3.QThread示例二4.线程同步前言 在程序中使用线程可以提高程序的性能、并发性、响应性和稳定性&#xff0c;使得程序设计更加灵活和简单。但是&#xff0c;线程编程也有一些挑战&#xff0c;如线程安全性和死锁等问题需要格外注意。我们使…

【1】linux命令每日分享——mkdir

大家好&#xff0c;这里是sdust-vrlab&#xff0c;Linux是一种免费使用和自由传播的类UNIX操作系统&#xff0c;Linux的基本思想有两点&#xff1a;一切都是文件&#xff1b;每个文件都有确定的用途&#xff1b;linux涉及到IT行业的方方面面&#xff0c;在我们日常的学习中&…

【机器学习】决策树-ID3算法

1.ID3算法 ID3算法利用信息增益进行特征的选择进行树的构建。信息熵的取值范围为0~1&#xff0c;值越大&#xff0c;越不纯&#xff0c;相反值越小&#xff0c;代表集合纯度越高。信息增益反映的是给定条件后不确定性减少的程度。每一次对决策树进行分叉选取属性的时候&#x…

网络计划--时间参数的计算和优化

根据网络图的基本概念和原则绘制出网络图之后&#xff0c;我们可以计算网络图中有关的时间参数&#xff0c;主要目的是找出关键路线&#xff0c;为网络计划的优化、调整和执行提供明确的时间概念。如下图中从始点①到终点⑧共有4条路线&#xff0c;可以分别计算出每条路线所需的…

使用maven搭建父子工程项目

创建父子工程&#xff0c;可以通过父工程来引入jar&#xff0c;定义统一的版本号等。更方便对整个项目的jar包实现统一化管理&#xff0c;让项目的层次更加清晰。一、创建父工程第一步&#xff1a;file–>new–>project–>maven默认使用jdk1.8&#xff0c;不引入任何j…

音视频基础之视频主要概念

视频主要概念 **视频码率&#xff1a;**kb/s&#xff0c;是指视频文件在单位时间内使用的数据流量&#xff0c;也叫码流率。码率越大&#xff0c;说明单位时间内取样率越大&#xff0c;数据流精度就越高。 **视频帧率&#xff1a;**fps&#xff0c;通常说一个视频的25帧&…