Java面试之用两个栈实现队列
文章目录
- 题目
- 一、什么是队列和栈?
- 1.1队列
- 1.2栈
- 二、具体实现
- 2.1 思路分析
- 2.2代码实现
题目
用两个栈实现一个队列,实现在队列尾部插入节点和在队列头部删除节点的功能。
一、什么是队列和栈?
1.1队列
队列是一种特殊的线性表,它只允许在表的前端(队头)进行删除操作,在表的后端(队尾)进行插入。
故队列又称为先进先出(FIFO—first in first out)线性表。
1.2栈
栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。
它按照后进先出(LIFO—last in first out)的原则存储数据,先进入的数据被压入(push)栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出(pop)数据(最后一个数据被第一个读出来)。
栈在计算机领域被广泛应用,比如:操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。
二、具体实现
2.1 思路分析
(a)在stack1中依次插入a、b、c,stack2为空
(b)现在从队列中删除一个元素,按照队列先入先出的规则,最先删除的应该是a。
但是a在栈底不能直接删除,这时候可以借助stack2,将元素逐个弹出(pop)并压入(push)stack2,则元素在stack2中的顺序{从c、b、a}正好和stack1中相反,此时就可以弹出stack2的栈顶a,如图b。
(c)如果想继续删除队列头部,按照最开始的顺序,b比c早进入队列,此时应该删除b。b正好在stack2的栈顶,只需要弹出stack2的栈顶即可。如图c。
这样就可以总结出一个删除的步骤:
1、当stack2不为空时,stack2就是栈顶就是最先进入队列的元素,可以弹出。
2、当stack2为空时,将stack1中的元素逐个弹入stack2中,由于先进入队列的元素被压到stack1栈底,经过弹出和压入操作后位处stack2栈顶,就可以直接弹出。
(d)接下来插入一个元素d,把它压入stack1。
(e)现在考虑删除一个元素,此时stack2不为空,直接弹出c,而c确实比d先进入队列,因此也是正确的。
2.2代码实现
代码如下:
import java.util.*;
import java.util.Stack;
public class CQueue{Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node){stack1.push(node);}public int pop(){if(stack2.isEmpty()){//将第一个栈中内容弹出放入第二个栈中while(!stack1.isEmpty()){stack2.push(stack1.pop());}}if(stack2.isEmpty()){Throw new Exception(queue is empty!);}int head = stack2.pop();return head;}}
相关文章:
Java面试之用两个栈实现队列
文章目录 题目一、什么是队列和栈?1.1队列1.2栈 二、具体实现2.1 思路分析2.2代码实现 题目 用两个栈实现一个队列,实现在队列尾部插入节点和在队列头部删除节点的功能。 一、什么是队列和栈? 1.1队列 队列是一种特殊的线性表,…...
Python-实用的文件管理及操作
本章,来说说,个人写代码过程中,对于文件管理常用的几种操作。 三个维度 1、指定文件的路径拼接2、检查某文件是否存在3、配置文件的路径管理 1、指定文件的路径拼接 这个操作可以用来管理文件路径也就是上述中的第三点。但是,这里…...
Mysql 事物与存储引擎
MySQL事务 MySQL 事务主要用于处理操作量大,复杂度高的数据。比如说,在人员管理系统中, 要删除一个人员,即需要删除人员的基本资料,又需要删除和该人员相关的信息,如信箱, 文章等等。这样&#…...
java.lang.classnotfoundexception: com.android.tools.lint.client.api.vendor
Unity Android studio打包报错修复 解决方式 java.lang.classnotfoundexception: com.android.tools.lint.client.api.vendor 解决方式 在 launcherTemplate 目录下找到 Android/lintOptions 选项 加上 checkReleaseBuilds false lintOptions { abortOnError false checkRelea…...
pytest fixture夹具,@pytest.fixture
fixture 是pytest 用于测试前后进行预备,清理工作的代码处理机制 fixture相对于setup 和teardown: fixure ,命名更加灵活,局限性比较小 conftest.py 配置里面可以实现数据共享,不需要import 就能自动找到一些配置 setu…...
YOLOv7源码解析
YOLOv7源码解析 YAML文件 YAML文件 以yolov7 cfg/yolov7-w6-pose.yaml为例: # parametersnc: 1 # number of classes nkpt: 4 # number of key points depth_multiple: 1.0 # model depth multiple width_multiple: 1.0 # layer channel multiple dw_conv_kpt:…...
2023高教社杯数学建模思路 - 复盘:校园消费行为分析
文章目录 0 赛题思路1 赛题背景2 分析目标3 数据说明4 数据预处理5 数据分析5.1 食堂就餐行为分析5.2 学生消费行为分析 建模资料 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 赛题背景 校园一卡通是集…...
ATF(TF-A)安全通告 TFV-2 (CVE-2017-7564)
安全之安全(security)博客目录导读 ATF(TF-A)安全通告汇总 目录 一、ATF(TF-A)安全通告 TFV-2 (CVE-2017-7564) 二、 CVE-2017-7564 一、ATF(TF-A)安全通告 TFV-2 (CVE-2017-7564) Title 启用安全自托管侵入式调试接口,可允许非安全世界引发安全世界panic CV…...
无涯教程-PHP - 标量函数声明
在PHP 7中,引入了一个新函数,即标量类型声明。标量类型声明有两个选项- Coercive - 强制性是默认模式。Strict - 严格模式必须明确提示。 可以使用上述模式强制执行以下类型的函数参数- intfloatbooleanstringinterfacesarraycallable 强制模…...
动态规划(Dynamic programming)讲解(线性 DP 篇)
文章目录 动态规划(Dynamic Programing)第一关:线性DP第一战: C F 191 A . D y n a s t y P u z z l e s \color{7F25DF}{CF191A.\space Dynasty\enspace Puzzles} CF191A. DynastyPuzzles题目描述难度: ☆☆☆ \color…...
提升开发能力的低代码思路
一、低代码理念 在现代软件开发中,低代码开发平台备受关注。那么,什么是低代码开发平台呢?简单来说,它是一种能够提供丰富的图形化用户界面,让开发者通过拖拽组件和模型就能构建应用的开发环境。与传统开发方式相比&am…...
YAML详解及使用方法
YAML详解及使用方法 一、基本介绍二、数据类型2.1 纯量(scalars)/标量2.1.1 字符串2.1.2 保留换行(Newlines preserved)2.1.3 布尔值(Boolean)2.1.4 整数(Integer)2.1.5 浮点数(Floating Point)2.1.6 空(Nu…...
垃圾回收器
垃圾回收器就是垃圾回收的实践者,随着JDK的发展,垃圾回收器也在不断的更迭,在不同的场合下使用不同的垃圾回收器,这也是JVM调优的一部分。 1.垃圾回收器的分类 按线程可分为单线程(串行)垃圾回收器和多线程(并行)垃圾回收器。 按…...
SpringBoot 读取配置文件的值为 Infinity
1.配置信息 appid:6E212341234 2.获取方式 Value("${admin}")private String admin; 获取到结果 Infinity 3.修改方案 配置信息上加号 appid:‘6E212341234 yml中使用[单引号]不会转换单引号里面的特殊字符,使用""[双…...
学习笔记230827--vue项目中,子组件拿不到父组件异步获取数据的问题
🧋 问题描述 父组件的数据是请求后台所得,因为是异步数据,就会出现,父组件的值传递过去了,子组件加载不到,拿不到值的问题。 下面从同步数据传递和异步数据传递开始论述问题 🧋🧋1…...
sql:SQL优化知识点记录(三)
(1)explain之select_type和table介绍 简单的查询类型是:simple 外层 primary,括号里subquery 用到了临时表:derived (2)explain之type介绍 trpe反映的结果与我们sql是否优化过,是否…...
List<Map>操作汇总
分组 List<Map> mapList new ArrayList<>(); Map<String,List<Map>> mapListGroup mapList.stream().collect(Collectors.groupingBy(e->e.get("xxx").toString())); 最大值最小值 int max maps.stream().mapToInt(e -> new Inte…...
软考:中级软件设计师:网络类型与拓扑结构,网络规划与设计,ip地址与子网划分,特殊含义的IP地址
软考:中级软件设计师:网络类型与拓扑结构 提示:系列被面试官问的问题,我自己当时不会,所以下来自己复盘一下,认真学习和总结,以应对未来更多的可能性 关于互联网大厂的笔试面试,都是需要细心准…...
linux创建进程
linux创建进程 准备工作 准备工作 在Ubuntu64系统上 1、安装GCC和Make工具 编译器GCC:把C源码转为二进制程序 Make:自动编译多源文件项目 sudo apt-get update #更新存储库 sudo apt-get install build-essential #安装build-essential包 gcc --versio…...
100天精通Golang(基础入门篇)——第19天:深入剖析Go语言中方法(Method)的妙用与实践
🌷🍁 博主猫头虎 带您 Go to Golang Language.✨✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~…...
【人工智能】—_不确定性、先验概率_后验概率、概率密度、贝叶斯法则、朴素贝叶斯_、最大似然估计
【人工智能】— 不确定性、先验概率/后验概率、概率密度、贝叶斯法则、朴素贝叶斯 文章目录 【人工智能】— 不确定性、先验概率/后验概率、概率密度、贝叶斯法则、朴素贝叶斯不确定性不确定性与理性决策基本概率符号先验概率(无条件概率)/后验概率(条件概率)随机变量概率密度联…...
postgresql-字符函数
postgresql-字符函数 字符串连接字符与编码字符串长度大小写转换子串查找与替换截断与填充字符串格式化MD5 值字符串拆分字符串反转 字符串连接 concat(str, …)函数用于连接字符串,并且忽略其中的 NULL 参数;concat_ws(sep, str, …) 函数使用指定分隔…...
VUE笔记(五)网络通信
一、axios的简介 1、什么是axios 文档:Axios 中文文档 | Axios 中文网 | Axios 是一个基于 promise 的网络请求库,可以用于浏览器和 node.js 概念:axios是一个基于Promise的网络请求库,可以用于浏览器和node.js 特点ÿ…...
微信小程序修改数据,input不能实时回显
场景: 填写发票抬头,填写抬头公司时候,会根据用户输入的内容实时获取相关的公司信息,用户选择搜索出来的公司,这时候 setData,但是数据并没有回显,而是需要再需要点一下屏幕。 解决方案: 原来…...
GitHub Copilot三连更:能在代码行里直接提问,上下文范围扩展到终端
量子位 | 公众号 QbitAI 就在昨晚,GitHub Copilot迎来了一波不小的更新。 包括: 全新交互体验——代码行中直接召唤聊天功能,不用切界面,主打一个专注; 改善斜杠命令,一键删除,主打快捷操作、…...
双亲委派机制
双亲委派机制流程 当Application ClassLoader 收到一个类加载请求时,他首先不会自己去尝试加载这个类,而是将这个请求委派给父类加载器Extension ClassLoader去完成。 当Extension ClassLoader收到一个类加载请求时,他首先也不会自己去尝试…...
美团北极星榜单,服务零售的医美新样本
事实证明,任何时候,人们对美的追求都是刚需,只是有时候被压抑了。 德勤中国的《中国医美行业2023年度洞悉报告》(以下简称“报告”)显示,中国医美市场规模预计在2023年超过2000亿元,实现20%增速…...
geant4 常用代码
1 获取特特定能量范围的特定粒子 E:\examples_understanding\geant4-v11.0.0_note\examples\extended\runAndEvent\RE02 //-- Particle with kinetic energy filter.G4SDParticleWithEnergyFilter* pkinEFilter new G4SDParticleWithEnergyFilter(fltName"gammaE filter&…...
重要通知!eBay将升级买家满意度考核,如何让你的店铺脱颖而出?
8月份,eBay发布了重要通知,为促进跨境卖家积极提升买家体验,升级了针对卖家的买家满意度考核。其中,产品质量是买家满意度考核的核心,是中国卖家急需提升的重中之重,也是eBay考核的重点。 eBay将着眼于产品…...
PHP中pack、unpack的用法
pack string pack ( string $format [, mixed $args [, mixed $... ]] ) 该函数用来将对应的参数($args)打包成二进制字符串。 其中第一个参数$format,有如下选项: a 以NUL字节填充字符串空白 A 以SPACE(空格)填充字符串 h 十六进制字符串&…...
KUKA机器人零点标定的具体方法
KUKA机器人零点标定的具体方法 在进行机器人校正时,先将各轴置于一个定义好的机械位置,即所谓的机械零点。这个机械零点位置表明了同轴的驱动角度之间的对应关系,它用一个测量刻槽表示。 为了精确地确定机器人某根轴的机械零点位置,一般应先找到其预校正位置,然后去掉测量…...
基于SpringBoot+Vue的旅游系统
摘 要 随着旅游业的发展,越来越多的人选择旅游作为自己的出行方式。在旅游规划过程中,旅游景点选择是至关重要的环节。本文提出了一种基于协同过滤推荐算法的旅游平台系统。该系统采用前后端分离的设计,主要使用了SpringBoot、Vue等技术&…...
leetcode算法题--复杂链表的复制
原题链接:https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/description/?envTypestudy-plan-v2&envIdcoding-interviews 感觉一开始想到的办法还是比较笨 /*** Definition for a Node.* type Node struct {* Val int* Next *Node* …...
C++面试题(叁)---操作系统篇
目录 操作系统篇 1 Linux中查看进程运行状态的指令、查看内存使用情况的指令、 tar解压文件的参数。 2 文件权限怎么修改 3 说说常用的Linux命令 4 说说如何以root权限运行某个程序。 5 说说软链接和硬链接的区别。 6 说说静态库和动态库怎么制作及如何使用,区…...
算法笔记:KD树
1 引入原因 K近邻算法需要在整个数据集中搜索和测试数据x最近的k个点,如果一一计算,然后再排序,开销过大 引入KD树的作用就是对KNN搜索和排序的耗时进行改进 2 KD树 2.1 主体思路 以空间换时间,利用训练样本集中的样本点&…...
plumelog介绍与应用-一个简单易用的java分布式日志系统
官方文档:http://www.plumelog.com/zh-cn/docs/FASTSTART.html 简介 无代码入侵的分布式日志系统,基于log4j、log4j2、logback搜集日志,设置链路ID,方便查询关联日志基于elasticsearch作为查询引擎高吞吐,查询效率高全…...
百度网盘删除“我的应用数据”文件夹
百度网盘删除“我的应用数据”文件夹电脑端方法-2023.2.27成功 - 哔哩哔哩 (bilibili.com) 百度网盘怎样删除我的应用数据文件夹-手机端方法-2023.3.24日成功 - 哔哩哔哩 (bilibili.com)...
多店铺智能客服,助力店铺销量倍增
近年来电商发展得非常快速,市场竞争也是愈发激烈了。商家不仅需要提高产品和服务的质量,还要争取为自己获取更多的曝光,以此来分散运营的风险和降低经营的成本,所以越来越多的商家也开始转向多平台多店铺运营。但即使运营多个平台…...
会话跟踪技术
cookie 是通过在浏览器第一次请求服务器时,在响应中放入cookie,浏览器接收到cookie后保存在本地,之后每次请求服务器时都将cookie携带到请求头中,用来验证用户身份与状态等。 缺点: 移动端app没有cookiecookie保存在…...
递归算法学习——子集
目录 一,题目解析 二,例子 三,题目接口 四,解题思路以及代码 1.完全深度搜索 2.广度搜索加上深度优先搜索 五,相似题 1.题目 2.题目接口 3.解题代码 一,题目解析 给你一个整数数组 nums ,…...
学习笔记:ROS使用经验(ROS报错)
报错:进程崩溃 ] process has died [pid 734, exit code -5, cmd /root/catkin_ws/devel/lib/pose_graph/pose_graph __name:pose_graph __log:/root/.ros/log/31b0ae1c-3295-11ee-bda9-02429b5737dc/pose_graph-5.log]. log file: /root/.ros/log/31b0ae1c-3295-11…...
设计模式二十四:访问者模式(Visitor Pattern)
用于将数据结构与数据操作分离,使得可以在不修改数据结构的情况下,定义新的操作。访问者模式的核心思想是,将数据结构和操作进行解耦,从而使得新增操作时不必修改数据结构,只需添加新的访问者。主要目的是在不改变数据…...
使用gn+Ninja构建项目
使用下载编译好的gn和ninja报错 先下载了gn的源码[gn.googlesource.com/gn],然后编译报错,就直接下载了了编译号的gn和Ninja,然后写了Helloworld应用的BUILD.gn,然后将"gn\examples\simple_build\build"拷贝至当前目录…...
VMware虚拟机连不上网络
固定ip地址 进入网络配置文件 cd /etc/sysconfig/network-scripts 打开文件 vi ifcfg-ens33 编辑 BOOTPROTO设置为static,有3个值(decp、none、static) BOOTPROTO"static" 打开网络 ONBOOT"yes" 固定ip IPADDR1…...
安防视频监控/视频集中存储/云存储平台EasyCVR平台无法取消共享通道该如何解决?
视频汇聚/视频云存储/集中存储/视频监控管理平台EasyCVR能在复杂的网络环境中,将分散的各类视频资源进行统一汇聚、整合、集中管理,实现视频资源的鉴权管理、按需调阅、全网分发、云存储、智能分析等,视频智能分析平台EasyCVR融合性强、开放度…...
算法通关村-----如何基于数组和链表实现栈
实现栈的基本方法 push(T t)元素入栈 T pop() 元素出栈 Tpeek() 查看栈顶元素 boolean isEmpty() 栈是否为空 基于数组实现栈 import java.util.Arrays;public class ArrayStack<T> {private Object[] stack;private int top;public ArrayStack() {this.stack new…...
day-05 TCP半关闭 ----- DNS ----- 套接字的选项
一、优雅的断开套接字连接 之前套接字的断开都是单方面的。 (一)基于TCP的半关闭 Linux的close函数和windows的closesocket函数意味着完全断开连接。完全断开不仅不能发送数据,从而也不能接收数据。在某些情况下,通信双方的某一方…...
区块链金融项目怎么做?
区块链技术的兴起引发了金融领域的变革,为金融行业带来了前所未有的机遇与挑战。在这个快速发展的领域中,如何在区块链金融领域做出卓越的表现?本文将从专业性和思考深度两个方面,探讨区块链金融的发展路径,并为读者提…...
Redis与数据库保持一致
参考链接 先更新数据库,再更新redis 存在漏洞,如果更新Redis失败,仍然会导致不一致 先删Redis,再更新数据库并同步数据到Redis 存在漏洞,多线程情况下,线程1删除redis后,还是有可能被其他线程读取旧的数据…...
idea中vue项目 npm安装插件后node modules中找不到
从硬盘中重新加载一下...