【数据结构面试题】栈与队列的相互实现
目录
1.队列实现栈
1.1创建栈
1.2判断是否为空
1.3入栈
1.4出栈
1.5获取栈顶元素
1.6完整代码
2. 用栈实现队列
2.1创建队列
2.2判断是否为空
2.3入队列
2.4出队列
2.5获取队头元素
2.6完整代码
1.队列实现栈
用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/
描述:
方法:我们用两个队列来实现栈
整体思路:
1.1创建栈
代码:
public class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack(){qu1=new LinkedList<>();qu2=new LinkedList<>();}}
1.2判断是否为空
只要qu1与qu2都为null时,栈就为空
代码:
public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
1.3入栈
(1)我们对两个队列进行检查,那个队列不为空,我们就把元素放在那个队里
(2)若元素都为空,则我们把元素放在qu1里
代码:
public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()) {qu2.offer(x);} else {qu1.offer(x);}}
1.4出栈
(1)我们对两个队列进行检查,若都为空,返回-1。
(2)只要不是(1)则先检查qu1,再先检查qu2,将不为空的队列出size-1个元素到另一个队列里
代码:
public int pop() {if (empty()) {return -1;}if(!qu1.isEmpty()){int size=qu1.size() ;for (int i = 0; i <size-1; i++) {int val=qu1.poll();qu2.offer(val);}return qu1.poll();} else {int size=qu2.size() ;for (int i = 0; i <size-1; i++) {int val=qu2.poll();qu1.offer(val);}return qu2.poll();}}
1.5获取栈顶元素
与出栈方法类似
public int top() {if (empty()) {return -1;}if(!qu1.isEmpty()){int val=-1;int size=qu1.size() ;for (int i = 0; i <size; i++) {val=qu1.poll();qu2.offer(val);}return val;} else {int val=-1;int size=qu2.size() ;for (int i = 0; i <size; i++) {val=qu2.poll();qu1.offer(val);}return val;}}
1.6完整代码
import java.util.LinkedList;
import java.util.Queue;public class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()) {qu2.offer(x);} else {qu1.offer(x);}}public int pop() {if (empty()) {return -1;}if(!qu1.isEmpty()){int size=qu1.size() ;for (int i = 0; i <size-1; i++) {int val=qu1.poll();qu2.offer(val);}return qu1.poll();} else {int size=qu2.size() ;for (int i = 0; i <size-1; i++) {int val=qu2.poll();qu1.offer(val);}return qu2.poll();}}public int top() {if (empty()) {return -1;}if(!qu1.isEmpty()){int val=-1;int size=qu1.size() ;for (int i = 0; i <size; i++) {val=qu1.poll();qu2.offer(val);}return val;} else {int val=-1;int size=qu2.size() ;for (int i = 0; i <size; i++) {val=qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}
2. 用栈实现队列
描述:
用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/
方法:两个栈来实现队列
2.1创建队列
public class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}
}
2.2判断是否为空
只要stack1与stack2都为null时,队列就为空
public boolean empty() {return stack1.empty()&&stack2.empty();}
2.3入队列
入栈的元素全部放入stack1中
public void push(int x) {stack1.push(x);}
2.4出队列
出栈时,检查stack2是否为null,若为null,则直接将stack1的元素出栈后入到stack2里
然后弹出栈顶元素即可
public int pop() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.pop();}
2.5获取队头元素
public int peek() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}
2.6完整代码
import java.util.Stack;public class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}
以上为我个人的小分享,如有问题,欢迎讨论!!!
都看到这了,不如关注一下,给个免费的赞
相关文章:

【数据结构面试题】栈与队列的相互实现
目录 1.队列实现栈 1.1创建栈 1.2判断是否为空 1.3入栈 1.4出栈 1.5获取栈顶元素 1.6完整代码 2. 用栈实现队列 2.1创建队列 2.2判断是否为空 2.3入队列 2.4出队列 2.5获取队头元素 2.6完整代码 1.队列实现栈 用队列实现栈https://leetcode.cn/problems/impleme…...
华为认证和红帽认证哪个比较好考呢
华为认证和红帽认证的考试难度、学习内容、适用范围等方面都有所不同,因此哪个比较好考要视具体情况而定: 考试难度:红帽认证的考试难度较高,需要考生具备较高的技术水平和实践经验;而华为认证则更注重基础知识的考察…...
[Java]_[中级]_[使用okhttp3和HttpClient代理访问外部网络]
场景 Java的http库常用的有HttpClient和Okhttp3, 如果公司有限制网络访问,需要代理才可以访问外网,那么如何使用代理Proxy? <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient<…...
ubuntu 20.04 docker 安装 mysql
要在Ubuntu 20.04上安装Docker并运行MySQL容器,您可以按照以下步骤操作: 1.更新系统包列表: sudo apt update2.安装Docker: sudo apt install docker.io3.启动Docker服务并设置其开机自启动: sudo systemctl start…...

C++在C语言基础上的优化
目录 一、命名空间 1、命名空间的定义 2、命名空间的使用 二、输入&输出 三、缺省参数 1、缺省参数的概念 2、缺省参数的分类 四、函数重载 五、引用 1.引用的概念 2.引用的特性 3、引用和指针的区别 六、内联函数 七、基于范围的for循环 一、命名空间 命名空…...

分享一个python实验室设备预约管理系统 实验室设备维修系统源码 lw 调试
💕💕作者:计算机源码社 💕💕个人简介:本人七年开发经验,擅长Java、Python、PHP、.NET、微信小程序、爬虫、大数据等,大家有这一块的问题可以一起交流! 💕&…...

兵者多诡(HCTF2016)
环境:https://github.com/MartinxMax/CTFer_Zero_one 题目简介 解题过程 登录首页 提交png图片上传抓包,可以看到是向upload文件提交数据 在fp参数中尝试伪协议读取home.php文件 http://127.0.0.1:88/HCTF2016-LFI/home.php?fpphp://filter/readconvert.base64…...

【JAVA-Day04】Java关键字和示例:深入了解常用关键字的用法
Java关键字和示例:深入了解常用关键字的用法 摘要Java 关键字、标识符和命名规范一、Java 关键字常用关键字DEMO1. 示例代码使用 if 和 else 关键字:2. 示例代码使用 for 循环:3. 示例代码使用 switch 关键字:4. 示例代码使用 wh…...
Android请求网络报错:not permitted by network security policy
一、错误记录 https的接口请求正常的, 请求http的接口时报错:not permitted by network security policy 二、问题分析 原因: 由于 Android P(版本27以上) 限制了明文流量的网络请求,非加密的流量请求都会被系统禁止掉。如果当…...
python报错:ImportError: urllib3 v2.0 only supports OpenSSL 1.1.1
python报错:ImportError: urllib3 v2.0 only supports OpenSSL 1.1.1 问题分析 说明:requests包引入了urllib3,而新版本的urllib3 需要OpenSSL 1.1.1以上版本,否则报错: ImportError: urllib3 v2.0 only supports Ope…...
如何使用adb command来设置cpu频率和核数
透過ADB Shell設定CPU開核與freq的command與用法如下: # Disable PPM echo 0 > /proc/ppm/enabled # Enable PPM (Default) echo 1 > /proc/ppm/enabled echo 0 > /proc/ppm/enabled Fixed # Core for each cluster echo X Y > /proc/ppm/policy/ut_fix_core_num …...

236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先 题目-中等难度示例1. dfs 题目-中等难度 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p…...
Git常见问题:git pull 和 git pull --rebase二者区别
git pull 和 git pull --rebase 都是从远程仓库获取最新的更改并将其合并到本地分支。但它们之间的区别在于合并方式。以下是它们之间的主要区别: git pull: 当你执行 git pull 时,Git 会执行以下两个操作: git fetchÿ…...

关于HarmonyOS元服务的主题演讲与合作签约
一、感言 坚持中,总会有很多意想不到的收获。 前几次参与HDC时更多的是观众、开发者、专家的身份,以参观、学习、交流为主。 通过几年的努力,和HarmonyOS功能成长,在2023年的HDC大会中,有了我的演讲,并带领…...
cache 学习
好文章: Cache的基本原理 - 知乎...

SSM - Springboot - MyBatis-Plus 全栈体系(六)
第二章 SpringFramework 四、SpringIoC 实践和应用 3. 基于 注解 方式管理 Bean 3.1 实验一:Bean 注解标记和扫描 (IoC) 3.1.1 注解理解 和 XML 配置文件一样,注解本身并不能执行,注解本身仅仅只是做一个标记,具体的功能是框…...

【Flutter】引入网络图片时,提示:Failed host lookup: ‘[图片host]‘
在使用 NetworkImage 组件加载外部图片时,提示 Failed host lookup: [图片host] 错误。 排查方向 1、清理缓存 解决方案: 尝试flutter clean清空缓存后重新安装依赖flutter pub get重新构建项目flutter create . 走完上述三个步骤后,再次…...

Python基础教程:索引和切片
前言 嗨喽,大家好呀~这里是爱看美女的茜茜呐 索引(下标) 索引又称下标,用来表示可迭代对象中的某个元素的位置。 用正整数表示的索引值,从左向右定位,从 0 开始计数,如 0,1&#…...

JVM基础面试题
JDK、JRE、JVM的关系 JVM Java虚拟机,它只识别.class类型文件,它能将class文件中的字节码指令进行识别并调用操作系统向上的API完成动作。 JRE Java运行时环境。它主要包含两部分:Jvm的标准实现和Java的一些基本类库。相对于JVM来说,JRE多出来…...
蓝桥杯官网填空题(平方末尾)
题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 能够表示为某个整数的平方的数字称为“平方数” 虽然无法立即说出某个数是平方数,但经常可以断定某个数不是平方数。 因为平方数的末位只可能是&#x…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...