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

数据结构——栈(Stack)详解

1. 栈(Stack)

1.1 概念

栈:一种特殊的线性表,只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中数据元素遵循后进先出LIFO(Last In First Out)的原则

压栈:栈的插入操作可以叫做进栈、压栈、入栈,入数据在栈顶

出栈:栈的删除操作叫做出栈,出数据在栈顶

1.2 栈的使用

方法功能
Stack()构造一个空的栈
E push(E e)将e入栈并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空
    public static void main(String[] args) {Stack<Integer> s = new Stack<>();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());//获取栈中有效数据System.out.println(s.peek());//查看栈顶元素System.out.println(s.pop());//使栈顶元素出栈System.out.println(s.empty());//检测栈是否为空System.out.println(s.isEmpty());//检测栈是否为空,继承自Vector}
System.out.println(s.isEmpty());

上面的isEmpty()方法,查看源码,虽然栈中没有,但是栈继承自Vector,在父类Vector中,有isEmpty方法

1.3 栈的模拟实现

import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public MyStack() {this.elem = new int[10];}public void push(int val) {if(isFull()) {//扩容elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;usedSize++;}public boolean isFull(){return usedSize == elem.length;}public int pop() {if(empty()) {return -1;}int oldVal = elem[usedSize-1];usedSize--;return oldVal;}public int peek() {if(empty()) {return -1;}return elem[usedSize-1];}public boolean empty() {return usedSize == 0;}
}

使用泛型实现

import java.util.Arrays;public class MyStack<E> {public Object[] elem;public int usedSize;public MyStack() {this.elem = new Object[10];}public void push(E val) {if(isFull()) {//扩容elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;usedSize++;}public boolean isFull(){return usedSize == elem.length;}public E pop() {if(empty()) {return null;}E oldVal = (E)elem[usedSize-1];usedSize--;return oldVal;}public E peek() {if(empty()) {return null;}return (E)elem[usedSize-1];}public boolean empty() {return usedSize == 0;}
}

1.4 栈的应用场景

1.将递归转化为循环

    //递归方式public void printList(Node head) {if(null != head) {printList(head.next);System.out.println(head.val + " ");}}//运用栈的循环方式public 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.println(s.pop().val + " ");}}

2. 括号匹配

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();//创建字符类型栈for(int i = 0; i < s.length(); i++) {//遍历字符串,将字符串中字符取出char ch = s.charAt(i);//1.遇到左括号,入栈if(ch == '(' || ch == '[' || ch == '{') {stack.push(ch);}else {//2.遇到右括号//先判断栈是否为空if(stack.empty()) {return false;}else {//3.取栈顶左括号看与当前右括号是否匹配char chL = stack.peek();if(chL == '(' && ch == ')' || chL == '[' && ch == ']' || chL == '{' && ch == '}') {stack.pop();//若左右括号匹配,则栈顶元素出栈}else {return false;}}}}return stack.empty();//最后若栈为空,返回true,栈不为空,返回false}
}

3. 逆波兰表达式求值

解析:

逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点:

  • 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

将中缀表达式转换为后缀表达式的方法:

当逆波兰式运用到栈中,按照次序将数字入栈,若遇到运算符,则取出栈顶两个数字,先取出为运算符右边操作数,后取出为运算符左边操作数(这是为了避免当运算符为 - 或 / 时,顺序不同造成结果不同的问题),如下图:

代码:

    public int evalRPN(String[] tokens) {Stack<Integer> s = new Stack<>();for (int i = 0; i < tokens.length; i++) {String tmp = tokens[i];if(!isOpearation(tmp)) {//判断当前字符串是否为运算符Integer val = Integer.valueOf(tmp);//将字符串转换为数字s.push(val);}else {Integer val2 = s.pop();Integer val1 = s.pop();switch(tmp) {case "+":s.push(val1+val2);break;case "-":s.push(val1-val2);break;case "*":s.push(val1*val2);break;case "/":s.push(val1/val2);break;}}}return s.pop();}public boolean isOpearation(String s) {if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {return true;}return false;}

4. 出栈入栈次序匹配

    public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> s = new Stack<>();int count = 0;for(int i = 0; i < pushV.length; i++) {s.push(pushV[i]);//这个单独的循环,必须保证栈不为空,count不能越界,栈顶元素等于count下标处值while(!s.empty() && count != popV.length && s.peek() == popV[count]){s.pop();count++;}}return s.empty();}

5. 最小栈

class MinStack {Stack<Integer> s;//普通栈,泛型类型别忘记加!!!Stack<Integer> ms;//最小栈public MinStack() {//构造方法s = new Stack<>();ms = new Stack<>();}public void push(int val) {s.push(val);if(ms.empty()) {//若为第一次入栈操作,则最小栈无条件入栈ms.push(val);}else {Integer peekVal = ms.peek();//若不是第一次,则需与最小栈栈顶元素进行比较if(val <= peekVal) {ms.push(val);}}}public void pop() {if(s.empty()) {return;}int popVal = s.pop();//包装类属于引用类型,不能直接==,所以此处用int接收,自动拆箱if(popVal == ms.peek()) {ms.pop();}}public int top() {if(s.empty()) {return -1;}return s.peek();}public int getMin() {if(ms.empty()) {return -1;}return ms.peek();}
}

1.5 栈、虚拟机栈、栈帧的区别

栈(Stack):是一种只允许在一端进行插入或删除的线性表,满足后进先出的特点

虚拟机栈:逻辑结构,是具有特殊作用的一块内存空间,主管Java程序的运行,它保存方法的局部变量(8种基本数据类型、对象的引用地址)、部分结果,并参与方法的调用和返回

栈帧:函数从调用过程到结束的体现,一个函数从调用到销毁中占用的空间,内部的局部变量统一放在栈帧中。每个函数在运行时,JVM都会创建一个栈帧,然后将栈帧压入到虚拟机栈中,当函数调用结束时,该函数对应的栈帧会从虚拟机栈中出栈

相关文章:

数据结构——栈(Stack)详解

1. 栈&#xff08;Stack&#xff09; 1.1 概念 栈&#xff1a;一种特殊的线性表&#xff0c;只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中数据元素遵循后进先出LIFO(Last In First Out)的原则 压栈&am…...

1.Element的table表高度自适应vue3+js写法

解决方法 在页面table上添加id&#xff0c;动态计算每页table的最大高度 &#xff0c;将高度保存在store中&#xff0c;每次切换路由时进行计算。 文章目录 解决方法前言一、页面table使用二、store状态库1.引入库 效果 前言 提示&#xff1a;状态管理使用的是pinia,用法参考…...

联想电脑电池只能充到80%,就不在充电了,猛一看以为坏了,只是设置了养护模式。

现在电池管理模式有三种&#xff1a; 1&#xff09;常规 2&#xff09;养护 3&#xff09;快充 好久没有用联想的电脑了&#xff0c;猛一看&#xff0c;咱充到了80%不充了&#xff0c;难道电池是坏的&#xff1f;我们要如何设置才可以让其充电到100%呢&#xff1f; 右下角…...

Unity接入PS5手柄和Xbox手柄以及Android平台的(以及不同平台分析)

Unity接入PS5手柄和Xbox手柄以及Android平台的&#xff08;以及不同平台分析&#xff09; 介绍Unity手柄小知识PC端和编辑器上的摇杆事件和滑动事件PS5手柄Xbox手柄北通手柄 安卓环境下&#xff08;安卓手机或者安卓模拟器&#xff09;PS5手柄Xbox手柄北通手柄 总结 介绍 最近…...

vue+java实现简易AI问答组件(基于百度文心大模型)

一、需求 公司想要在页面中加入AI智能对话功能&#xff0c;故查找免费gpt接口&#xff0c;最终决定百度千帆大模型&#xff08;进入官网、官方文档中心&#xff09;&#xff1b; 二、主要功能列举 AI智能对话&#xff1b;记录上下文回答环境&#xff1b;折叠/展开窗口&#…...

刷代码随想有感(104):动态规划——01背包问题/二维dp数组

题干&#xff1a; 代码&#xff1a; #include<bits/stdc.h> using namespace std; int n,bagweight; void solve(){vector<int>weight(n, 0);vector<int>value(n, 0);for(int i 0; i < n; i){cin>>weight[i];}for(int j 0; j < n; j){cin>…...

Docker-Portainer可视化管理工具

Docker-Portainer可视化管理工具 文章目录 Docker-Portainer可视化管理工具介绍资源列表基础环境一、安装Docker二、配置Docker加速器三、拉取Portainer汉化版本镜像四、运行容器五、访问可视化界面 介绍 Portainer是一款开源的容器管理平台&#xff0c;它提供了一个直观易用的…...

SqlSugar 集成

1 关于 SqlSugar SqlSugar 是 .NET/C# 平台非常优秀的 ORM 框架&#xff0c;目前 Nuget 总下载突破 700K&#xff0c;Github 关注量也高达 3.2K&#xff0c;是目前当之无愧的国产优秀 ORM 框架之一。 SqlSugar 官方地址&#xff1a;果糖网 &#xff08; SqlSugar 官网 &#…...

MySQL Connector/C++ 和 MySQL Connector/ODBC 的区别

MySQL Connector/C++ 和 MySQL Connector/ODBC 是两种不同的数据库连接工具,它们各自有不同的特点和用途。以下是它们之间的一些主要区别: 1. **编程接口**: - MySQL Connector/C++ 提供了面向对象的编程接口,它是用C++编写的,提供了C++特有的类和对象来与MySQL数据库…...

Weevil-Optimizer象鼻虫优化算法的matlab仿真实现

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 Weevil-Optimizer象鼻虫优化算法的matlab仿真实现&#xff0c;仿真输出算法的优化收敛曲线&#xff0c;对比不同的适应度函数。 2.测试软件版本以及运行结果展示…...

Web前端项目-交互式3D魔方【附源码】

交互式3D魔方 ​ 3D魔方游戏是一款基于网页技术的三维魔方游戏。它利用HTML、CSS和JavaScript前端技术来实现3D效果&#xff0c;并在网页上呈现出逼真的魔方操作体验。 运行效果&#xff1a; 一&#xff1a;index.html <!DOCTYPE html> <html><head><…...

视频格式转换avi格式怎么弄?分享视频转换方法

视频格式转换avi格式怎么弄&#xff1f;AVI作为一种广泛支持的视频格式&#xff0c;能够在多种设备和播放器上顺畅播放&#xff0c;确保我们的视频内容能够无障碍地分享给朋友或上传至各大平台。其次&#xff0c;AVI格式通常具有较好的兼容性&#xff0c;能够避免格式转换过程中…...

UniRx 入门

Reactive X 是 Reactive Extensions 的缩写&#xff0c;一般简写为 Rx&#xff0c;最初是 LINQ 的一个扩展&#xff0c;由微软的团队开发&#xff0c;Rx 是一个编程模型&#xff0c;目标是提供一致的编程接口&#xff0c;帮助开发者更方便的处理异步数据流&#xff0c;支持大部…...

简单游戏制作——飞行棋

控制台初始化 int w 50; int h 50; ConsoleInit(w, h); static void ConsoleInit(int w, int h) {//基础设置//光标的隐藏Console.CursorVisible false;//舞台的大小Console.SetWindowSize(w, h);Console.SetBufferSize(w, h); } 场景选择相关 #region 场景选择相关 //声…...

等保一体机

等保一体机是面向等保场景推出的合规型安全防护产品。基于“一个中心&#xff0c;三重防护”的设计理念&#xff0c;通过内置全面、多样的安全能力&#xff0c;为政府、医疗、教育、企业等中小型客户提供快速合规、按需赋能的一站式等保合规解决方案。 等保一体机要求管理网络和…...

什么是寄存器文件(Register File)?

寄存器文件&#xff08;Register File&#xff09;是计算机系统中用于存储处理器操作数的小型、快速的存储单元集。它在 CPU 内部&#xff0c;提供极高的访问速度&#xff0c;通常用于存储临时数据、操作数和指令执行过程中的中间结果。 寄存器文件的组成和特点 寄存器集&…...

6月15号作业

使用手动连接&#xff0c;将登录框中的取消按钮使用第二中连接方式&#xff0c;右击转到槽&#xff0c;在该槽函数中&#xff0c;调用关闭函数 将登录按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff0…...

零基础入门学用Arduino 第三部分(三)

重要的内容写在前面&#xff1a; 该系列是以up主太极创客的零基础入门学用Arduino教程为基础制作的学习笔记。个人把这个教程学完之后&#xff0c;整体感觉是很好的&#xff0c;如果有条件的可以先学习一些相关课程&#xff0c;学起来会更加轻松&#xff0c;相关课程有数字电路…...

Trusty qemu + android环境搭建详细步骤

下载源码 mkdir trusty cd trusty repo init -u https://android.googlesource.com/trusty/manifest -b master repo sync -j32 编译 ./trusty/vendor/google/aosp/scripts/build.py generic-arm64 查看编译结果 ls build-root/build-generic-arm64/lk.bin 安装运行依赖 …...

杀戮尖塔游戏

Java 你正在玩策略卡牌杀戮尖塔游戏&#xff0c;轮到你出牌&#xff0c;手里N张攻击卡&#xff0c;每张都需要花金币coust[i]和获得伤害dmager[i]。 最多花3金币能造成的最大伤害是多少&#xff1f; class Solution{public int calc(int[] cost, int[] dmager, N){int[][] db …...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...