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

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栈模拟实现队列 队列和栈的区别 栈和队列都是常用的数据结构&#xff0c;它们的…...

HarmonyOS应用开发者高级认证满分指南

声明&#xff1a;由于HarmonyOS应用开发者高级认证的题库一直在变&#xff0c;所以文章中的题目直做参考。 1. 判断题 云函数打包完成后&#xff0c;需要到APPGallery Connect创建对应函数的触发器才可以在端侧中调用。 【错】每一个自定义组件都有自己的生命周期。 【对】基…...

CSharp中Blazor初体验

Blazor 是一个由微软开发的开源 Web 框架&#xff0c;用于构建富客户端 Web 应用程序使用 C# 语言和 .NET 平台。Blazor 允许开发人员使用 C# 语言来编写前端 Web 应用程序&#xff0c;而不需要像传统的 JavaScript 框架&#xff08;如 Angular、React 或 Vue.js&#xff09;那…...

Linux下新建用户,并进行授权

注意&#xff1a;以下操作需要在root用户下&#xff01; 新增用户 adduser 用户名设置密码 passwd 用户名更改目录所有者命令 chown -R 用户名:用户名 目录更改目录权限命令 chmod -R 755 目录...

STM32为基础的模拟I2C通用8bit和16bit读取以及多字节读取

GPIO模拟I2C驱动的通用代码&#xff0c;I2C的寄存器地址有8位和16位的&#xff0c;主要解决了同一个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&#xff1a; 二叉搜索树的最小绝对差&#xff1a;力扣题目链接 给你一个二叉搜索树的根节点 root &#xff0c;返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数&#xff0c;其数值等于两值之差的…...

C++数据结构——二叉搜索树详解

目录 一&#xff0c;关于二叉搜索树 1.1 概念 1.2 基本结构 二&#xff0c;二叉搜索树接口实现 2.1 插入 2.2 查找 2.3 打印 2.4* 删除 三&#xff0c;二叉搜索树接口递归实现 3.1 查找 3.2 插入 3.3 删除 四&#xff0c;二叉搜索树的默认成员函数 五&#xff0c;…...

ros2机器人在gazebo中移动方案

原文连接Gazebo - Docs: Moving the robot (gazebosim.org) 很重要的地方&#xff1a;使用虚拟机运行Ubuntu的时候&#xff0c;需要关闭”加速3D图形“的那个选项&#xff0c;否则gazebo无法正常显示。 Moving the robot&#xff08;使用命令移动机器人示例&#xff09; In t…...

学习Java第74天,Ajax简介

什么是ajax AJAX Asynchronous JavaScript and XML&#xff08;异步的 JavaScript 和 XML&#xff09;。 AJAX 不是新的编程语言&#xff0c;而是一种使用现有标准的新方法。 AJAX 最大的优点是在不重新加载整个页面的情况下&#xff0c;可以与服务器交换数据并更新部分网页…...

【Java面试题】在Java中String,Stringbuffer,StringBuilder的区别?

Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍在Java中String&#xff0c;Stringbuffer&#xff0c;StringBuilder的区别以及部分理论知识 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f4dd;私信必回哟&#x1f601; &#x1f349;博主收将持续更新学习记录…...

让AIGC成为你的智能外脑,助力你的工作和生活

人工智能成为智能外脑 在当前的科技浪潮中&#xff0c;人工智能技术正在以前所未有的速度改变着我们的生活和工作方式。其中&#xff0c;AIGC技术以其强大的潜力和广泛的应用前景&#xff0c;正在引领着这场革命。 AIGC技术是一种基于人工智能的生成式技术&#xff0c;它可以通…...

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数据压缩

介绍 数据压缩是将原有数据通过某种压缩算法计算得到相对数据量小的过程。这种过程是可逆的&#xff0c;即能通过压缩后的数据恢复出原数据。数据压缩能够节省存储空间&#xff0c;减轻网络负载。 在即需要加密又需要压缩的情况下&#xff0c;必须先压缩再加密&#xff0c;次…...

SQLturning:定位连续值范围起点和终点

在上一篇blog说到&#xff0c;如何去优化查询连续值范围&#xff0c;没看过的朋友&#xff0c;上篇blog链接[在此]。(https://blog.csdn.net/weixin_42575078/article/details/135067645?spm1001.2014.3001.5501) 那么今天来说说怎么将连续的数据合并&#xff0c;然后返回合并…...

饥荒Mod 开发(十七):手动保存和加载,无限重生

饥荒Mod 开发(十六)&#xff1a;五格装备栏 饥荒Mod 开发(十八)&#xff1a;Mod 添加配置选项 饥荒游戏会自动保存&#xff0c;本来是一个好的机制&#xff0c;但是当角色死亡的时候存档会被删除&#xff0c;又要从头开始&#xff0c;有可能一不小心玩了很久的档就直接给整没了…...

Skywalking系列之最新版9.2.0-JavaAgent本地构建

MAC 10.15.7IDEA 2021.2skywalking-agent 9.2.0-SNAPSHOTJDK 17/21 (最新的代码要看最新的要求&#xff0c;注意不能使用JDK8&#xff0c;会构建失败)Maven 3.6.0 关于本地构建JavaAgent源码 1、获取源码&#xff0c;加载submodule 分步执行&#xff1a; git clone https:/…...

olap/clickhouse-编译器优化与向量化

本文主要结合15721和clickhouse源码来聊聊向量化&#xff0c;正好我最近也在用Eigen做算子加速&#xff0c;了解下还是有好处的。 提示编译器 提示编译器而不是复杂化简单的代码 什么时候使用汇编&#xff0c;什么时候使用SIMD&#xff1f;下面有几个基本原则&#xff1a; …...

RK3399平台开发系列讲解(内核入门篇)网络协议的分层

🚀返回专栏总目录 文章目录 一、应用层二、传输层三、网络层四、数据链路层(Data Link Layer)五、物理层沉淀、分享、成长,让自己和他人都能有所收获!😄 📢对于多数的应用和用户而言,使用互联网的一个基本要求就是数据可以无损地到达。用户通过应用进行网络通信࿰...

Idea远程debugger调试

当我们服务部署在服务器上&#xff0c;我们想要像在本地一样debug,就可以使用idea自带的Remote JVM Debug 创建Remote JVM Debug服务器启动jar打断点进入断点 当我们服务部署在服务器上&#xff0c;我们想要像在本地一样debug,就可以使用idea自带的 Remote JVM Debug) 创建Rem…...

MATLAB - Gazebo 仿真环境

系列文章目录 前言 机器人系统工具箱&#xff08;Robotics System Toolbox™&#xff09;为使用 Gazebo 模拟器可视化的模拟环境提供了一个界面。通过 Gazebo&#xff0c;您可以在真实模拟的物理场景中使用机器人进行测试和实验&#xff0c;并获得高质量的图形。 Gazebo 可在…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...