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

【算法专题--栈】用栈实现队列 -- 高频面试题(图文详解,小白一看就懂!!)

目录

一、前言

二、题目描述 

三、解题方法

⭐双栈 模拟 队列

🥝栈 和 队列 的特性 

🍍具体思路

🍍案例图解

四、总结与提炼 

五、共勉   


一、前言

        用栈实现队列 这道题,可以说是--栈专题--,最经典的一道题,也是在面试中频率最高的一道题目,通常在面试中,面试官可能会从多个方面考察这道题目,所以大家需要对这道题目非常熟悉哦!!
       本片博客就来详细的讲讲解一下 用栈实现队列 的实现方法,让我们的面试变的更加顺利!!!

二、题目描述 

题目链接: 232. 用栈实现队列 - 力扣(LeetCode)

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

三、解题方法

⭐双栈 模拟 队列

🥝栈 和 队列 的特性 


队列的特性是 FIFO(先入先出),而栈的特性是 FILO(先入后出)。

知道两者特性之后,我们需要用两个栈来模拟队列的特性,一个栈为入队栈,一个栈为出对栈。


🍍具体思路


我们使用两个栈,其中栈 stk1用于入队,另一个栈 stk2 用于出队。 

  • 入队时,直接将元素入栈 stk1时间复杂度 O(1)。 
  • 出队时,先判断栈 stk2 是否为空,如果为空,则将栈 stk1 中的元素全部出栈并入栈 stk2,然后再从栈 stk2 中出栈一个元素。如果栈 stk2 不为空,则直接从栈 stk2 中出栈一个元素。时间复杂度 O(1)
  • 获取队首元素时,先判断栈 stk2 是否为空,如果为空,则将栈 stk1 中的元素全部出栈并入栈 stk2,然后再从栈 stk2 中获取栈顶元素。如果栈 stk2 不为空,则直接从栈 stk2 中获取栈顶元素。时间复杂度 O(1)
  • 判断队列是否为空时,只要判断两个栈是否都为空即可。时间复杂度 O(1)。 

干涩的语言可能让大家不太好理解,我们在来看一下 详细的图解


🍍案例图解

执行语句:
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

 我们,根据这些语句,进行 入队 和 出队 的操作

  • 首先 需要 入队列 【1】 【2】

  • 出 队列  将【1】 从队列 中 排出去 

  • 继续 入队列元素 【3】 【4】

  •  清空队列中的元素

  •  最后,判断队列是否为 空


 代码:

class MyQueue {
public:MyQueue() {// 程序自己创建构造函数初始化}void move()  // 移动两个栈 中的 元素{if(st2.empty()){while(!st1.empty()){st2.push(st1.top());st1.pop();}}}void push(int x) // 入 队列{// 将全部元素 入st1 st1.push(x);}int pop()  // 出 队列{// 先 移动 元素move();int ans = st2.top();st2.pop();return ans;}int peek() {move();return st2.top();}bool empty() {return st1.empty() && st2.empty();}private://用两个 栈 实现 队列stack<int> st1;  // 入队stack<int> st2;  // 出队};

四、总结与提炼 

        最后我们来总结一下本文所介绍的内容,本文讲解来一道力扣中有关 用栈实现队列 的题目,这道题目是校招笔试面试中有关栈章节非常高频的一道题目大家下去一定要自己再画画图,分析一下,把这段代码逻辑自己实现一遍,才能更好地掌握 !!

五、共勉   

以下就是我对 用栈实现队列 的理解,如果有不懂和发现问题的小伙伴,请在评论区说出来哦,同时我还会继续更新对 栈专题 的理解,请持续关注我哦!!! 

相关文章:

【算法专题--栈】用栈实现队列 -- 高频面试题(图文详解,小白一看就懂!!)

目录 一、前言 二、题目描述 三、解题方法 ⭐双栈 模拟 队列 &#x1f95d;栈 和 队列 的特性 &#x1f34d;具体思路 &#x1f34d;案例图解 四、总结与提炼 五、共勉 一、前言 用栈实现队列 这道题&#xff0c;可以说是--栈专题--&#xff0c;最经典的一道题&…...

2024亚太杯中文赛B题全保姆教程

B题 洪水灾害的数据分析与预测 问题 1. 请分析附件 train.csv 中的数据&#xff0c;分析并可视化上述 20 个指标中&#xff0c;哪 些指标与洪水的发生有着密切的关联&#xff1f;哪些指标与洪水发生的相关性不大&#xff1f;并 分析可能的原因&#xff0c;然后针对洪水的提前预…...

穿越光影,共赏中华瑰宝——皮影戏文化交流盛会

2024年7月3日&#xff0c;皮影不离团队的成员非常荣幸能与外国语学院的同学以及留学生一同探索中国古老而迷人的艺术形式——皮影戏。皮影戏&#xff0c;源自中国民间&#xff0c;距今已有数千年的历史&#xff0c;它不仅是光与影的魔术&#xff0c;更是文化传承的活化石。 在这…...

SQL常用经典语句大全

SQL经典语句大全 一、基础 1、说明&#xff1a;创建数据库 CREATE DATABASE database-name 2、说明&#xff1a;删除数据库 drop database dbname 3、说明&#xff1a;备份sql server — 创建 备份数据的 device USE master EXEC sp_addumpdevice ‘disk’, ‘testBack’, ‘c:…...

黑马点评DAY5|商户查询缓存

商户查询缓存 缓存的定义 缓存就是数据交换的缓冲区&#xff08;Cache&#xff09;&#xff0c;是存储数据的临时地方&#xff0c;一般读写性能较高。 比如计算机的CPU计算速度非常快&#xff0c;但是需要先从内存中读取数据再放入CPU的寄存器中进行运算&#xff0c;这样会限…...

Owl 中的 Props 概述

在动态的 Web 开发环境中&#xff0c;创建模块化和可重用组件对于构建可扩展应用程序至关重要。将这种方法提升到新水平的一个框架是 Owl&#xff0c;其中“props”&#xff08;属性的缩写&#xff09;的概念在协调父组件和子组件之间的通信中起着关键作用。在 Owl 框架中&…...

【大数据综合试验区1008】揭秘企业数字化转型:大数据试验区政策数据集大公开!

今天给大家分享的是国内顶级期刊中国工业经济2023年发布的最新期刊《政策赋能、数字生态与企业数字化转型——基于国家大数据综合试验区的准自然实验》文章中所使用到的数据集——国家大数据综合试验区政策数据集以及工具变量数据&#xff0c;该文章基于2009-2019年中国上市企业…...

在 WebGPU 与 Vulkan 之间做出正确的选择(Making the Right Choice between WebGPU vs Vulkan)

在 WebGPU 与 Vulkan 之间做出正确的选择&#xff08;Making the Right Choice between WebGPU vs Vulkan&#xff09; WebGPU 和 Vulkan 之间的主要区别WebGPU 是什么&#xff1f;它适合谁使用&#xff1f;Vulkan 是什么&#xff1f;它适合谁使用&#xff1f;WebGPU 和 Vulkan…...

亚马逊云服务器的价格真的那么贵吗?一年要花多少钱?

亚马逊Web服务&#xff08;AWS&#xff09;作为全球领先的云计算平台&#xff0c;其定价策略常常引起用户的关注。很多人可能会问&#xff1a;"AWS真的那么贵吗&#xff1f;"实际上&#xff0c;这个问题的答案并不是简单的"是"或"否"&#xff0c…...

Python学习篇:Python基础知识(三)

目录 1 Python保留字 2 注释 3 行与缩进 ​编辑4 多行语句 5 输入和输出 6 变量 7 数据类型 8 类型转换 9 表达式 10 运算符 1 Python保留字 Python保留字&#xff08;也称为关键字&#xff09;是Python编程语言中预定义的、具有特殊含义的标识符。这些保留字不能用作…...

C++字体库开发之字体回退三

代码片段 class FontCoverage { public: using SP std::shared_ptr<FontCoverage>; virtual ~FontCoverage() default; virtual void set(int index, FontTypes::CoverageLevel level) 0; virtual FontTypes::Coverag…...

python vtk lod 设置

在Python中使用VTK库设置Level of Detail (LOD)可以通过vtkLODProp3D类来实现。这个类允许你为一个模型指定不同级别的细节表示&#xff0c;从而在渲染时根据模型与摄像机的距离自动切换到更适合的表示。 以下是一个简单的例子&#xff0c;展示如何使用vtkLODProp3D来设置LOD&…...

Rhino 犀牛三维建模工具下载安装,Rhino 适用于机械设计广泛领域

Rhinoceros&#xff0c;这款软件小巧而强大&#xff0c;无论是机械设计、科学工业还是三维动画等多元化领域&#xff0c;它都能展现出其惊人的建模能力。 Rhinoceros所包含的NURBS建模功能&#xff0c;堪称业界翘楚。NURBS&#xff0c;即非均匀有理B样条&#xff0c;是计算机图…...

Unleashing Text-to-Image Diffusion Models for Visual Perception

mmcv的环境不好满足&#xff0c;不建议复现...

[2024]docker-compose实战 (1)前言

前言 本文用来记录使用docker-compose来实战搭建一个多项目的测试环境. 环境中包含nodejs, php, html, redis, MongoDB, mysql. 在本次部署流程中, 尽量保证原镜像的"干净简洁", 尽量不会往镜像中加入各种软件和插件, 所有的配置尽可能的在宿主机映射进去. 项目…...

并发编程面试题3

一、CountDownLatch,Semaphore的高频问题: 1.1 CountDownLatch是啥?有啥用?底层咋实现的? CountDownLatch 本质上是一个计数器,用于协调多个线程之间的同步。主要应用场景是在多线程并行处理业务时,需要等待其他线程处理完再进行后续操作,例如合并结果或响应用户请求…...

Movable antenna 早期研究

原英文论文名字Historical Review of Fluid Antenna and Movable Antenna 最近&#xff0c;无线通信研究界对“流体天线”和“可移动天线”两种新兴天线技术的发展引起了极大的关注&#xff0c;这两种技术因其前所未有的灵活性和可重构性而极大地提高了无线应用中的系统性能。…...

Polkadot 安全机制揭秘:保障多链生态的互操作性与安全性

作者&#xff1a;Filippo Franchini&#xff0c;Web3 Foundation 原文&#xff1a;https://x.com/filippoweb3/status/1806318265536242146 编译&#xff1a;OneBlock Polkadot 是一个创新的多链区块链平台&#xff0c;旨在实现不同区块链之间的互操作性和共享安全性。本文将详…...

python将多个文件夹里面的文件拷贝到一个文件夹中

网上可以搜到很多方式&#xff0c;有的好使&#xff0c;有的不好使&#xff0c;亲测如下脚本可用&#xff0c;并可达到我想要的效果&#xff0c;只将多个文件夹里的文件拷贝到一个文件夹中&#xff0c;不拷贝文件夹本身&#xff0c;如果需要文件夹也拷贝打开注释行即可 import…...

docker私有仓库harbor部署

docker私有仓库harbor部署 概述 Docker 官方镜像源被中国大陆政府封锁&#xff0c;导致无法在中国大陆的计算机上直接使用 Docker 拉取镜像&#xff0c;导致使用者一下子手足无措了&#xff0c;的确一开始会有很大的影响&#xff0c;为了应对这种影响我们可以自己构建私有仓库&…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...