LeetCode255.用队列实现栈
题目传送门:Leetcode255.用队列实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(
push、top、pop和empty)。实现
MyStack类:
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的,返回true;否则,返回false。注意:
- 你只能使用队列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
输入: ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 2, 2, false]解释: MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False提示:
1 <= x <= 9- 最多调用
100次push、pop、top和empty- 每次调用
pop和top都保证栈不为空进阶:你能否仅用一个队列来实现栈。
试题解析:
已知队列是先进先出,栈是先进后出。
当我们寻找栈顶元素时,实际上是要将当前队列的尾元素输出,但队列的pop()函数只能弹出队首,这时便可以使用第二个辅助队列。
具体方案:
定义两个队列q1,q2,q1为存放数据的队列,q2是辅助队列,每一步操作之后都要将数据存回q1
进行push操作时,在q1中插入元素
进行pop操作时:
1、将q1中的除了队尾之外的元素,全部插入到q2队列中
2、在q1中删除剩下的元素,即队尾元素
3、将q2队列中的元素再插回到q1中
class MyStack {
public:queue<int> q1;queue<int> q2;MyStack() {}void push(int x) {q1.push(x);}int pop() {int n = 0;while(n < q1.size() - 1){//循环到q1只剩一个元素q2.push(q1.front());q1.pop();}int num = q1.front();q1.pop();//将数据存回q1while(!q2.empty()){q1.push(q2.front());q2.pop();}return num;}int top() {return q1.back();}bool empty() {if(q1.empty()){return true;}return false;}
};
更好方案
从以上方法我们可以观察到,q1是存放数据的队列,q2为辅助队列,每一次执行删除之后都要将q2的数据存回q1,接下来的push,pop操作都是从q1开始
那么我们可不可以在每一次pop中都少一次存回q1的操作,而将之后的push,pop操作开始于q2呢?
已知我们每一次转移元素操作后,都会有一个队列为空,那么pop操作时,我们只需要从不为空的队列开始操作即可
至于push操作,在最开始时,q1,q2都为空时,我们将元素添加到q1,对于之后的操作,我们还是只需要从不为空的队列开始插入元素即可。
class MyStack {
public:queue<int> q1;queue<int> q2;MyStack() {}void push(int x) {//若q1,q2都不为空,则插入到q1后if(q1.empty()&&q2.empty()){q1.push(x);}else{//选择不空的队列插入元素if(!q1.empty()) q1.push(x);else if(!q2.empty()) q2.push(x);}}int pop() {int n = 0;int num;//选择不空的队列操作if(!q1.empty()){while(n < q1.size() - 1){q2.push(q1.front());q1.pop();}num = q1.front();q1.pop();}else if(!q2.empty()){while(n < q2.size() - 1){q1.push(q2.front());q2.pop();}num = q2.front();q2.pop();}return num;}int top() {//选择不空的队列操作if(q1.empty()){while(!q2.empty()){q1.push(q2.front());q2.pop();}return q1.back();}else if(q2.empty()){while(!q1.empty()){q2.push(q1.front());q1.pop();}return q2.back();}return 0;}bool empty() {if(q1.empty()&&q2.empty()){return true;}return false;}
};
相关文章:
LeetCode255.用队列实现栈
题目传送门:Leetcode255.用队列实现栈 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。 实现 MyStack 类: void push(int x) 将元素 x 压…...
PHPStudy快速搭建网站并结合内网穿透远程访问本地站点
文章目录 [toc]使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点,测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中,查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2…...
AI嵌入式K210项目(1)-芯片开发板介绍
系列文章目录 在人工智能大潮滚滚而来的时代,作为一个从事嵌入式行业多年的程序猿倍感焦虑,有被替代的焦虑,也有跟不上新技术步伐的无奈,本系列文章将介绍一个从硬件设计到ai训练、最后到模型部署的完整案例;第一阶段…...
Blazor中使用impress.js
impress.js是什么? 你想在浏览器中做PPT吗?比如在做某些类似于PPT自动翻页,局部放大之类,炫酷无比。 在Blazor中,几经尝试,用以下方法可以实现。写文不易,请点赞、收藏、关注,并在转…...
ros2 ubuntu 20.04 安装 foxy
设置区域设置 确保您有一个支持UTF-8. 如果您处于最小环境(例如 docker 容器)中,则区域设置可能是最小的,例如POSIX. 我们使用以下设置进行测试。但是,如果您使用不同的 UTF-8 支持的区域设置,应该没问题。…...
Blazor 错误笔记
1. 运行时问题 Microsoft.NETCore.App.Runtime.Mono.browser-wasm Microsoft.NETCore.App.Runtime.Mono.browser-wasm 是一个 .NET Core 运行时的包,用于在浏览器中运行 .NET Core 应用程序。它是针对 WebAssembly 架构的 .NET Core 运行时,可以在浏览…...
【深度学习1对1指导】
...
XUbuntu22.04之快速复制绝对路径(二百零五)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒…...
21、Kubernetes核心技术 - 高可用集群搭建(kubeadm+keepalived+haproxy)
目录 一、简介 二、高可用集群架构说明 三、部署环境说明 四、高可用集群搭建 (1)、初始化所有节点 (2)、修改host文件 (3)、调整内核参数 (4)、所有节点安装Docker (4-1)、配置 docker 的阿里 yum 源 (4-2)、yum 安装 docker (4-3)、配置 docker 的镜像源 (4-4)…...
使用SpringDataRedis操作Redis
Redis的java客户端 jedisLettuceSpring Data Redis Spring Data redis 是Spring的一部分,对 Redis 底层开发包进行了高度封装。在Spring项目中,可以使用Spring Data Redis来简化操作。 Spring Data Redis使用方式 操作步骤: 导入Spring …...
PyCharm社区版如何创建Django项目并运行
一、配置Django环境 1、使用PyCharm打开一个普通的Python项目 2、为该项目配置Django环境 (1)点击"File"-"Settings" (2)点击"Project:项目名"-"Python Interpreter"-"号" &…...
深度探讨鸿蒙工程师面试题
深度探讨鸿蒙工程师面试题 第一部分:引言 鸿蒙(HarmonyOS)作为华为推出的全场景分布式操作系统,引领着未来智能化时代的潮流。鸿蒙工程师在这一创新性领域中扮演着至关重要的角色。本文将深入研究一系列鸿蒙工程师面试题&#x…...
python数据结构堆栈
堆 堆是一种树形结构:满足两个主要性质 堆是一种完全二叉树:堆中所有层级除了最后一层都是完全填满的,且最后一层的节点都是向左排列堆中的任意节点都不大于(或不小于)其子节点的值,这也是堆的属性 impo…...
从网页连接socket服务器和I/O
1.i/o InputStream和InputStreamReader是Java I/O类库中的两个关键类,用于处理字节流。它们的主要区别在于它们处理数据的方式。 InputStream: InputStream是用于读取字节流的抽象类。它是所有字节输入流类的父类。InputStream的子类可以从不同的数据源读取字节&…...
鸿蒙HarmonyOS学习手册_入门篇
鸿蒙HarmonyOS学习手册_入门篇 文章目录 鸿蒙HarmonyOS学习手册_入门篇入门快速入门开发准备基本概念UI框架应用模型工具准备 构建第一个ArkTS应用(Stage模型)-快速入门-入门创建ArkTS工程ArkTS工程目录结构(Stage模型)构建第一个…...
人工智能复习
机器学习中线性回归和逻辑回归: 机器学习的分类: 监督学习和无监督学习,半监督学习 监督学习(Supervised Learning): 监督学习是一种利用带有标签(标记)的数据进行训练的机器学习…...
C++ 多态以及多态的原理
文章目录 多态的概念多态的构成条件虚函数的重写虚函数重写的两个例外 重载、重写(覆盖)、重定义(隐藏)对比C11 final 和 override关键字抽象类接口继承和普通继承多态的原理虚函数表多态的原理 单继承和多继承关系的虚函数表单继承中的虚函数表多继承中的虚函数表 多态的概念 …...
贝蒂详解<string.h>(下)
✨✨欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:C语言学习 贝蒂的主页:Betty‘s blog 目录 1. 简介 2. memset()函数 2.1用法 2.2实例 2.3 实现me…...
问题 F: 分巧克力
题目描述 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力,其中第i 块HiWi 的方格组成的长方形。 为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。 切出的巧克力需要满足&am…...
安装pillow可能遇到的问题
安装命令 pip install Pillow安装 Pillow 这个 Python 图像处理库时可能会遇到多种问题。以下一些常见的安装问题及其解决方法: 缺少依赖项: Pillow 安装可能需要一些基础库,如 libjpeg 和 zlib。如果在安装时提示缺少这些库,你需要先安装它…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
