Java 栈和队列的交互实现
文章目录
- 队列和栈的区别
- 一.用队列模拟实现栈
- 1.1入栈
- 1.2出栈
- 1.3返回栈顶元素
- 1.4判断栈是否为空
- 二.用栈模拟实现队列
- 2.1 入队
- 2.2出队
- 2.3peek
- 2.4判断队列是否为空
- 三.完整代码
- 3.1 队列模拟实现栈
- 3.2栈模拟实现队列
队列和栈的区别
栈和队列都是常用的数据结构,它们的主要区别在于数据的插入和删除顺序。
栈 (Stack) 是一种后进先出 (Last-In-First-Out, LIFO) 的数据结构,只允许在一端进行插入和删除操作,这一端称为栈顶。新元素插入后成为新的栈顶,而删除时也只能删除栈顶元素。
队列 (Queue) 是一种先进先出 (First-In-First-Out, FIFO) 的数据结构,允许在两端进行插入和删除操作,插入在队尾,删除在队头。新元素插入时成为新的队尾,而删除时也只能删除队头元素。
一.用队列模拟实现栈
1.void push(int x) 将元素 x 压入栈顶。
2.int pop() 移除并返回栈顶元素。
3.int top() 返回栈顶元素。
4.boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
如上便是需要用队列来实现栈的四个基本操作。
我们试想,实现这些栈的操作,一个队列可以完成吗?
显然不可以,我们使用两个队列来实现栈的模拟

大体流程
1.入栈时:
如果两个都为空,那么想
1.1入栈
当我们要放入18 25 35 48 这一串数字入栈时,先放入18 25 35(放入时选择的队列是不为空的队列),模拟入队以及入栈时的状况,如下图

public void push(int x) {if(empty()){queue1.offer(x);return;}if(!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}
1.2出栈
此时如果我们要将35出栈时,又该如何操作呢?此时我们就需要用到第二个队列,将队列一的前size-1个元素(也就是18 25)从队列一中出队,放入队列二中。此时队列一中的元素为35,队列二的元素为18 25 如下图。

当初栈完成时,我们此时要将48入栈时,又该放入哪个栈中呢?我们考虑栈的特点(先入后出),我们将再入栈的元素放到不为空的队列中。

public int pop() {if(empty()){return -1;}if(!queue1.isEmpty()){int size = queue1.size();for (int i = 0; i < size-1; i++) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size = queue2.size();for (int i = 0; i < size-1; i++) {queue1.offer(queue2.poll());}return queue2.poll();}}
1.3返回栈顶元素
在实现pop的基础上,我们将声明一个变量temp来储存每次要移除的元素。
public int top() {if(empty()){return -1;}if (!queue1.isEmpty()){int temp = -1;int size = queue1.size();for (int i = 0; i < size; i++) {temp = queue1.poll();queue2.offer(temp);}return temp;}else {int size = queue2.size();int temp = -1;for (int i = 0; i < size; i++) {temp = queue2.poll();queue1.offer(temp);}return temp;}}
1.4判断栈是否为空
当队列一和队列二都为空时,此时栈就为空。
public boolean empty() {return queue1.isEmpty()&&queue2.isEmpty();}
二.用栈模拟实现队列
我们也是用两个栈来模拟实现队列
2.1 入队
我们将所有入队的元素都放入栈一中,如下图

public void push(int x) {stack1.push(x);}
2.2出队
要出栈时,如果栈二不为空,就出栈二中的元素,如果栈二为空,将栈一中的所有元素一次性的全部push到栈二中,此时就将入栈的元素全部倒转过来了,(例如入栈时在栈中的入栈顺序依次排序为18 25 35,栈二中此时的元素入栈顺序是35 25 18,出栈时就先出18,就完成了转换)如下图

public int pop() {if(empty()){return -1;}if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}
2.3peek
peek只是将出队时的pop换成peek,就可以完成要求。
public int peek() {if(empty()){return -1;}if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}
2.4判断队列是否为空
如果栈一和栈二都为空时,那么队列就为空。
public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
三.完整代码
3.1 队列模拟实现栈
class MyStack {Queue<Integer> queue1 ;Queue<Integer> queue2 ;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {if(empty()){queue1.offer(x);return;}if(!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}public int pop() {if(empty()){return -1;}if(!queue1.isEmpty()){int size = queue1.size();for (int i = 0; i < size-1; i++) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size = queue2.size();for (int i = 0; i < size-1; i++) {queue1.offer(queue2.poll());}return queue2.poll();}}public int top() {if(empty()){return -1;}if (!queue1.isEmpty()){int temp = -1;int size = queue1.size();for (int i = 0; i < size; i++) {temp = queue1.poll();queue2.offer(temp);}return temp;}else {int size = queue2.size();int temp = -1;for (int i = 0; i < size; i++) {temp = queue2.poll();queue1.offer(temp);}return temp;}}public boolean empty() {return queue1.isEmpty()&&queue2.isEmpty();}
}
3.2栈模拟实现队列
class MyQueue {public Stack<Integer> stack1 ;public 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.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()){return -1;}if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}
相关文章:
Java 栈和队列的交互实现
文章目录 队列和栈的区别一.用队列模拟实现栈1.1入栈1.2出栈1.3返回栈顶元素1.4判断栈是否为空 二.用栈模拟实现队列2.1 入队2.2出队2.3peek2.4判断队列是否为空 三.完整代码3.1 队列模拟实现栈3.2栈模拟实现队列 队列和栈的区别 栈和队列都是常用的数据结构,它们的…...
HarmonyOS应用开发者高级认证满分指南
声明:由于HarmonyOS应用开发者高级认证的题库一直在变,所以文章中的题目直做参考。 1. 判断题 云函数打包完成后,需要到APPGallery Connect创建对应函数的触发器才可以在端侧中调用。 【错】每一个自定义组件都有自己的生命周期。 【对】基…...
CSharp中Blazor初体验
Blazor 是一个由微软开发的开源 Web 框架,用于构建富客户端 Web 应用程序使用 C# 语言和 .NET 平台。Blazor 允许开发人员使用 C# 语言来编写前端 Web 应用程序,而不需要像传统的 JavaScript 框架(如 Angular、React 或 Vue.js)那…...
Linux下新建用户,并进行授权
注意:以下操作需要在root用户下! 新增用户 adduser 用户名设置密码 passwd 用户名更改目录所有者命令 chown -R 用户名:用户名 目录更改目录权限命令 chmod -R 755 目录...
STM32为基础的模拟I2C通用8bit和16bit读取以及多字节读取
GPIO模拟I2C驱动的通用代码,I2C的寄存器地址有8位和16位的,主要解决了同一个MCU同时处理8位和16位寄存器地址芯片时候的驱动问题。 typedef enum {IIC_8BIT_BASE_ADDR,IIC_16BIT_BASE_ADDR }iic_bits_e; typedef struct {uint8_t DevAddr;uint16_t RegA…...
算法训练营Day19
#Java #二叉树 #双指针 开源学习资料 Feeling and experiences: 二叉搜索树的最小绝对差:力扣题目链接 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数,其数值等于两值之差的…...
C++数据结构——二叉搜索树详解
目录 一,关于二叉搜索树 1.1 概念 1.2 基本结构 二,二叉搜索树接口实现 2.1 插入 2.2 查找 2.3 打印 2.4* 删除 三,二叉搜索树接口递归实现 3.1 查找 3.2 插入 3.3 删除 四,二叉搜索树的默认成员函数 五,…...
ros2机器人在gazebo中移动方案
原文连接Gazebo - Docs: Moving the robot (gazebosim.org) 很重要的地方:使用虚拟机运行Ubuntu的时候,需要关闭”加速3D图形“的那个选项,否则gazebo无法正常显示。 Moving the robot(使用命令移动机器人示例) In t…...
学习Java第74天,Ajax简介
什么是ajax AJAX Asynchronous JavaScript and XML(异步的 JavaScript 和 XML)。 AJAX 不是新的编程语言,而是一种使用现有标准的新方法。 AJAX 最大的优点是在不重新加载整个页面的情况下,可以与服务器交换数据并更新部分网页…...
【Java面试题】在Java中String,Stringbuffer,StringBuilder的区别?
Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍在Java中String,Stringbuffer,StringBuilder的区别以及部分理论知识 🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁 🍉博主收将持续更新学习记录…...
让AIGC成为你的智能外脑,助力你的工作和生活
人工智能成为智能外脑 在当前的科技浪潮中,人工智能技术正在以前所未有的速度改变着我们的生活和工作方式。其中,AIGC技术以其强大的潜力和广泛的应用前景,正在引领着这场革命。 AIGC技术是一种基于人工智能的生成式技术,它可以通…...
ubuntu12.04 源
替换 /etc/apt/sources.list deb http://old-releases.ubuntu.com/ubuntu precise main restricted universe multiverse deb http://old-releases.ubuntu.com/ubuntu precise-security main restricted universe multiverse deb http://old-releases.ubuntu.com/ubu…...
openssl数据压缩
介绍 数据压缩是将原有数据通过某种压缩算法计算得到相对数据量小的过程。这种过程是可逆的,即能通过压缩后的数据恢复出原数据。数据压缩能够节省存储空间,减轻网络负载。 在即需要加密又需要压缩的情况下,必须先压缩再加密,次…...
SQLturning:定位连续值范围起点和终点
在上一篇blog说到,如何去优化查询连续值范围,没看过的朋友,上篇blog链接[在此]。(https://blog.csdn.net/weixin_42575078/article/details/135067645?spm1001.2014.3001.5501) 那么今天来说说怎么将连续的数据合并,然后返回合并…...
饥荒Mod 开发(十七):手动保存和加载,无限重生
饥荒Mod 开发(十六):五格装备栏 饥荒Mod 开发(十八):Mod 添加配置选项 饥荒游戏会自动保存,本来是一个好的机制,但是当角色死亡的时候存档会被删除,又要从头开始,有可能一不小心玩了很久的档就直接给整没了…...
Skywalking系列之最新版9.2.0-JavaAgent本地构建
MAC 10.15.7IDEA 2021.2skywalking-agent 9.2.0-SNAPSHOTJDK 17/21 (最新的代码要看最新的要求,注意不能使用JDK8,会构建失败)Maven 3.6.0 关于本地构建JavaAgent源码 1、获取源码,加载submodule 分步执行: git clone https:/…...
olap/clickhouse-编译器优化与向量化
本文主要结合15721和clickhouse源码来聊聊向量化,正好我最近也在用Eigen做算子加速,了解下还是有好处的。 提示编译器 提示编译器而不是复杂化简单的代码 什么时候使用汇编,什么时候使用SIMD?下面有几个基本原则: …...
RK3399平台开发系列讲解(内核入门篇)网络协议的分层
🚀返回专栏总目录 文章目录 一、应用层二、传输层三、网络层四、数据链路层(Data Link Layer)五、物理层沉淀、分享、成长,让自己和他人都能有所收获!😄 📢对于多数的应用和用户而言,使用互联网的一个基本要求就是数据可以无损地到达。用户通过应用进行网络通信...
Idea远程debugger调试
当我们服务部署在服务器上,我们想要像在本地一样debug,就可以使用idea自带的Remote JVM Debug 创建Remote JVM Debug服务器启动jar打断点进入断点 当我们服务部署在服务器上,我们想要像在本地一样debug,就可以使用idea自带的 Remote JVM Debug) 创建Rem…...
MATLAB - Gazebo 仿真环境
系列文章目录 前言 机器人系统工具箱(Robotics System Toolbox™)为使用 Gazebo 模拟器可视化的模拟环境提供了一个界面。通过 Gazebo,您可以在真实模拟的物理场景中使用机器人进行测试和实验,并获得高质量的图形。 Gazebo 可在…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
