【数据结构面试题】栈与队列的相互实现
目录
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…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...

基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...