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

六、栈、栈的相关问题

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

前言

一、栈

1.栈概述

2.栈的实现

2.1 栈的API

2.2 栈的实现

二、栈的括号匹配问题

1.问题描述

2.代码实现

三、逆波兰表达式求值问题

1.问题描述

2.代码

总结


前言

提示:这里可以添加本文要记录的大概内容:

自学JAVA数据结构笔记,跟学视频为:黑马程序员Java数据结构与java算法全套教程,数据结构+算法教程全资料发布,包含154张java数据结构图_哔哩哔哩_bilibili


提示:以下是本篇文章正文内容,下面案例可供参考

一、栈

1.栈概述

栈是一种基于先进后出(FILO)的数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出 的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一 个数据被第一个读出来)。

2.栈的实现

2.1 栈的API

类名                 Stack

构造方法         Stack():创建Stack对象

成员方法         1.public boolean isEmpty():判断栈是否为空,是返回true,否返回false                         2.public int size():获取栈中元素的个数

                        3.public T pop():弹出栈顶元素

                        4.public void push(T t):向栈中压入元素t

成员变量         1.private Node head:记录首结点

                        2.private int N:当前栈的元素个数

2.2 栈的实现

package List;import java.util.Iterator;/*
*       使用链表实现栈
* */
public class Stack <T> implements Iterable<T>{private Node head;private int N;//结点类private class Node{private T item;private Node next;public Node(T item, Node next){this.item = item;this.next = next;}}//构造函数public Stack(){this.head = new Node(null,null);this.N = 0;}//判断栈是否为空public boolean isEmpty(){return N == 0;}//返回栈长度public int size(){return N;}//把t元素压入栈public void push(T t){//第一个结点Node first = head.next;//创建新结点//由于栈的特点是先入后出,使用新压入的结点为链表的第一个结点Node newNode = new Node(t,first);head.next = newNode;N ++;}//出栈public T pop(){//出栈结点Node curr = head.next;if(curr == null){return null;}//头结点的下一个结点指向要删除结点的下一个结点‘head.next = curr.next;N --;return curr.item;}//实现迭代器@Overridepublic Iterator<T> iterator() {return new STiterator();}private class STiterator implements Iterator{private Node curr;public STiterator(){this.curr = head;}@Overridepublic boolean hasNext(){return curr.next != null;}@Overridepublic Object next() {curr = curr.next;return curr.item;}}}

二、栈的括号匹配问题

1.问题描述

给定一个字符串,里边可能包含"()"小括号和其他字符,请编写程序检查该字符串的中的小括号是否成对出现。

例如:

        "(上海)(长安)":正确匹配

        "上海((长安))":正确匹配

        "上海(长安(北京)(深圳)南京)":正确匹配

        "上海(长安))":错误匹配

        "((上海)长安":错误匹配

2.代码实现

package Stack;import java.util.Scanner;public class BracketsMatch {public static void main(String[] args) {//创建字符串Scanner input = new Scanner(System.in);String str = "上海(长安))";//判断是否是有效括号boolean match = isMatch(str);if(match){System.out.println("正确匹配");}else{System.out.println("错误匹配");}}public static boolean isMatch(String str){//创建栈对象//1.创建一个栈用来存储左括号Stack<String> chars = new Stack<String>();//2.从左往右遍历字符串,拿到每一个字符for (int i = 0; i < str.length(); i++) {String curr = str.charAt(i) + "";//3.判断该字符是不是左括号,如果是,放入栈中存储if (curr.equals("(")) {chars.push(curr);} else if (curr.equals(")")) {//4.判断该字符是不是右括号,如果不是,继续下一次循环//5.如果该字符是右括号,则从栈中弹出一个元素t;String res = chars.pop();//6.判断元素t是否为null,如果不是,则证明有对应的左括号,如果不是,则证明没有对应的左括号if (res == null) {return false;}}}//7.循环结束后,判断栈中还有没有剩余的左括号,如果有,则不匹配,如果没有,则匹配return chars.size() == 0;}
}

三、逆波兰表达式求值问题

1.问题描述

逆波兰表达式求值问题是我们计算机中经常遇到的一类问题,要研究明白这个问题,首先我们得搞清楚什么是逆波 兰表达式?要搞清楚逆波兰表达式,我们得从中缀表达式说起。

中缀表达式:

中缀表达式就是我们平常生活中使用的表达式,例如:

1+3*2,2-(1+3)等等,

中缀表达式的特点是:二元运算符总 是置于两个操作数中间。

中缀表达式是人们最喜欢的表达式方式,因为简单,易懂。但是对于计算机来说就不是这样了,因为中缀表达式的 运算顺序不具有规律性。不同的运算符具有不同的优先级,如果计算机执行中缀表达式,需要解析表达式语义,做大量的优先级相关操作。

逆波兰表达式(后缀表达式):

逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法,后缀表 达式的特点:运算符总是放在跟它相关的操作数之后。

中缀表达式逆波兰表达式
a+bab+
a+(b-c)abc-+
a+(b-c)*dabc-d*+
a*(b-c)+dabc-*d+

2.代码

package Stack;public class ReversePolishNotation {public static void main(String[] args) {//中缀表达式3*(17-15)+18/6的逆波兰表达式如下String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};int result = caculate(notation);System.out.println("逆波兰表达式的结果为:" + result);}/*** @param notaion 逆波兰表达式的数组表示方式* @return 逆波兰表达式的计算结果*/public static int caculate(String[] notaion) {//1.创建一个栈对象oprands存储操作数Stack<Integer> oprands = new Stack<Integer>();//2.从左往右遍历逆波兰表达式,得到每一个字符串for (String curr : notaion) {//3.判断该字符串是不是运算符,如果不是,把该该操作数压入oprands栈中Integer o1;Integer o2;Integer result;switch (curr) {case "+"://4.如果是运算符,则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2,得到结果resultresult = o2 + o1;//6.把该结果压入oprands栈中oprands.push(result);break;case "-"://4.如果是运算符,则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2,得到结果resultresult = o2 - o1;//6.把该结果压入oprands栈中oprands.push(result);break;case "*"://4.如果是运算符,则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2,得到结果resultresult = o2 * o1;//6.把该结果压入oprands栈中oprands.push(result);break;case "/"://4.如果是运算符,则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2,得到结果resultresult = o2 / o1;//6.把该结果压入oprands栈中oprands.push(result);break;default:oprands.push(Integer.parseInt(curr));break;}}//7.遍历结束后,拿出栈中最终的结果返回Integer result = oprands.pop();return result;}
}

总结

提示:这里对文章进行总结:
 

相关文章:

六、栈、栈的相关问题

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、栈 1.栈概述 2.栈的实现 2.1 栈的API 2.2 栈的实现 二、栈的括号匹配问题 1.问题描述 2.代码实现 三、逆波兰表达式求值问题 1.问题描述 2.代码 总结 前言 提…...

Java安全停止线程

Thread 类虽提供了一个 stop() 方法&#xff08;已经被废弃&#xff09;&#xff0c;但由于 stop() 方法强制终止一个正在执行的线程&#xff0c;可能会造成数据不一致的问题&#xff0c;所以在生产环境中最好不要使用。 场景&#xff1a; 由于一些操作需要轮询处理&#xff…...

12 readdir 函数

前言 在之前 ls 命令 中我们可以看到, ls 命令的执行也是依赖于 opendir, readdir, stat, lstat 等相关操作系统提供的相关系统调用来处理业务 因此 我们这里来进一步看一下 更细节的这些 系统调用 我们这里关注的是 readdir 这个函数, 入口系统调用是 getdents 如下调试…...

Windows环境搭建Android开发环境-Android Studio/Git/JDK

Windows环境搭建Android开发环境-Android Studio/Git/JDK 因为休假回来后公司的开发环境由Ubuntu变为了Windows&#xff0c;所以需要重新配置一下开发环境。 工作多年第一次使用Windows环境进行开发工作&#xff0c;作次记录下来。 一、 Git安装 1.1git 标题软件下载 网址&…...

全国爱耳日丨听力受损严重有哪些解决办法

——【科学爱耳护耳&#xff0c;实现主动健康】随着数码电子设备使用越来越方便、日常使用时间越来越长&#xff0c;听力障碍、患上耳道疾病一系列问题也接踵而至&#xff0c;在当下我们必须重视听力健康&#xff0c;采取更科学的听音方式&#xff0c;保护听力健康&#xff0c;…...

【抽水蓄能电站】基于粒子群优化算法的抽水蓄能电站的最佳调度方案研究(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

【异常】因多租户字段缺少导致Error updating database. Column ‘tenant_id‘ cannot be null

一、报错内容 org.springframework.dao.DataIntegrityViolationException: ### Error updating database. Cause: java.sql.SQLIntegrityConstraintViolationException: Column tenant_id cannot be null ### The error may exist in com/xxx/cloud/mall/admin/mapper/Goods…...

类和对象(上)

文章目录 面向对象的初步认知类的实例化this引用对象的构造及初始化封装static成员代码块内部类 对象的打印一、面向对象的初步认知 Java是一门纯面向对象的语言(Object Oriented Program&#xff0c;简称OOP)&#xff0c;在面向对象的世界里&#xff0c;一切皆为对象。在java中…...

Java经典面试题——谈谈 Java 反射机制,动态代理是基于什么原理?

典型回答 反射机制是 Java 语言提供的一种基本功能&#xff0c;赋予程序在运行时 自省&#xff08;introspect&#xff0c;官方用语&#xff09;的能力。通过反射我们可以直接操作类或者对象&#xff0c;比如获取某个对象的类定义&#xff0c;获取类声明的属性和方法&#xff…...

19 客户端服务订阅机制的核心流程

Nacos客户端服务订阅机制的核心流程 说起Nacos的服务订阅机制&#xff0c;大家会觉得比较难理解&#xff0c;那我们就来详细分析一下&#xff0c;那我们先从Nacos订阅的概述说起 Nacos订阅概述 Nacos的订阅机制&#xff0c;如果用一句话来描述就是&#xff1a;Nacos客户端通…...

教师论文|科技专著管理系统

技术&#xff1a;Java、JSP等摘要&#xff1a;随着计算机和互联网技术的发展&#xff0c;社会的信息化程度越来越高&#xff0c;各行各业只有适应这种发展趋势&#xff0c;才能增强自己的适应能力和竞争能力&#xff0c;不断发展壮大。大学作为教育的基地&#xff0c;是社会进步…...

骨传导耳机是什么意思,骨传导耳机的好处具体有哪些

​在这个全民都是手机的时代&#xff0c;各种蓝牙耳机&#xff0c;入耳式耳机&#xff0c;真无线耳机等各种款式琳琅满目。而骨传导耳机是一种全新的科技产物&#xff0c;顾名思义就是通过头骨振动将声音传至外耳内的耳机。由于无需入耳&#xff0c;不会对耳朵造成任何影响。那…...

elasticsearch—使用汇总

文档结构1、概念简介2、使用创景3、核心组件4、环境部署5、操作实践官方网站&#xff1a;https://www.elastic.co/cn/elasticsearch/ 官方手册&#xff1a;https://www.elastic.co/guide/en/elasticsearch/reference/8.6/getting-started.html 参考教程&#xff1a; A&#xff…...

聊一聊代码重构——我们为什么要代码重构

代码重构 事情的起因是在去年下半年&#xff0c;我们终于无法承受往年的历史包袱而决定开始进行代码重构。 在以前我们尝试过进行代码重构但是从来没有系统性的考虑过如何重构。在对代码重构的过程中很多经验都是来自《重构&#xff1a;改善既有代码的设计》这本书&#xff0c;…...

【Python学习笔记】第二十九节 Python2 和Python3发生了哪些变化

Python 版本分为两大流派&#xff0c;一个是 Python 2.x 版本&#xff0c;另外一个是 Python 3.x 版本&#xff0c;Python 官方同时提供了对这两个版本的支持和维护。2020 年 1 月 1 日&#xff0c;Python 官方终止了对 Python 2.7 版本&#xff08;最后一个 Python 2.x 版本&a…...

[oeasy]python0099_雅达利大崩溃_IBM的开放架构_兼容机_oem

雅达利大崩溃 回忆上次内容 个人计算机浪潮已经来临 苹果公司迅速发展微软公司脱离mits准备做纯软件公司IBM用大型机思路制作的5100惨败 Commodore 64 既做计算机又做游戏机 计算机行业和游戏行业 跟随着底层技术不断迭代已经进入了战乱纷纷的年代最终又会如何呢&#xff1f…...

学术论文投稿之同行评审过程中可能会遭遇哪些偏见?

同行评审过程的顺利进行&#xff0c;在很大程度上取决于学术界的积极参与和相互信任&#xff0c;以及需要参与各方都以负责任的态度行事。作为审稿专家&#xff0c;向作者提供公正、客观的评价是至关重要的。同行评审过程中&#xff0c;若有任何偏离客观性的行为&#xff0c;均…...

Python写一个自动发送直播弹幕的工具,非常简单

哈喽大家好&#xff0c;今天给大家用Python整一个可以在直播间自动发弹幕的工具&#xff0c;来为喜欢的主播疯狂扣6 &#xff01; 事情原由昨晚回家&#xff0c;表弟在看LOL直播&#xff0c;看得我气不打一处来&#xff0c;差点就想锤他。 身为程序员的表弟&#xff0c;看直…...

学生档案管理系统的设计与实现

技术&#xff1a;Java、JSP等摘要&#xff1a;本设计是为托普学院学生档案的管理实现电子化而设计的&#xff0c;系统开发采用J2EE技术&#xff0c;数据库采用了SQL Server 2005&#xff0c;因而系统具有很好的扩展性、可移植性&#xff0c;实现了教学资源的信息化管理。主要功…...

JavaEE学习笔记-SpringBoot快速上手、部分注解解释

SpringBoot快速上手 一、快速创建SpringBoot应用1.1利用IDEA提供的Spring Initializr创建Spring Boot应用1.2Spring Boot生成的项目结构介绍1.3初步测试后端是否OK(建立一个controll类)二、热部署2.1 添加依赖2.2 Setting处项目自动化设置2.3 具体项目设置2.4 待选步骤三、注…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...