【数据结构面试题】栈与队列的相互实现
目录
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…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
