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

数据结构-Stack和栈

news 来源：原创 2025/5/21 18:26:18

1.栈

1.1什么是栈

栈是一种特殊的线性表，只允许在固定的一段进行插入和删除操作，进行插入和删除操作的一段称为栈顶，另一端称为栈底。

栈中的数据元素遵顼后进先出LIFO（Last In First Out）的原则，就像一叠盘子，只能在顶部添加或移除盘子。

压栈：栈的插入操作叫做压栈/进栈/入栈，新插入的元素在栈顶。

出战：栈的删除操作叫做出栈，要删除的元素在栈顶。

从图上观察发现：无论是插入还是删除操作，栈底的位置不发生变化，但是栈顶的位置会随插入或删除操作而发生变化。

1.2栈的常用方法

在Java标准库中提供了java.util.Stack（栈的实现类），此处的常用方法指的是Stack的常用方法。

Stack的常用方法如下表所示：

方法	解释
Stack()	构造方法，构造一个空的栈
E push(E,e)	将元素e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素的个数
boolean empty()	检验栈是否为空

注意：

pop()是删除元素，并返回删除（删除前的栈顶元素）的元素

peek()是获取栈顶元素并返回，不进行出栈操作

常用方法的代码演示：

public class Test {public static void main(String[] args) {Stack<String> stack=new Stack<>();//入栈stack.push("My");stack.push("name");stack.push("is");stack.push("hajimi");//获取栈中有效元素的个数-->4System.out.println(stack.size());//获取栈顶元素-->hajimi  遵循后进先出System.out.println(stack.peek());//peek方法不会改变栈中的元素个数System.out.println(stack.size());//出栈String deleteElem=stack.pop();//获取栈中有效元素的个数-->3System.out.println(stack.size());//判断栈是否为空-->falseSystem.out.println(stack.isEmpty());}
}

2.Stack

2.1什么是Stack

Java提供了多种方式来实现栈，包括使用java.util.Stack类，使用Deque接口，或者手动实现栈。

java.util.Stack是Java标准库中提供的一个栈实现类。它继承自Vector类，是一个线程安全的栈实现。

2.2 Stack的特点

1.线程安全：

由于Stack继承自Vector，它的所有方法都是同步的(线程安全的)。

2.动态扩容：

Stack的底层是Vector，它会根据需要进行动态扩容。

这是Vector的动态扩容方法的原码：

2.3 Stack的局限性

虽然Stack提供了很方便的栈操作，但仍存在一些局限性：

1.继承自Vector：Stack继承自Vector，意味着它继承了一些与栈无关的方法，可能会导致误用

2.性能问题：由于Stack是线程安全的，它的同步机制可能会导致性能的下降，尤其是单线程环境中

2.4实现一个Stack

Stack的底层是Vector，而Vector的底层是数组，接下来我们来编写自己的"Stack"。

代码编写：

package datastructure;import java.util.Arrays;public class MyStack2 {//用来存放栈中的元素private int[] elem;//计算栈中有效元素的个数private int usedSize;//默认初始容量private static final int DEFAULT_SIZE=10;public MyStack2(){this.elem=new int[DEFAULT_SIZE];}//判断栈是否已满private boolean isFull(){return elem.length==usedSize;}//判断栈是否为空private boolean isEmpty(){return usedSize==0;}//元素入栈方法public void push(int val){//判断栈是否已满，如果已满进行扩容if(isFull()){Arrays.copyOf(elem,2*elem.length);}//将元素压入，并将有效元素的个数加一elem[usedSize++]=val;}//元素出栈操作public int pop(){if(isEmpty()){System.out.println("栈中没有元素，无法进行出栈操作");return Integer.MAX_VALUE;}//获取栈顶元素，即要删除的元素int deleteElem=elem[usedSize-1];usedSize--;return deleteElem;}//获取栈顶元素public int peek(){if(isEmpty()){System.out.println("栈为空，无法获取栈顶元素");return Integer.MAX_VALUE;}return elem[usedSize-1];}//计算栈中元素的个数public int size(){return usedSize;}
}

对上述的代码进行运行测试：

public class Test {public static void main(String[] args) {MyStack2 myStack2=new MyStack2();myStack2.push(1);myStack2.push(2);myStack2.push(3);myStack2.push(4);myStack2.push(5);System.out.println("当前栈中元素的个数:"+myStack2.size());System.out.println("获取栈顶元素:"+myStack2.peek());System.out.println("进行出栈:"+myStack2.pop());System.out.println("当前栈中元素的个数:"+myStack2.size());System.out.println("获取栈顶元素:"+myStack2.peek());}
}

运行结果：

3.栈，虚拟机栈，栈帧

概念区分：栈，虚拟机栈和栈帧

栈：一种数据结构，遵循后进先出（LIFO）的原则，允许在栈顶进行元素的插入和删除操作，常用于括号匹配，表达式求值，深度优先搜索等场景。

虚拟机栈：Java虚拟机（JVM）运行时数据区的一部分，用于存储方法调用，局部变量。每个线程都具有一个自己的虚拟机栈，虚拟机栈中存储的是栈帧

栈帧：是虚拟机栈中的一个条目，用于存储方法调用的相关信息。每个方法调用都会创建一个栈帧，并将其压入虚拟机栈，方法结束后，栈帧会被弹出。

4.栈的应用-逆波兰表达式求值

4.1 什么是逆波兰表达式

逆波兰表达式，也称后缀表达式，是一种特殊的算数表达式表示方式。在逆波兰表达式中，操作符位于操作数之后，这种表达方式的优点式不需要括号来表示操作的优先级，从而简化了表达式的解析和计算

4.2 逆波兰表达式的特点

1.操作符在操作数之后：例如，普通的表达式（中缀表达式）5 - 2 在逆波兰表达式中表示为 5 2 -

2.无需括号：由于操作符位置明确，不需要括号来表示优先级

3.易于计算：可以使用栈这种数据结构计算表达式的值

4.3 如何用栈解决逆波兰表达式求值

我们知道栈遵循后入先出（Last In First Out）的原则，逆波兰表达式中操作符位于操作数之后，我们可以根据这两个特点对元素进行出栈和入栈操作。

1.先初始化一个空栈

2.从左向右扫描表达式，如果遇到操作数就将其压入栈中，如果遇到操作符，就从栈中弹出两个元素，进行计算，并将计算的结果压入栈中

3.表达式扫描完成后，栈顶元素即为计算的结果

假设传递的参数是一个数组：tokens=["2","1","+","3","*"]

将其转为中缀表达式：(2+1)*3=9

代码编写：

public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack();for (int i = 0; i < tokens.length; i++) {String token = tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 = stack.pop();int num1 = stack.pop();switch (token) {case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;default:}}}return stack.pop();
}
public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}

数据结构-Stack和栈

1.栈 1.1什么是栈栈是一种特殊的线性表，只允许在固定的一段进行插入和删除操作，进行插入和删除操作的一段称为栈顶，另一端称为栈底。栈中的数据元素遵顼后进先出LIFO（Last In First Out）的原则，就像一…...

编程日记 2025/5/21 18:26:18

内容检索（2025.01.30）

随着创作数量的增加，博客文章所涉及的内容越来越庞杂，为了更为方便地阅读，后续更新发布的文章将陆续在此汇总并附上原文链接，感兴趣的小伙伴们可持续关注文章发布动态！ 博客域名：http://my-signal.blog.cs…...

编程日记 2025/5/21 17:44:42

牛客周赛 Round 77

题目目录 C-小红走网格解题思路参考代码 D-隐匿社交网络解题思路参考代码 F-计树解题思路参考代码 C-小红走网格解题思路根据裴蜀定理：设a，b是不全为0的整数，对任意整数x，y，满足gcd（a，b&…...

编程日记 2025/5/21 17:57:17

c++面试：类定义为什么可以放到头文件中

这个问题是刚了解预编译的时候产生的疑惑。声明是指向编译器告知某个变量、函数或类的存在及其类型，但并不分配实际的存储空间。声明的主要目的是让编译器知道如何解析程序中的符号引用。定义不仅告诉编译器实体的存在，还会为该实体分配存储空间&#…...

编程日记 2025/5/21 18:18:45

Oracle查看数据库表空间使用情况

Oracle RAC环境查看表空间使用情况查询字段释义： NEED_ADDFILE,--是否需增加表空间文件 TABLESPACE_NAME,--表空间名称 TABLESPACE_FILE_COUNT, --表空间当前数据文件数量 NOW_FILEENABLE_BLOCKS,--表空间文件当前数据块数 NOW_FILEENABLE_BYTES_GB,--表空间文件当…...

编程日记 2025/5/20 23:03:00

Spring Boot 热部署实现指南

在开发 Spring Bot 项目时，热部署功能能够显著提升开发效率，让开发者无需频繁重启服务器就能看到代码修改后的效果。下面为大家详细介绍一种实现 Spring Boot 热部署的方法，同时也欢迎大家补充其他实现形式。步骤一、开启 IDEA 自动编译功能…...

编程日记 2025/5/19 10:12:10

如何构建ObjC语言编译环境?构建无比简洁的clang编译ObjC环境？Windows搭建Swift语言编译环境？

如何构建ObjC语言编译环境? 除了在线ObjC编译器，本地环境Windows/Mac/Linux均可以搭建ObjC编译环境。 Mac自然不用多说，ObjC是亲儿子。(WSL Ubuntu 22.04) Ubuntu可以安装gobjc/gnustep和gnustep-devel构建编译环境。 sudo apt-get install gobjc gnus…...

编程日记 2025/5/20 9:18:44

C++——类和对象（下）

1.初始化列表之前我们实现构造函数时，初始化成员变量主要使用函数体内赋值，构造函数初始化还有一种方式，就是初始化列表，初始化列表的使用方式是以一个冒号开始，接着是一个以逗号分隔的数据成员列表，每个…...

编程日记 2025/5/21 13:59:32

R 字符串：深入理解与高效应用

R 字符串：深入理解与高效应用引言在R语言中，字符串是数据处理和编程中不可或缺的一部分。无论是数据清洗、数据转换还是数据分析，字符串的处理都是基础技能。本文将深入探讨R语言中的字符串概念，包括其基本操作、常见函数以及高效应用方法。字符串基本概念字符串定…...

编程日记 2025/5/17 4:02:08

C#面试常考随笔7:什么是匿名⽅法？还有Lambda表达式？

匿名方法本质上是一种没有显式名称的方法，它可以作为参数传递给需要委托类型的方法，常用于事件处理、回调函数等场景，能够让代码更加简洁和紧凑。使用场景事件处理：在处理事件时，不需要为每个事件处理程序单独定义…...

编程日记 2025/5/21 17:21:05

舵机型号与识别

舵机型号繁多，不同品牌和制造商有不同的命名规则。常见的舵机品牌包括 Futaba、Hitec、Tower Pro、Savox、JX Servo 等。以下是舵机型号的常见识别方法以及一些典型的型号示例： 一、舵机型号的识别方法型号命名规则： 舵机型号通常由字母和数…...

编程日记 2025/5/21 16:49:40

【memgpt】letta 课程6：多agent编排

Lab 6: Multi-Agent Orchestration 多代理协作 letta 是作为一个服务存在的，app通过restful api 通信多智能体之间如何协调与沟通？相互发送消息共享内存块，让代理同步到不同的服务的内存块...

编程日记 2025/5/21 16:53:19

《DeepSeek手机版：开启AI移动新时代》

DeepSeek 手机版爆火：现象与背景在当今数字化时代，AI 技术的发展日新月异，如同一股汹涌澎湃的浪潮，深刻地改变着我们的生活。而在这股浪潮中，DeepSeek 手机版宛如一颗璀璨的新星，迅速崛起，引发…...

编程日记 2025/5/21 4:01:05

列表（列表是什么）

你将学习列表是什么以及如何使用列表元素。列表让你能够在一个地方存储成组的信息，其中可以只包含几个元素，也可以包含数百万个元素。列表是新手可直接使用的最强大的Python功能之一，它融合了众多重要的编程概念。列表是什么列表由一系列…...

编程日记 2025/5/21 17:16:37

C语言-运算符

1. 按位与运算符（&） 按位与运算符对两个整数的每一位执行“与”操作。只有当两个相应位都为 1 时，结果才为 1 ；否则为 0。 // 示例 int a 5; // 二进制: 0101 int b 3; // 二进制: 0011 int result a & b; …...

编程日记 2025/5/20 17:29:55

yolov11、yolov8部署的7种方法（yolov11、yolov8部署rknn的7种方法），一天一种部署方法，7天入门部署

由于涉及量化、部署两个领域，本博文难免有不对之处，欢迎指正。本博客对 yolov11（yolov8）尝试了7种不同的部署方法，在最基础的模型上一步一步的去掉解码相关的操作（移到后处理种进行）&#xff0…...

编程日记 2025/5/21 17:25:34

事务03之MVCC机制

MVCC 多版本并发控制机制文章目录 MVCC 多版本并发控制机制一：并发事务的场景1：读读场景2：写写场景3：读写 or 写读场景二：MVCC机制综述1：MVCC日常生活的体现2：多版本并发控制三：M…...

编程日记 2025/5/21 10:16:23

Autosar-Os是怎么运行的？（时间保护）

写在前面： 入行一段时间了，基于个人理解整理一些东西，如有错误，欢迎各位大佬评论区指正！！！ 1.功能概述 AUTOSAR OS 的四大可定制类型凸显了时间保护（Timing Protection）…...

编程日记 2025/5/19 22:59:12

论文阅读(九)：通过概率图模型建立连锁不平衡模型和进行关联研究：最新进展访问之旅

1.论文链接：Modeling Linkage Disequilibrium and Performing Association Studies through Probabilistic Graphical Models: a Visiting Tour of Recent Advances 摘要： 本章对概率图模型（PGMs）的最新进展进行了深入的回顾&…...

编程日记 2025/5/21 18:20:27

python学opencv|读取图像（五十二）使用cv.matchTemplate()函数实现最佳图像匹配

【1】引言前序学习了图像的常规读取和基本按位操作技巧，相关文章包括且不限于： python学opencv|读取图像-CSDN博客 python学opencv|读取图像（四十九）原理探究：使用cv2.bitwise()系列函数实现图像按位运算-CSDN博客…...

编程日记 2025/5/21 3:07:48

视频脚本生成器（基于openai API和streamlit）

utils.py： # 所有和ai交互的代码放进utils.py里（utils 通常是 “utilities” 的缩写，意为 “实用工具” 或 “实用函数”）from langchain.prompts import ChatPromptTemplate from langchain_openai import ChatOpenAI from lan…...

编程日记 2025/5/21 10:49:05

《LLM大语言模型+RAG实战+Langchain+ChatGLM-4+Transformer》

文章目录 Langchain的定义Langchain的组成三个核心组件实现整个核心组成部分为什么要使用LangchainLangchain的底层原理Langchain实战操作LangSmithLangChain调用LLM安装openAI库-国内镜像源代码运行结果小结使用Langchain的提示模板部署Langchain程序安装langserve代码请求格…...

编程日记 2025/5/21 17:38:35

【MySQL — 数据库增删改查操作】深入解析MySQL的 Update 和 Delete 操作

1. 测试数据 mysql> select* from exam1; ----------------------------------------- | id | name | Chinese | Math | English | ----------------------------------------- | 1 | 唐三藏 | 67.0 | 98.0 | 56.0 | | 2 | 孙悟空 | 87.0 | 78.…...

编程日记 2025/5/16 2:43:06

AnyThingLLM本地私有知识库搭建

***************************************************** 环境准备操作系统：Windows11 内存：32GB RAM 存储：预留 300GB 可用空间显存: 16G 网络: 100M带宽前置准备: 已安装ollama环境 deepseek本地大模型 ***************************…...

编程日记 2025/5/21 18:03:56

数仓ETL测试

提取，转换和加载有助于组织使数据在不同的数据系统中可访问，有意义且可用。ETL工具是用于提取，转换和加载数据的软件。在当今数据驱动的世界中，无论大小如何，都会从各种组织，机器和小工具中生成大量数据。 …...

编程日记 2025/5/21 17:47:43

leetcode——将有序数组转化为二叉搜索树（java）

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。示例 1： 输入：nums [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答…...

编程日记 2025/5/21 1:27:04

蓝桥杯模拟算法：多项式输出

P1067 [NOIP2009 普及组] 多项式输出 - 洛谷 | 计算机科学教育新生态这道题是一道模拟题，我们需要分情况讨论，我们需要做一下分类讨论 #include <iostream> #include <cstdlib> using namespace std;int main() {int n;cin >> n;for…...

编程日记 2025/5/17 14:31:34

新鲜速递：DeepSeek-R1开源大模型本地部署实战—Ollama + MaxKB 搭建RAG检索增强生成应用

在AI技术快速发展的今天，开源大模型的本地化部署正在成为开发者们的热门实践方向。最火的莫过于吊打OpenAI过亿成本的纯国产DeepSeek开源大模型，就在刚刚，凭一己之力让英伟达大跌18%，纳斯达克大跌3.7%，足足是给中国AI产…...

编程日记 2025/5/18 21:50:14

【张雪峰高考志愿填报】合集

【张雪峰高考志愿填报】合集链接：https://pan.quark.cn/s/89a2d88fa807 高考结束，分数即将揭晓，志愿填报的关键时刻近在眼前！同学们，这可是人生的重要转折点，选对志愿，就像为未来铺就一条…...

编程日记 2025/5/20 0:47:24

【gRPC-gateway】option定义规则及HttpBody响应

HTTP Option 定义规则在 .proto 文件中，通过 google.api.http 注解定义 HTTP 路由规则，控制请求参数映射需要在.proto文件显式 import https://github.com/googleapis/googleapis/tree/master/google/api 一、HTTP Option 定义规则详解 1. 基础路由…...

编程日记 2025/5/19 10:33:42

rsync安装与使用-linux015

使用 rsync 可以非常高效地将文件或目录从一个服务器传输到另一个服务器。能力： 支持 64 位文件、64 位 inode、64 位时间戳、64 位长整型支持套接字对、符号链接、符号链接时间、硬链接、硬链接特殊文件、硬链接符号链接支持 IPv6、访问时间（atimes&…...

编程日记 2025/5/21 14:02:31

一种用于低成本水质监测的软传感器开源方法：以硝酸盐（NO3⁻）浓度为例

论文标题 A Soft Sensor Open-Source Methodology for Inexpensive Monitoring of Water Quality: A Case Study of NO3− Concentrations 作者信息 Antonio Jess Chaves, ITIS Software, University of Mlaga, 29071 Mlaga, Spain Cristian Martn, ITIS Software, Universi…...

编程日记 2025/5/19 12:30:45

剑指 Offer II 011. 0 和 1 个数相同的子数组

comments: true edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20011.%200%20%E5%92%8C%201%20%E4%B8%AA%E6%95%B0%E7%9B%B8%E5%90%8C%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/README.md 剑指 Offer II 011. 0 和 1 个数相同的子…...

编程日记 2025/5/18 18:10:54

1.栈