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

【LeetCode刷题日志】232.用栈实现队列

  • 🎈个人主页:库库的里昂
  •  🎐C/C++领域新星创作者
  •  🎉欢迎 👍点赞✍评论⭐收藏
  • ✨收录专栏:LeetCode 刷题日志
  • 🤝希望作者的文章能对你有所帮助,有不足的地方请在评论区留言指正,大家一起学习交流!🤗

目录

1.题目描述

2.解题思路+代码实现

方法:双栈

思路及算法:

代码实现:


1.题目描述

OJ链接 【leetcode 题号:232.用栈实现队列】【难度:简单】

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

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to toppeek/pop from topsize, 和 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 次 pushpoppeek 和 empty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

进阶:

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

2.解题思路+代码实现

方法:双栈
思路及算法:

将一个栈当作输入栈,用于压入push传入的数据;另一个栈当作输出栈,用于 pop和peek操作。

每次pop或peek时,若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

代码实现:
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}void STPush(ST* pst, STDataType x)
{if (pst->top == pst->capacity) {int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc fail");return;}pst->a = tmp;pst->capacity = newCapacity;}pst->a[pst->top] = x;pst->top++;
}bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}int STSize(ST* pst)
{assert(pst);return pst->top;
}//------以下为OJ提供-------typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));if (obj == NULL) {perror("malloc fail");return 0;}STInit(&obj->pushst);STInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst, x);
}int myQueuePop(MyQueue* obj) {int front = myQueuePeek(obj);STPop(&obj->popst);return front;
}int myQueuePeek(MyQueue* obj) {if (STEmpty(&obj->popst)) {while (!STEmpty(&obj->pushst)) {STPush(&obj->popst, STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

复杂度分析

  • 时间复杂度:push和empty为O(1),pop和peek为均摊O(1)。对于每个元素,至多入栈和出栈各两次,故均摊复杂度为O(1)。
  • 空间复杂度:O(n)。其中n是操作总数。对于有n次push操作的情况,队列中会有n个元素,故空间复杂度为O(n)。

相关文章:

【LeetCode刷题日志】232.用栈实现队列

&#x1f388;个人主页&#xff1a;库库的里昂 &#x1f390;C/C领域新星创作者 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏✨收录专栏&#xff1a;LeetCode 刷题日志&#x1f91d;希望作者的文章能对你有所帮助&#xff0c;有不足的地方请在评论区留言指正&#xff0c;…...

单元测试实战(二)Service 的测试

为鼓励单元测试&#xff0c;特分门别类示例各种组件的测试代码并进行解说&#xff0c;供开发人员参考。 本文中的测试均基于JUnit5。 单元测试实战&#xff08;一&#xff09;Controller 的测试 单元测试实战&#xff08;二&#xff09;Service 的测试 单元测试实战&#x…...

LabVIEW和NIUSRP硬件加快了认知无线电开发

LabVIEW和NIUSRP硬件加快了认知无线电开发 对于电视频谱&#xff0c;主用户传输有两种类型&#xff1a;广播电视和节目制作和特殊事件(PMSE)设备。广播塔的位置已知&#xff0c;且覆盖电视传输塔&#xff08;复用器&#xff09;附近的某个特定地理区域&#xff08;称为排除区域…...

嵌入式软件工程师面试题——2025校招社招通用(十六)

说明&#xff1a; 面试群&#xff0c;群号&#xff1a; 228447240面试题来源于网络书籍&#xff0c;公司题目以及博主原创或修改&#xff08;题目大部分来源于各种公司&#xff09;&#xff1b;文中很多题目&#xff0c;或许大家直接编译器写完&#xff0c;1分钟就出结果了。但…...

白盒测试之测试用例设计方法

白盒测试之测试用例设计方法 什么是白盒测试白盒测试的特点白盒测试的设计方法静态设计方法动态设计方法语句覆盖分支(判定)覆盖条件覆盖判定条件覆盖组合覆盖路径覆盖总结 什么是白盒测试 按照测试方法分类&#xff0c;测试可以分为白盒测试和黑盒测试两种。 白盒测试也称结构…...

在CentOS 7上关闭SELinux

要在CentOS 7上关闭SELinux&#xff0c;可以按照以下步骤进行操作&#xff1a; 临时关闭SELinux&#xff08;不建议使用&#xff09;&#xff1a; setenforce 0但是这种方式只对当前启动有效&#xff0c;重启系统后会失效。 2. 永久关闭SELinux&#xff1a; vi /etc/selinux…...

基于单片机温湿度PM2.5报警系统

**单片机设计介绍&#xff0c; 基于单片机温湿度PM2.5报警设置系统 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 单片机温湿度PM2.5报警设置系统是一种智能化的环境检测与报警系统。它主要由单片机、传感器、液晶显示屏、蜂鸣器…...

OpenHarmony系统编译环境

1. 推荐系统Ubuntu 2204 2. 必须安装的软件 apt-get install curl build-essential gcc g make ninja-build cmake libffi-dev e2fsprogs pkg-config flex bison perl bc openssl libssl-dev libelf-dev binutils binutils-dev libdwarf-dev u-boot-tools mtd-utils cpio de…...

二十三种设计模式全面解析-职责链模式(Chain of Responsibility Pattern):解放代码责任链,提升灵活性与可维护性

在软件开发中&#xff0c;我们经常面临处理请求或事件的情况。有时候&#xff0c;我们需要将请求或事件依次传递给多个对象进行处理&#xff0c;但又不确定哪个对象最终会处理它。这时候&#xff0c;职责链模式&#xff08;Chain of Responsibility Pattern&#xff09;就能派上…...

通过制作llama_cpp的docker镜像在内网离线部署运行大模型

对于机器在内网&#xff0c;无法连接互联网的服务器来说&#xff0c;想要部署体验开源的大模型&#xff0c;需要拷贝各种依赖文件进行环境搭建难度较大&#xff0c;本文介绍如何通过制作docker镜像的方式&#xff0c;通过llama.cpp实现量化大模型的快速内网部署体验。 一、llam…...

JavaScript 异步编程

异步的概念 异步&#xff08;Asynchronous, async&#xff09;是与同步&#xff08;Synchronous, sync&#xff09;相对的概念。 在我们学习的传统单线程编程中&#xff0c;程序的运行是同步的&#xff08;同步不意味着所有步骤同时运行&#xff0c;而是指步骤在一个控制流序…...

linux课程第一课------命令的简单的介绍

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…...

XLua热更新框架原理和代码实战

安装插件 下载Xlua插件&#xff1a;https://github.com/Tencent/xLua 下载完成后&#xff0c;把Asset文件夹下的文件拖入自己的工程Asset中&#xff0c;看到Unity编辑器上多了个Xlua菜单&#xff0c;说明插件导入成功 Lua启动代码 新建一个空场景&#xff0c;场景中什么都不…...

Hive客户端hive与beeline的区别

hive与beeline简介 1、背景2、hive3、beeline4、hive与beeline的关系 1、背景 Hive的hive与beeline命令都可以为客户端提供Hive的控制台连接。两者之间有什么区别或联系吗&#xff1f; Hive-cli(hive)是Hive连接hiveserver2的命令行工具&#xff0c;从Hive出生就一直存在&…...

<MySQL> 什么是数据库索引?数据库索引的底层结构是什么?

目录 一、什么是数据库索引? 1.1 索引的概念 1.2 索引的特点 1.3 索引的适用场景 1.4 索引的使用 1.4.1 创建索引 1.4.2 查看索引 1.4.3 删除索引 二、数据库索引的底层结构是什么&#xff1f; 2.1 数据库中的 B树 长啥样&#xff1f; 2.2 B树为什么适合做数据库索…...

对于koa中间件的理解

洋葱模型 大家都知道koa是洋葱模型&#xff0c;先一层一层通过next往下&#xff0c;之后再回去执行next后面的内容&#xff0c;next即使没写&#xff0c;最后也会进入下一个中间件。 那么什么是ctx呢&#xff0c;ctx顾名思义就是上下文&#xff0c;也就是上一层传给下一层的东…...

分页文件pagefile.sys引出的疑问

现象描述&#xff1a; 磁盘中显示无任何文件&#xff0c;却占用5GB左右的磁盘空间&#xff1b;格式化D盘时提示【此驱动器正在使用中。另一个程序或进程正在使用此驱动器。是否仍要对其进行格式化&#xff1f;】&#xff0c;点击【是】提示【Windows 无法完成格式化。】&#…...

【开题报告】疫苗在线预约小程序的设计与实现

1.选题背景 &#xff08;1&#xff09;新冠疫情下的疫苗接种挑战&#xff1a; 针对当前全球范围内的新冠疫情&#xff0c;疫苗接种成为控制疫情蔓延的重要手段。然而&#xff0c;大规模疫苗接种也带来了接种排队、人群聚集等管理难题&#xff0c;为了更好地组织和管理疫苗接种…...

【深度学习实验】注意力机制(二):掩码Softmax 操作

文章目录 一、实验介绍二、实验环境1. 配置虚拟环境2. 库版本介绍 三、实验内容0. 理论介绍a. 认知神经学中的注意力b. 注意力机制&#xff1a; 1. 注意力权重矩阵可视化&#xff08;矩阵热图&#xff09;2. 掩码Softmax 操作a. 导入必要的库b. masked_softmaxc. 实验结果 ​ …...

idea运行项目之后一直卡在Writing classes… 解决方案

最近遇到idea里直接运行一个Spring boot项目后&#xff0c;idea一直慢悠悠的parsing java&#xff0c;然后就writing classes&#xff0c;然后就一直卡着不动了&#xff0c;运气好10几分钟能把项目启动起来。 多年的摸鱼经验告诉我&#xff0c;事出反常必有妖&#xff0c;赶紧…...

第3篇:系统透视——信息部门如何构建“税务友好型”IT架构

本篇导读&#xff1a;如果你是信息总监或IT负责人&#xff0c;请通读全文&#xff0c;尤其是“系统合规设计的三必须”和“现场检查SOP”&#xff1b;如果你是财税人员&#xff0c;请重点阅读“研产供销全链条的系统对接要求”和“与IT部门的协作要点”&#xff1b;如果你是老板…...

自制极低频电流探头:负电阻补偿原理与低频方波测量实践

1. 项目概述&#xff1a;为极低频电流测量而生在电子测试领域&#xff0c;电流探头是个再常见不过的工具&#xff0c;无论是排查开关电源的纹波&#xff0c;还是分析电机驱动的波形&#xff0c;都离不开它。但如果你尝试用市面上常见的电流探头去观察一个频率低至几赫兹&#x…...

TVA注意力层INT8量化配置技巧

重磅预告&#xff1a;本专栏将独家连载系列丛书《智能体视觉技术与应用》部分精华内容&#xff0c;该书是世界首套系统阐述“因式智能体”视觉理论与实践的专著&#xff0c;特邀美国 TypeOne 公司首席科学家、斯坦福大学博士 Bohan 担任技术顾问。Bohan先生师从美国三院院士、“…...

从NLP到RAG:AI标书生成系统的技术架构与落地路径深度剖析

引言2026年2月&#xff0c;国家发改委等八部门联合印发《关于加快招标投标领域人工智能推广应用的实施意见》&#xff0c;明确到2026年底招标文件检测、智能辅助评标、围串标识别等重点场景在部分省市实现全覆盖。同一时期&#xff0c;《招标投标法》修订草案经国务院常务会议原…...

AWS DevOps Agent 完全指南

AWS DevOps Agent 是 AWS 推出的前沿 AI 运维代理,自主调查和解决事件、持续预防故障、提升系统可靠性。本文档覆盖从原理到实战的全生命周期管理。 一、定位与价值 一句话定义 AWS DevOps Agent = AI 驱动的 SRE 队友,724 自主调查告警、定位根因、生成修复方案、预防未来…...

Style-Bert-VITS2未来发展方向:从语音克隆到实时语音转换的技术演进路线

Style-Bert-VITS2未来发展方向&#xff1a;从语音克隆到实时语音转换的技术演进路线 【免费下载链接】Style-Bert-VITS2 Style-Bert-VITS2: Bert-VITS2 with more controllable voice styles. 项目地址: https://gitcode.com/gh_mirrors/st/Style-Bert-VITS2 Style-Bert…...

Windows 11 LTSC安装微软商店的终极解决方案:3步恢复完整应用生态

Windows 11 LTSC安装微软商店的终极解决方案&#xff1a;3步恢复完整应用生态 【免费下载链接】LTSC-Add-MicrosoftStore Add Windows Store to Windows 11 24H2 LTSC 项目地址: https://gitcode.com/gh_mirrors/ltscad/LTSC-Add-MicrosoftStore LTSC-Add-MicrosoftStor…...

AI算法工程师如何进行数据预处理?这5个步骤让你的数据更优质

在AI模型开发与测试的全流程中&#xff0c;数据质量直接决定了最终模型的效果上限——哪怕是最先进的大语言模型&#xff0c;用劣质数据训练出来也只能输出劣质结果。对于软件测试从业者来说&#xff0c;不管是参与AI模型的功能测试、性能测试&#xff0c;还是负责测试数据集的…...

2026年新能源人才全球本地化策略

导读&#xff1a;报告基于领英行业洞察&#xff0c;聚焦 2026 年全球新能源行业发展格局、中国企业出海现状、人才供需痛点及全球化人才本地化落地策略&#xff0c;为新能源企业海外人才招聘、培养与组织管理提供完整解决方案。关注公众号&#xff1a;【互联互通社区】&#xf…...

ChartGPT深度解析:基于AI的自然语言图表生成架构设计与企业级应用

ChartGPT深度解析&#xff1a;基于AI的自然语言图表生成架构设计与企业级应用 【免费下载链接】chart-gpt AI tool to build charts based on text input 项目地址: https://gitcode.com/gh_mirrors/ch/chart-gpt ChartGPT是一款创新的AI驱动图表生成工具&#xff0c;通…...