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

【数据结构面试题】栈与队列的相互实现

目录

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.队列实现栈

用队列实现栈icon-default.png?t=N7T8https://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. 用栈实现队列

描述: 

用栈实现队列icon-default.png?t=N7T8https://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…...

华为认证和红帽认证哪个比较好考呢

华为认证和红帽认证的考试难度、学习内容、适用范围等方面都有所不同&#xff0c;因此哪个比较好考要视具体情况而定&#xff1a; 考试难度&#xff1a;红帽认证的考试难度较高&#xff0c;需要考生具备较高的技术水平和实践经验&#xff1b;而华为认证则更注重基础知识的考察…...

[Java]_[中级]_[使用okhttp3和HttpClient代理访问外部网络]

场景 Java的http库常用的有HttpClient和Okhttp3, 如果公司有限制网络访问&#xff0c;需要代理才可以访问外网&#xff0c;那么如何使用代理Proxy&#xff1f; <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient<…...

ubuntu 20.04 docker 安装 mysql

要在Ubuntu 20.04上安装Docker并运行MySQL容器&#xff0c;您可以按照以下步骤操作&#xff1a; 1.更新系统包列表&#xff1a; sudo apt update2.安装Docker&#xff1a; sudo apt install docker.io3.启动Docker服务并设置其开机自启动&#xff1a; sudo systemctl start…...

C++在C语言基础上的优化

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

分享一个python实验室设备预约管理系统 实验室设备维修系统源码 lw 调试

&#x1f495;&#x1f495;作者&#xff1a;计算机源码社 &#x1f495;&#x1f495;个人简介&#xff1a;本人七年开发经验&#xff0c;擅长Java、Python、PHP、.NET、微信小程序、爬虫、大数据等&#xff0c;大家有这一块的问题可以一起交流&#xff01; &#x1f495;&…...

兵者多诡(HCTF2016)

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

【JAVA-Day04】Java关键字和示例:深入了解常用关键字的用法

Java关键字和示例&#xff1a;深入了解常用关键字的用法 摘要Java 关键字、标识符和命名规范一、Java 关键字常用关键字DEMO1. 示例代码使用 if 和 else 关键字&#xff1a;2. 示例代码使用 for 循环&#xff1a;3. 示例代码使用 switch 关键字&#xff1a;4. 示例代码使用 wh…...

Android请求网络报错:not permitted by network security policy

一、错误记录 https的接口请求正常的&#xff0c; 请求http的接口时报错&#xff1a;not permitted by network security policy 二、问题分析 原因&#xff1a; 由于 Android P(版本27以上) 限制了明文流量的网络请求&#xff0c;非加密的流量请求都会被系统禁止掉。如果当…...

python报错:ImportError: urllib3 v2.0 only supports OpenSSL 1.1.1

python报错&#xff1a;ImportError: urllib3 v2.0 only supports OpenSSL 1.1.1 问题分析 说明&#xff1a;requests包引入了urllib3&#xff0c;而新版本的urllib3 需要OpenSSL 1.1.1以上版本&#xff0c;否则报错&#xff1a; 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 题目-中等难度 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p…...

Git常见问题:git pull 和 git pull --rebase二者区别

git pull 和 git pull --rebase 都是从远程仓库获取最新的更改并将其合并到本地分支。但它们之间的区别在于合并方式。以下是它们之间的主要区别&#xff1a; git pull&#xff1a; 当你执行 git pull 时&#xff0c;Git 会执行以下两个操作&#xff1a; git fetch&#xff…...

关于HarmonyOS元服务的主题演讲与合作签约

一、感言 坚持中&#xff0c;总会有很多意想不到的收获。 前几次参与HDC时更多的是观众、开发者、专家的身份&#xff0c;以参观、学习、交流为主。 通过几年的努力&#xff0c;和HarmonyOS功能成长&#xff0c;在2023年的HDC大会中&#xff0c;有了我的演讲&#xff0c;并带领…...

cache 学习

好文章&#xff1a; Cache的基本原理 - 知乎...

SSM - Springboot - MyBatis-Plus 全栈体系(六)

第二章 SpringFramework 四、SpringIoC 实践和应用 3. 基于 注解 方式管理 Bean 3.1 实验一&#xff1a;Bean 注解标记和扫描 (IoC) 3.1.1 注解理解 和 XML 配置文件一样&#xff0c;注解本身并不能执行&#xff0c;注解本身仅仅只是做一个标记&#xff0c;具体的功能是框…...

【Flutter】引入网络图片时,提示:Failed host lookup: ‘[图片host]‘

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

Python基础教程:索引和切片

前言 嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 索引&#xff08;下标&#xff09; 索引又称下标&#xff0c;用来表示可迭代对象中的某个元素的位置。 用正整数表示的索引值&#xff0c;从左向右定位&#xff0c;从 0 开始计数&#xff0c;如 0&#xff0c;1&#…...

JVM基础面试题

JDK、JRE、JVM的关系 JVM Java虚拟机&#xff0c;它只识别.class类型文件&#xff0c;它能将class文件中的字节码指令进行识别并调用操作系统向上的API完成动作。 JRE Java运行时环境。它主要包含两部分&#xff1a;Jvm的标准实现和Java的一些基本类库。相对于JVM来说,JRE多出来…...

蓝桥杯官网填空题(平方末尾)

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 能够表示为某个整数的平方的数字称为“平方数” 虽然无法立即说出某个数是平方数&#xff0c;但经常可以断定某个数不是平方数。 因为平方数的末位只可能是&#x…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

相机从app启动流程

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

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

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、运行以下命令卸载所有冲突的软件包&#xff1a; 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的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看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&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

基于Java+MySQL实现(GUI)客户管理系统

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