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

LeetCode-232. 用栈实现队列(C++)

目录捏

  • 一、题目描述
  • 二、示例与提示
  • 三、思路
  • 四、代码


一、题目描述

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

实现 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 次 pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

进阶:

  • 你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。

三、思路

本题要使用栈来实现队列,所以需要先了解栈和队列分别有什么特性。

栈:先进后出;队列:先进先出

所以,要使用栈来模式队列的行为,如果仅仅用一个栈,是一定不行的,所以需要两个栈一个输入栈,一个输出栈,这里要注意输入栈和输出栈的关系。

push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意:全部导入),再从输出栈弹出数据,如果输出栈不为空,则直接从输出栈弹出数据就可以了。

最后如何判断队列为呢?如果进栈和出栈都为空的话,说明模拟的队列为空了。


在代码实现的时候,会发现 pop()peek() 两个函数功能类似,代码实现上也是类似的,所以我们可以思考一下如何把代码抽象一下。

我们在实现 peek() 函数时可以直接复用 pop() 函数,只不过最后需要把弹出的值再push进去。

四、代码

class MyQueue {
public:stack<int>stIn; // 定义输入栈stack<int>stOut; // 定义输出栈MyQueue() {}void push(int x) {stIn.push(x);}int pop() {// 分两种情况讨论:输出栈为空、输出栈不为空if(stOut.empty()) {// 只有当stOut为空的时候,再从stIn里导入数据(导入stIn全部数据)while(!stIn.empty()) {// 从stIn导入数据直到stIn为空stOut.push(stIn.top());stIn.pop();}}int res = stOut.top();stOut.pop();return res;}int peek() {int res = this->pop(); // 此处直接复用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res,所以再push回去return res;}bool empty() {// 如果进栈和出栈都为空的话,说明模拟的队列为空return stIn.empty()&&stOut.empty();}
};

复杂度分析

时间复杂度: push和empty为O(1), pop和peek为O(n)

相关文章:

LeetCode-232. 用栈实现队列(C++)

目录捏 一、题目描述二、示例与提示三、思路四、代码 一、题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xff1a; 实现 MyQueue 类&#xff1a; void push(int x) 将元素 x 推到队列的…...

无人机红外相机的畸变矫正

在项目开展过程中&#xff0c;发现大疆M30T的红外相机存在比较明显的畸变问题&#xff0c;因此需要对红外图像进行畸变矫正。在资料检索过程中&#xff0c;发现对红外无人机影像矫正的资料较少&#xff0c;对此&#xff0c;我从相机的成像原理角度出发&#xff0c;探索出一种效…...

C++编程案例讲解-基于结构体的控制台通讯录管理系统

基于结构体的控制台通讯录管理系统 通讯录是一个可以记录亲人、好友信息的工具&#xff0c;系统中需要实现的功能如下&#xff1a; 添加联系人&#xff1a;向通讯录中添加新人&#xff0c;信息包括&#xff08;姓名、性别、年龄、联系电话、家庭住址&#xff09;最多记录1000人…...

ASP.NETCore6开启文件服务允许通过url访问附件(图片)

需求背景 最近在做一个工作台的文件上传下载功能&#xff0c;主要想实现上传图片之后&#xff0c;可以通过url直接访问。由于url直接访问文件不安全&#xff0c;所以需要手动开启文件服务。 配置 文件路径如下&#xff0c;其中Files是存放文件的目录&#xff1a; 那么&…...

python爬取Web of science论文信息

一、python爬取WOS总体思路 (一)拟实现功能描述 wos里面&#xff0c;爬取论文的名称&#xff0c;作者名称&#xff0c;作者单位&#xff0c;引用数量 要求&#xff1a;英文论文、期刊无论好坏 检索关键词&#xff1a;zhejiang academy of agricultural sciences、 xianghu lab…...

本地域名 127.0.0.1 / localhost

所谓本地域名就是 只能在本机使用的域名 &#xff0c;一般在开发阶段使用。 编辑文件 C:\Windows\System32\drivers\etc\hosts。 127.0.0.1 www.baidu.com如果修改失败,可以修改该文件的权限。 原理&#xff1a; 在地址栏输入 域名 之后&#xff0c;浏览器会先进行 DNS…...

Python —— 不同类型的数据长度计算方式

在Python 中&#xff0c;不同类型的数据长度计算方式&#xff0c;有何不同&#x1f447; 字符串&#xff08;String&#xff09; my_string "Hello, World!" string_length len(my_string) print("字符串的长度是&#xff1a;", string_length) //输出…...

NowCoder | 环形链表的约瑟夫问题

NowCoder | 环形链表的约瑟夫问题 OJ链接 思路&#xff1a; 创建带环链表带环链表的删除节点 代码如下&#xff1a; #include<stdlib.h>typedef struct ListNode ListNode; ListNode* ListBuyNode(int x) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node…...

华为政企数据中心网络交换机产品集

产品类型产品型号产品说明 核心/汇聚交换机CE8850-EI-B-B0BCloudEngine 8850-64CQ-EI 提供 64 x 100 GE QSFP28&#xff0c;CloudEngine 8800系列交换机是面向数据中心推出的新一代高性能、高密度、低时延灵活插卡以太网交换机&#xff0c;可以与华为CloudEngine系列数据中心…...

多门店自助点餐+外卖二合一小程序源码系统 带完整搭建教程

随着餐饮业的快速发展和互联网技术的不断进步&#xff0c;越来越多的餐厅开始采用自助点餐和外卖服务。市场上许多的外卖小程序APP应运而生。下面罗峰来给大家介绍一款多门店自助点餐外卖二合一小程序源码系统。该系统结合了自助点餐和外卖服务的优势&#xff0c;为餐厅提供了一…...

kafka可视化工具

Offset Explorer kafka可视化工具...

Excel 转 Json 、Node.js实现(应用场景:i18n国际化)

创作灵感来源于在线转换是按照换行符去转换excel内容换行符后很难处理 本文是按单元格转换 const xlsx require(node-xlsx) const fs require(fs) const xlsxData xlsx.parse(./demo.xlsx) // 需要转换的excel文件// 数据处理 方便粘贴复制 const data xlsxData[2].data …...

Redis7--基础篇2(Redis的十大数据类型及常用命令)

1. Redis的十大数据类型及常用命令 Redis是key-value键值对类型的数据库&#xff0c;我们所说的数据类型指的是value的数据类型&#xff0c;key的数据类型都是字符串。 1.1 字符串&#xff08;String&#xff09; string是redis最基本的类型&#xff0c;一个key对应一个val…...

1.HTML中网页介绍

1.网页 1.1 什么是网页 网站是指在因特网上根据一定的规则&#xff0c;使用HTML等制作的用于展示特定内容的相关的网页集合 网页是网站中的一“页”&#xff0c;通常是HTML格式文件&#xff0c;它要通过浏览器来阅读。 网页是构成网站的基本元素&#xff0c;它通常是有图片&am…...

执行sql报错only_full_group_by的解决方法

一、前言 最近老项目换新数据库&#xff08;都是mysql&#xff09;&#xff0c;有些在老数据库可以执行的sql&#xff0c;在新数据库执行就会报错sql_modeonly_full_group_by 意思是说数据库的模式是sql_modeonly_full_group_by&#xff0c;group by的字段必须和查询字段一致…...

不学51直接学stm32可以吗?学stm32需要哪些基础?

不学51直接学stm32可以吗&#xff1f;学stm32需要哪些基础&#xff1f; 不管那些大佬技术多么牛逼&#xff0c;大多数入门都是从51单片机开始。 最近有一些入门的小伙伴问我说看到同学都从直接从STM32开始干了。最近很多小伙伴找我&#xff0c;说想要一些stm32的资料&#xff…...

6.1二叉树的递归遍历(LC144,LC15,LC94)

什么是递归函数&#xff1f; 递归函数是一种函数调用自身的编程技巧。 在递归函数中&#xff0c;函数通过不断调用自身来解决一个问题&#xff0c;直到达到基本情况&#xff08;递归终止条件&#xff09;并返回结果。 递归函数在解决一些问题时非常有用&#xff0c;特别是那些…...

Spring基础(3):复习

为了让大家更容易接受我的一些观点&#xff0c;上一篇很多笔墨都用在了思路引导上&#xff0c;所以导致文章可能比较臃肿。 这一篇来总结一下&#xff0c;会稍微精简一些&#xff0c;但整体趣味性不如第二篇。 (上一篇说过了&#xff0c;目前介绍的2种注入方式的说法其实不够…...

Java-Hbase介绍

1.1. 概念 base 是分布式、面向列的开源数据库&#xff08;其实准确的说是面向列族&#xff09;。HDFS 为 Hbase 提供可靠的 底层数据存储服务&#xff0c;MapReduce 为 Hbase 提供高性能的计算能力&#xff0c;Zookeeper 为 Hbase 提供 稳定服务和 Failover 机制&#xff0c…...

【PHP】【Too few arguments to function Firebase\JWT\JWT::encode()。。。。。。。】

1.安装jwt composer require firebase/php-jwtuse Firebase\JWT\JWT;public function hello($name ThinkPHP5){$secret_key "YOUR_SECRET_KEY";$issuer_claim "THE_ISSUER";$audience_claim "THE_AUDIENCE";$issuedat_claim time(); // is…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...