首页 > 其他分享 >20230307 2.2. 堆栈

20230307 2.2. 堆栈

时间:2023-06-21 16:36:53浏览次数:48  
标签:Deque 运算 20230307 栈顶 堆栈 2.2 Stack 表达式

引题

计算机如何进行表达式求值?

中缀表达式:运算符号位于两个运算数之间。如 ,a+b*c-d/e

后缀表达式:运算符号位于两个运算数之后。如, abc*+de/-

堆栈的抽象数据类型描述

堆栈(Stack):具有一定操作约束的线性表(只在一端(栈顶,Top)做 插入、删除)

  • 插入数据:入栈(Push)

  • 删除数据:出栈(Pop)

  • 后入先出:Last In First Out(LIFO)

类型名称: 堆栈(Stack)

数据对象集:一个有0个或多个元素的有穷线性表。

操作集:长度为MaxSize的堆栈S ∈ Stack,堆栈元素item ∈ ElementType

  • Stack CreateStack( int MaxSize ): 生成空堆栈,其最大长度为MaxSize;

  • int IsFull( Stack S, int MaxSize ):判断堆栈S是否已满;

  • void Push( Stack S, ElementType item ):将元素item压入堆栈;

  • int IsEmpty ( Stack S ):判断堆栈S是否为空;

  • ElementType Pop( Stack S ):删除并返回栈顶元素;

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行。

堆栈应用

  • 表达式求值
    基本策略:将中缀表达式转换为后缀表达式,然后求值
    2+9/3-5 → 2 9 3 / + 5 -
  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法

Java 关联

  • java.util.Stack :继承 Vector ,线程同步

  • Java 更推荐使用 java.util.Deque 接口实现栈功能

  • ArrayDequeDeque 的数组实现

  • LinkedList 同时实现了 ListDeque 接口,是 Deque的链表实现

  • Deque 之所以可以实现栈功能,实际上就是操作队列的头部,push 就是 addFirstpop 就是 removeFirst

ArrayDeque

  • 实现上用了大量的位运算
  • 和ArrayList一样有设置初始容量的构造方法,但是意思不同,这里是设置能够容纳入参大小的初始容量,实际是不小于入参大小的最接近的2的n次幂,这样做是为了进行位运算

java.util.Stack 方法

只列出部分

  • empty
    • 判断是否为空
  • peek
    • 查看此堆栈顶部的对象,不将其从堆栈中移除
  • pop
    • 移出并返回栈顶对象
  • push
    • 将一个对象压入这个堆栈的顶部
  • search
    • 返回最靠近栈顶的equals判断为true的元素

标签:Deque,运算,20230307,栈顶,堆栈,2.2,Stack,表达式
From: https://www.cnblogs.com/huangwenjie/p/17490485.html

相关文章

  • 最完美WIN11_Pro_22H2.22631.1900软件选装纯净版VIP50.3
    【系统简介】=============================================================1.本次更新母盘来自UUP_WIN11_PRO_22H2.22631.1900。进一步精简优化调整。2.只为呈现最好的作品,手工精简优化部分较多。3.OS版本号为22631.1900。个别要求高的就下MSDN吧,里面啥功能都有。4.集成《DrvCeo......
  • PromSQL v2.29
    启动参数负偏移量:启动时增加--enable-feature=promql-negative-offset时间修饰符:@启动时增加--enable-feature=promql-at-modifier数据类型分类即时向量:Instant-vector范围向量:Range-vector标量:Scalar字符串(未启用)查询指标名//结果为即时向量,所有该指标的结果,......
  • MySQL8(glibc2.28)二进制安装
    操作系统:centos7.9安装数据库:mysql-8.0.33-linux-glibc2.28一、升级gcc(传送阵:升级gcc)1、添加mysql8依赖库软连接mv/lib64/libstdc++.so.6/lib64/libstdc++.so.6_oldln-s/usr/local/gcc/lib64/libstdc++.so.6/lib64/libstdc++.so.62、查看GLIBC_2.28是否更新成功stri......
  • Day02 2.2 ADB配置和使用
    ADB配置和使用【一】什么是ADB「adb」即AndroidDebugBridge,亦称安卓调试桥是谷歌为安卓开发者提供的开发工具之一,可以让你的电脑以指令窗口的方式控制手机。可以在安卓开发者网页中的SDK平台工具页面下直接下载对应系统的adb配置文件,大小只有几十MB1下载地址(......
  • jpa2.2.10 JpaSpecificationExecutor Specification 查询时,实体类中存在@OneToMany,怎
    对于这个问题,您可以在查询时通过join()方法指定不查询@OneToMany关联表。举个例子,如果有一个实体A与实体B是一对多关系,那么您可以这样写查询条件:@OneToMany(targetEntity=DcyRightImage.class,cascade={CascadeType.ALL},fetch=FetchType.EAGER)@JoinColumn(nam......
  • nacos2.0升级至2.2.3
    背景安全漏洞修复升级注意事项近期Nacos社区收到关于Nacos鉴权功能通过token.secret.key默认值进行撞击,绕过身份验证安全漏洞的问题。社区在2.2.0.1和1.4.5版本已移除了自带的默认值,并在token.secret.key未传入或非法时阻止Nacos节点启动来提醒用户设置自定义token.secret......
  • 最完美WIN11_Pro_22H2.22631.1835软件选装纯净版VIP50.1
    【系统简介】=============================================================1.本次更新母盘来自UUP_WIN11_PRO_22H2.22631.1835。进一步精简优化调整。2.只为呈现最好的作品,手工精简优化部分较多。3.OS版本号为22631.1835。个别要求高的就下MSDN吧,里面啥功能都有。4.集成《DrvCeo......
  • 面试算法:计算堆栈当前元素的最大值
    更详细的讲解和代码调试演示过程,请参看视频如何进入google,算法面试技能全面提升指南有一道堆栈相关算法题,我被面试过两次以上,看似其在算法面试中出现的概率很高,由此值得我们好好分析下。题目是这样的:对于堆栈的常用操作有,pop弹出堆栈顶部的元素;push向堆栈压入一个元素;peek获......
  • 函数调用堆栈
    这段代码反汇编后,代码是什么呢?#include<stdio.h>longtest(inta,intb){a=a+3;b=b+5;returna+b;}intmain(intargc,char*argv[]){printf("%d",test(10,90));return0;}......
  • 调试技巧之调用堆栈
    在计算机科学中,Callstack是指存放某个程序的正在运行的函数的信息的栈。Callstack由stackframes组成,每个stackframe对应于一个未完成运行的函数。在当今流行的计算机体系架构中,大部分计算机的参数传递,局部变量的分配和释放都是通过操纵程序栈来实现的。栈用来传递函数参数,存......