数据结构——栈的实现(java实现)与相应的oj题
文章目录
- 一 栈
- 栈的概念:
- 栈的实现:
- 栈的数组实现
- 默认构造方法
- 压栈
- 获取栈元素的个数
- 出栈
- 获取栈顶元素
- 判断当前栈是否为空
- java提供的Stack类
- Stack实现的接口:
- LinkedList也可以当Stack使用
- 虚拟机栈,栈帧,栈的三个概念
- 二 栈的一些算法题:
- (1) 逆序打印单链表。
- (2)[括号匹配](https://leetcode-cn.com/problems/valid-parentheses)
- (3)[逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)
- 逆波兰表达式
- (4) [出入栈次序匹配](https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking)
- (5)[最小栈](https://leetcode-cn.com/problems/min-stack/)
- 总结:
一 栈
栈的概念:
栈也是一种线性表,栈只允许在表的一端进行插入与删除操作,所以栈中数据的特征的先进后出(先进来的后出去)。
栈顶:是栈进行插入与删除操作的表的一端
栈底:不允许插入删除操作的一端
压栈:将数据插入到栈中
出栈:将数据移除栈
栈的实现:
栈的底层可以由数组实现,也可以由链表实现
栈由数组实现时,栈的压栈与出栈的时间复杂度均为O(1)。
栈由单链表实现时,
如果采用尾插法,压栈操作时间复杂度为O(n),如果有last指针,则
压栈时间复杂度为O(1),但是出栈的时间复杂度一定为O(n)。
如果采用头插法,则压栈与出栈的时间复杂度均为O(1).
栈由双链表实现时,不论采用头插法与尾插法,时间复杂度均为O(1)。
栈的数组实现
当栈使用数组实现时,栈的插入与删除操作,时间复杂度均为O(1);
public class MyStack {static int DEFAULT_SIZE = 10; //设置默认的数组大小private int [] element ; //实现栈的数组int usedsize = 0 ; //栈中有效元素的个数//默认构造方法public MyStack() {}//入栈public void push(int val) {}//出栈public int pop() {}//获取栈顶元素 但是不删除public int peek() { }//获取栈元素个数public int size(){} //判空public boolean isEmpty() { }
}
默认构造方法
默认申请10个空间
public MyStack(){this.element = new int[10];}
压栈
思想:先判断栈满没满,如果满了则扩容,然后进行压栈
public void push(int data){//先判断栈是否有空间if(usedsize==element.length){//如果没有空间//则扩容this.element = Arrays.copyOf(element,2*element.length);}//保证空间后this.element[usedsize++] = data;}
获取栈元素的个数
思想:直接返回usedsize
public int size(){return usedsize;}
出栈
思想:先判断栈是否为空,为空则抛出异常,不为空,则返回栈顶元素值,并且usedsize-1.
public int pop(){//要判断栈是否为空,如果为空,则退出try{if (isEmpty()) {//2. 问题出现,构造参数的形参问题,super()调用父类的构造方法throw new EmptyException("EmptyException异常报错");}}catch (EmptyException e){e.printStackTrace();}int val = this.element[usedsize-1];usedsize -- ;return val;}
获取栈顶元素
思想:与出栈逻辑相同,只是usedsize值不需-1 。
public int peek(){try{if (isEmpty()) {throw new EmptyException("EmptyException异常报错");}}catch (EmptyException e){e.printStackTrace();}return this.element[usedsize-1];}
判断当前栈是否为空
思想:直接判断usedsize 是否为0即可。
public boolean isEmpty(){return usedsize == 0;}
java提供的Stack类
Stack实现的接口:
接口说明 1. 继承Cloneable接口支持克隆其他接口,暂时还没搞明白,以后更新补充
LinkedList也可以当Stack使用
java提供的LinkedList类也可以当做栈来使用,LinkedList的方法列表如下:
public class Test {public static void main(String[] args) {LinkedList<Integer> stack = new LinkedList<>();stack.push(5);stack.push(2);stack.pop();stack.pop();stack.pop();}
}
虚拟机栈,栈帧,栈的三个概念
虚拟机栈是JVM中的一块内存。
栈帧是为一个方法,函数分配的内存。
栈是一种数据结构。
二 栈的一些算法题:
(1) 逆序打印单链表。
采用递归的方法:
// 递归方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}
采用栈的方法:
void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}
// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}
}
(2)括号匹配
题解:1 . 对于这个题无法直接看出其数学模型,必须先画图,列出各种情况,再判断
从图中可以分析出,要实现判断括号匹配
- 就要使得每一个左括号和右括号能够与对应位置的右括号进行匹配判断
- 且当所有的左括号(右括号)判断完时,其对应的右括号(左括号)也判断完毕,即满足左括号个数与右括号个数相当的情况。
- 如果第一个括号是右括号,说明此括号没有对应的左括号,说明一定为字符串一定括号不匹配。
实现思想:遍历字符串,遇到左括号则存入栈中,遇到右括号则与栈顶元素比较,相匹配,则继续循环,如果不匹配或栈为空,则返回false。
class Solution1 {public boolean isValid(String s) {Stack <Character> stack = new Stack<>();//采用for循环,这样可以找到字符串中的字符for(int i =0;i<s.length();i++) {char ch = s.charAt(i);if (ch == '{' || ch == '[' || ch == '(') {//问题,java提供的栈是否需要手动扩容?stack.push(ch);} else {//如果是右括号的内容if (stack.isEmpty()) {return false;} else {char ch2 = stack.peek(); //当获取栈顶元素时,栈可能为空//栈区不能为空if (((ch == '}' && ch2 == '{') || (ch == ']' && ch2 == '[') || (ch == ')' && ch2 == '('))) {//说明匹配,//将栈顶的元素去除stack.pop();} else {//如果不匹配,情况1 如果栈中还没有左括号,则一定不匹配,return false;}}}}// 如果栈表为空,说明匹配完毕if(stack.isEmpty()){return true;}return false;}
}
(3)逆波兰表达式求值
逆波兰表达式
逆波兰表达式即后缀表达式,后缀表达式是由中缀表达式转换而成。
所谓中缀表达式即我们平常所写的±*/的算式
我们平常所写的中缀表达式中是有优先级的,即先乘除,后加减,有括号先算括号里面的
但是计算机是不能够识别优先级的,为了能够使计算机计算,我们将中缀表达式的规则
表达成后缀表达式的形式,这样计算机便能够计算算式。
中缀表达式转换成后缀表达式的的规则:
- 先将中缀表达式中能够加括号的部分都加上括号
- 然后将所有的运算符移到所在 最近扩号之外。
- 然后去除掉所有括号即得到后缀表达式。
后缀表达式的运算规则:
遍历整个表达式,遇到运算符时,则将运算符前面的两个数作为操作数计算
得出的结果替代两个操作数,然后继续遍历表达式,循环上次操作。
本题:只是要求按照后缀表达式的规则计算结果
实现思想:遍历表达式,遇到操作数即将操作数压入栈中,遇到运算符,则进行两次出栈
,获取两个操作数进行计算(需要注意的是第一次出栈的是右操作数,第二次出栈的是左操作数)
然后将计算的结果再进行压栈,然后循环此操作。
class Solution {public int evalRPN(String[] tokens) {//创建一个栈,创建栈时不需要考虑栈的空间大小Stack<Integer> stack = new Stack<>();//采用foreach进行遍历栈for (String str : tokens) {if (!isOperator(str)) {int a = Integer.parseInt(str);stack.push(a);} else {int val2 = stack.pop();int val1 = stack.pop();//如果为运算符switch (str) {case "+" : stack.push(val1 + val2);break;case "-" : stack.push(val1 - val2);break;case "*" : stack.push(val1 * val2);break;case "/" : stack.push(val1 / val2);break;}}}return stack.peek();}
总结
1. 字符串形式的运算符不能直接转换成运算符
2. 后缀表达式先进栈的是左操作数,后进栈的是右操作数,当我们需要出栈时,第一次获取栈顶元素是右操作数,第二次获取栈顶元素才是左操作数。
(4) 出入栈次序匹配
class Solution2{public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i< pushV.length;i++) {stack.push(pushV[i]);while(!stack.empty() && j < popV.length &&stack.peek() == popV[j]) {stack.pop();j++;}}return stack.empty();}
}
(5)最小栈
题解:
如果只用一个栈的话,我们不可能实现题目的要求,只有能将栈的最小值时刻储存起来才能实现题目的要求。因此我们实现两个栈,一个栈用于存储数据,另一个最小栈用于存放栈当前的最小值。
实现思想:入栈的规则:
- 普通栈一定要放,最小栈如果为空,或者栈顶元素小于压入的数据,则放入最小栈中
- 如果压入的数据与最小栈栈顶元素相当,也放入最小栈中。(因为最小栈中的元素必须与普通栈的最小值保持同步即必须与出栈的规则相匹配)。
出栈的规则:
如果普通栈的栈顶元素与最小栈栈顶元素相同,则最小栈也需要出栈。
class MinStack {//创建两个栈Stack <Integer> stack = new Stack<>(); //普通栈Stack <Integer> minStack = new Stack<>();//最小栈public MinStack() {}
public void push(int val) {//压栈,压入数据//普通栈一定要压入stack.push(val);//然后判断最小栈是否压入if(minStack.empty()){minStack.push(val);}else{if(val<=minStack.peek()){minStack.push(val);}}}public void pop() {//出栈//普通栈一定出栈int val = stack.pop();//最小栈出栈://如果两栈的栈顶元素相同,则出栈if(val == minStack.peek()){minStack.pop();}}public int top() {//获取栈顶元素if(!stack.empty()){return stack.peek();}return -1 ;}public int getMin() {if(minStack.empty()){return -1;}return minStack.peek();}}
总结:
在使用栈时,最常用的运用是根据栈先进后出的特性,将一段有序的数据转为逆序后,再进行操作使用。
相关文章:

数据结构——栈的实现(java实现)与相应的oj题
文章目录 一 栈栈的概念:栈的实现:栈的数组实现默认构造方法压栈获取栈元素的个数出栈获取栈顶元素判断当前栈是否为空 java提供的Stack类Stack实现的接口: LinkedList也可以当Stack使用虚拟机栈,栈帧,栈的三个概念 二 栈的一些算…...
linux修改时区为CST
目录 第一步: 第二步: 第三步: 第一步: 备份原来的时区信息 [rootlocalhost ~]# mv /etc/localtime localtime.bak 第二步: 通过软链接将亚洲/上海 的时区信息 指导时区信息 [rootlocalhost ~]# ln -s /usr/share…...
【Spring Security】初识Spring Security
今天晚上因为一个项目问题,而正式开始学习Spring Security。 这个问题是“APP端的操作员应仅可查看管理后台的项目负责人分配给自己的计划”。 一、Spring Security的核心组件: Spring Security的核心组件包括:SecurityContextHolder、Auth…...

配置单区域OSPF
目录 引言 一、搭建基础网络 1.1 配置网络拓扑图如下 1.2 IP地址表 二、测试每个网段都能单独连通 2.1 PC0 ping通Router1所有接口 2.2 PC1 ping通Router1所有接口 2.3 PC2 ping通Router2所有接口 2.4 PC3 ping通Router2所有接口 2.5 PC4 ping通Router3所有接口 2.…...
SQL中的游标是什么?
在 SQL 中,游标(Cursor)是一种用于遍历结果集的数据库对象。它允许开发者在 SQL 查询的结果集中逐行或逐批处理数据。 具体来说,SQL 中的游标通常用于以下目的: 遍历结果集:当一个 SQL 查询返回多行结果时…...

7. LangChain4j如何使用统一api调用?
前言 当我们对接LangChain4j的时候,面对复杂的各种各样的大模型的api的对接,让很多开发者感到力不从心。在每个大模型的api都不一样的时候?该如何快捷的切换模型的使用呢? 这时,One-API应运而生,它以其简洁…...

RPM、YUM 安装 xtrabackup 8 (mysql 热备系列一)包含rpm安装 mysql 8 配置主从
RPM安装 percona-xtrabackup-80-8.0.35-30.1.el7.x86_64.rpm 官网: https://www.percona.com/ 下载地址: https://www.percona.com/downloads wget https://downloads.percona.com/downloads/percona-distribution-mysql-ps/percona-distribution-mysq…...

maven项目打成可运行的jar及pom中的依赖一同打包
maven项目打jar及pom中的依赖一同打包 最近开发中有个需求,不部署新的服务,只jar包执行 那maven项目中,代码如何以jar的方式运行、如何把代码打成jar、pom中的依赖如何与代码一同打到jar包中? 1、代码如何以jar的方式运行&…...

Gettler‘s Screep World 笔记 Ⅰ
夏促时候刚刚入坑,写个笔记叭~ 环境配置 参考 HoPGoldy 大佬的简书,先配置下开发环境 萌新去看大佬的详细教程,我这里比较简单,有前端基础的可以直接抄 VSCode 跳过 node 我配的是v18.18.2 换源 npm config set registry h…...
联合体(union)的定义以及如何与结构体(struct)不同
联合体(Union)是一种特殊的数据类型,它允许在相同的内存位置存储不同的数据类型。但是,在任何给定的时间点,联合体只能存储其中的一个值;这意味着联合体的大小是其最大成员的大小,因为它必须足够…...

【Spark官方文档部分翻译】RDD编程指南(RDD Programming Guide)
写在前面 内容如何选择 本翻译只翻译本人认为精华的部分,本人认为的Spark的一些核心理念,编程思想。一些特别基础的操作包括但不限于搭建环境就不在此赘述了。 配套版本 本系列基于Spark 3.3.1,Scala 2.12.10,进行翻译总结 原…...

前端八股文 $set
为什么会有$set vue2中对数组中新增的属性是监听不到的 如图 vue 插件中有但是 视图中没有刷新 解决方法 解决就是 $set() 就是在数组中新增属性的时候可以重新渲染视图 具体的写法 写法 就是 第一个 是在那个对象上新增 第二个参数 是新增的属性 第三个参数是 新增的属性…...

Connecting weaviate with langflow across docker containers
题意:在Docker容器之间连接Weaviate与Langflow 问题背景: I am trying to build a local RAG application using Langflow. For my vectore store, I want to use a local Weaviate instance, hosted in a separate docker container on the same netwo…...
【linux vim使用说明】
基本概念 提示:本文是网络资源整理 模式: vim 有多种模式,每种模式都有不同的功能。 普通模式 (Normal Mode): 默认模式,用于导航和执行命令。插入模式 (Insert Mode): 用于文本输入。可以通过按 i 进入。可视模式 (Visual Mode): 用于选择…...

cocos2d-x安装和项目
首先多方查找资料发现教程很简洁,发现对自己的操作方面没多大帮助,后来干脆去官网,好像也很简洁。基于这样一个原因,加上我首次碰cocos2d-x,决定记录一下整个流程,解决实际操作上的疑惑。 涉及的方面&…...

因果推断 | 双重机器学习(DML)算法原理和实例应用
文章目录 1 引言2 DML算法原理2.1 问题阐述2.2 DML算法 3 DML代码实现3.1 策略变量为0/1变量3.2 策略变量为连续变量 4 总结5 相关阅读 1 引言 小伙伴们,好久不见呀。 距离上次更新已经过去了一个半月,上次发文章时还信誓旦旦地表达自己后续目标是3周更…...
Flutter 开源库学习
网上看了好多歌词实现逻辑相关资料,封装比较的好的 就 flutter_lyric,核心类是LyricsReader,而且如果实现逐字逐句歌词编辑功能还需要自己实现很多细节 ,网友原话是 :歌词的功能真的是不少,写起来也是挺难的…...

自主巡航,目标射击
中国机器人及人工智能大赛 参赛经验: 自主巡航赛道 【机器人和人工智能——自主巡航赛项】动手实践篇-CSDN博客 主要逻辑代码 #!/usr/bin/env python #coding: utf-8import rospy from geometry_msgs.msg import Point import threading import actionlib impor…...
MySQL中EXPLAIN关键字详解
昨天领导突然问到,MySQL中explain获取到的type字段中index和ref的区别是什么。 这两种状态都是在使用索引后产生的,但具体区别却了解不多,只知道ref相比于index效率更高。 因此,本文较为详细地记录了MySQL性能中返回字段的含义、状…...
如何理解ref toRef和toRefs
是什么 ref 生成值类型的响应式数据可用于模板和reactive通过.value修改值 ref也可以像vue2中的ref那样使用 toRef 针对一个响应式对象(reactive)的prop创建一个ref两者保持引用关系 toRefs 将响应式对象(reactive封装)转换…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...

【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...