技术改变世界 阅读塑造人生! - shaogx.com

This string was altered by TechBlog\Plugins\Example.; This is an example to show the potential of an offcanvas layout pattern in Bootstrap. Try some responsive-range viewport sizes to see it in action.

java 栈和队列(LinkedList模拟实现)

栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是其运算规则较线性表有更多的限制,故又称它们为运算受限的线性表。       LinkedList数据结构是一种双向的链式结构,每一个对象除了数据本身外,还有两个引用,分别指向前一个元素和后一个元素,和数组的顺序存储结构(如:ArrayList)相比,插入和删除比较方便,但速度会慢一些。 栈的定义          栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。   (1)通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。   (2)当表中没有元素时称为空栈。   (3)栈为后进先出(Last   In   First   Out)的线性表,简称为LIFO表。          栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中 "最新 "的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。 可以通过LinkedList 的如下方法模拟实现Stack的功能:                                                                   LinkedList ls = new LinkedList();... 全文

java 队列 LinkedList

Java数据结构和算法(四)——栈

stack,中文翻译为堆栈,其实指的是栈,heap,堆。这里讲的是数据结构的栈,不是内存分配里面的堆和栈。栈是先进后出的数据的结构,好比你碟子一个一个堆起来,最后放的那个是堆在最上面的。队列就是排队买苹果,先去的那个可以先买。栈... 全文

Java数据结构和算法 数据结构 算法

栈和堆

         绝大数情况下(不知道还有哪些情况),java程序(方法、变量、对象)驻留在内存中的栈和堆上。 栈(堆栈):驻留于常规RAM(随机访问存储器)区域,但可通过它的“堆栈指针”获得处理的直接支持。堆栈指针若向下移,会创建新的内存;若向上移,则会释放那些内存。这是一种特别快、特别有效的数据保存方式,仅次于寄存器。        创建程序时,Java编译器必须准确地知道堆栈内保存的所有数据的“长度”以及“存在时间”。这是由于它必须生成相应的代码,以便向上和向下移动指针。这一限制无疑影响了程序的灵活性,所以尽管有些Java数据要保存在堆栈里——特别是对象句柄,但Java对象并不放到其中。堆:一种常规用途的内存池(也在RAM区域),其中保存了Java对象。和堆栈不同,“内存堆”或“堆”(Heap)最吸引人的地方在于编译器不必知道要从堆里分配多少存储空间,也不必知道存储的数据要在堆里停留多长的时间。因此,用堆保存数据时会得到更大的灵活性。要求创建一个对象时,只需用new命令编制相关的代码即可。执行这些代码时,会在堆里自动进行数据的保存。当然,为达到这种灵活性,必然会付出一定的代价:在堆里分配存储空间时会花掉更长的时间! 总结:1.对象在栈上2.局部变量在堆上 摘自 thinging in java... 全文

java 内存 休闲

深入Java核心:JVM中的栈和局部变量(1)

Java开发中,每当我们在程序中使用new生成一个对象,对象的引用存放在栈里,而对象是存放在堆里的。可以看出栈在Java核心的重要位置。今天我们就继续深入Java核心这个系列,为您介绍Java中的栈、局部变量及其之间的关系。... 全文

JVM 局部变量

深度解析Java内存的原型

本文主要通过分析Java内存分配的栈、堆以以及常量池详细的讲解了其的工作原理。一、Java虚拟机内存原型寄存器:我们在程序中无法控制栈:存放基本类型的数据和对象的引用,但对象本身不存放在栈中,而是存放在堆中堆:存放用new产生的数据静态域:存放在对象中用static定义的静态成员常量池:存放常量非RAM存储:硬盘等永久存储空间。二、常量池(constant pool)... 全文

Java

Java数据结构:栈的实现

栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法:pop() 出栈操作,弹出栈顶元素。push(E e) 入栈操作peek() 查看栈顶元素isEmpty() 栈是否为空另外,实现一个栈,还应该考虑到几个问题:栈的初始大小以及栈满以后如何新增栈空间对栈进行更新时需要进行同步简单示例,使用数组实现栈,代码如下:... 全文

Java 数据结构

Java虚拟机中的栈和堆

Java虚拟机中的栈和堆简单的说:Java把内存划分成两种:一种是栈内存,一种是堆内存。在函数中定义的一些基本类型的变量和对象的引用变量都在函数的栈内存中分配。当在一段代码块定义一个变量时,Java就在栈中为这个变量分配内存空间,当超过变量的作用域后,Java会自动释放掉为该变量所分配的内存空间,该内存空间可以立即被另作他用。堆内存用来存放由new创建的对象和数组。在堆中分配的内存,由Java虚拟机的自动垃圾回收器来管理。在堆中产生了一个数组或对象后,还可以在栈中定义一个特殊的变量,让栈中这个变量的取值等于数组或对象在堆内存中的首地址,栈中的这个变量就成了数组或对象的引用变量。引用变量就相当于是为数组或对象起的一个名称,以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象。具体的说:栈与堆都是Java用来在Ram中存放数据的地方。与C++不同,Java自动管理栈和堆,程序员不能直接地设置栈或堆。Java的堆是一个运行时数据区,类的对象从中分配空间。这些对象通过new、newarray、anewarray和multianewarray等指令建立,它们不需要程序代码来显式的释放。堆是由垃圾回收来负责的,堆的优势是可以动态地分配内存大小,生存期也不必事先告诉编译器,因为它是在运行时动态分配内存的,Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是,由于要在运行时动态分配内存,存取速度较慢。栈的优势是,存取速度比堆要快,仅次于寄存器,栈数据可以共享。但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性。栈中主要存放一些基本类型的变量(,int, short, long, byte, float, double, boolean, char)和对象句柄。栈有一个很重要的特殊性,就是存在栈中的数据可以共享。假设我们同时定义:int a = 3; int b = 3;编译器先处理int a = 3;首先它会在栈中创建一个变量为a的引用,然后查找栈中是否有3这个值,如果没找到,就将3存放进来,然后将a指向3。接着处理int b = 3;在创建完b的引用变量后,因为在栈中已经有3这个值,便将b直接指向3。这样,就出现了a与b同时均指向3的情况。这时,如果再令a=4;那么编译器会重新搜索栈中是否有4值,如果没有,则将4存放进来,并令a指向4;如果已经有了,则直接将a指向这个地址。因此a值的改变不会影响到b的值。要注意这种数据的共享与两个对象的引用同时指向一个对象的这种共享是不同的,因为这种情况a的修改并不会影响到b, 它是由编译器完成的,它有利于节省空间。而一个对象引用变量修改了这个对象的内部状态,会影响到另一个对象引用变量。String是一个特殊的包装类数据。可以用:String str = new String("abc"); String str = "abc"; 两种的形式来创建,第一种是用new()来新建对象的,它会在存放于堆中。每调用一次就会创建一个新的对象。而第二种是先在栈中创建一个对String类的对象引用变量str,然后查找栈中有没有存放"abc",如果没有,则将"abc"存放进栈,并令str指向”abc”,如果已经有”abc” 则直接令str指向“abc”。比较类里面的数值是否相等时,用equals()方法;当测试两个包装类的引用是否指向同一个对象时,用==,下面用例子说明上面的理论。String str1 = "abc"; String str2 = "abc"; System.out.println(str1==str2); //true 可以看出str1和str2是指向同一个对象的。String str1 =new String ("abc"); String str2 =new String ("abc"); System.out.println(str1==str2); // false 用new的方式是生成不同的对象。每一次生成一个。因此用第二种方式创建多个”abc”字符串,在内存中其实只存在一个对象而已. 这种写法有利与节省内存空间. 同时它可以在一定程度上提高程序的运行速度,因为JVM会自动根据栈中数据的实际情况来决定是否有必要创建新对象。而对于String str = new String("abc");的代码,则一概在堆中创建新对象,而不管其字符串值是否相等,是否有必要创建新对象,从而加重了程序的负担。另一方面, 要注意: 我们在使用诸如String str = "abc";的格式定义类时,总是想当然地认为,创建了String类的对象str。担心陷阱!对象可能并没有被创建!而可能只是指向一个先前已经创建的对象。只有通过new()方法才能保证每次都创建一个新的对象。由于String类的immutable性质,当String变量需要经常变换其值时,应该考虑使用StringBuffer类,以提高程序效率。java中内存分配策略及堆和栈的比较2.1 内存分配策略按照编译原理的观点,程序运行时的内存分配有三种策略,分别是静态的,栈式的,和堆式的. 静态存储分配是指在编译时就能确定每个数据目标在运行时刻的存储空间需求,因而在编译时就可以给他们分配固定的内存空间.这种分配策略要求程序代码中不允许有可变数据结构(比如可变数组)的存在,也不允许有嵌套或者递归的结构出现,因为它们都会导致编译程序无法计算准确的存储空间需求. 栈式存储分配也可称为动态存储分配,是由一个类似于堆栈的运行栈来实现的.和静态存储分配相反,在栈式存储方案中,程序对数据区的需求在编译时是完全未知的,只有到运行的时候才能够知道,但是规定在运行中进入一个程序模块时,必须知道该程序模块所需的数据区大小才能够为其分配内存.和我们在数据结构所熟知的栈一样,栈式存储分配按照先进后出的原则进行分配。静态存储分配要求在编译时能知道所有变量的存储要求,栈式存储分配要求在过程的入口处必须知道所有的存储要求,而堆式存储分配则专门负责在编译时或运行时模块入口处都无法确定存储要求的数据结构的内存分配,比如可变长度串和对象实例.堆由大片的可利用块或空闲块组成,堆中的内存可以按照任意顺序分配和释放. 2.2 堆和栈的比较上面的定义从编译原理的教材中总结而来,除静态存储分配之外,都显得很呆板和难以理解,下面撇开静态存储分配,集中比较堆和栈: 从堆和栈的功能和作用来通俗的比较,堆主要用来存放对象的,栈主要是用来执行程序的.而这种不同又主要是由于堆和栈的特点决定的: 在编程中,例如C/C++中,所有的方法调用都是通过栈来进行的,所有的局部变量,形式参数都是从栈中分配内存空间的。实际上也不是什么分配,只是从栈顶向上用就行,就好像工厂中的传送带(conveyor belt)一样,Stack Pointer会自动指引你到放东西的位置,你所要做的只是把东西放下来就行.退出函数的时候,修改栈指针就可以把栈中的内容销毁.这样的模式速度最快, 当然要用来运行程序了.需要注意的是,在分配的时候,比如为一个即将要调用的程序模块分配数据区时,应事先知道这个数据区的大小,也就说是虽然分配是在程序运行时进行的,但是分配的大小多少是确定的,不变的,而这个"大小多少"是在编译时确定的,不是在运行时. 堆是应用程序在运行的时候请求操作系统分配给自己内存,由于从操作系统管理的内存分配,所以在分配和销毁时都要占用时间,因此用堆的效率非常低.但是堆的优点在于,编译器不必知道要从堆里分配多少存储空间,也不必知道存储的数据要在堆里停留多长的时间,因此,用堆保存数据时会得到更大的灵活性。事实上,面向对象的多态性,堆内存分配是必不可少的,因为多态变量所需的存储空间只有在运行时创建了对象之后才能确定.在C++中,要求创建一个对象时,只需用 new命令编制相关的代码即可。执行这些代码时,会在堆里自动进行数据的保存.当然,为达到这种灵活性,必然会付出一定的代价:在堆里分配存储空间时会花掉更长的时间!这也正是导致我们刚才所说的效率低的原因,看来列宁同志说的好,人的优点往往也是人的缺点,人的缺点往往也是人的优点(晕~). 2.3 JVM中的堆和栈JVM是基于堆栈的虚拟机.JVM为每个新创建的线程都分配一个堆栈.也就是说,对于一个Java程序来说,它的运行就是通过对堆栈的操作来完成的。堆栈以帧为单位保存线程的状态。JVM对堆栈只进行两种操作:以帧为单位的压栈和出栈操作。我们知道,某个线程正在执行的方法称为此线程的当前方法.我们可能不知道,当前方法使用的帧称为当前帧。当线程激活一个Java方法,JVM就会在线程的 Java堆栈里新压入一个帧。这个帧自然成为了当前帧.在此方法执行期间,这个帧将用来保存参数,局部变量,中间计算过程和其他数据.这个帧在这里和编译原理中的活动纪录的概念是差不多的. 从Java的这种分配机制来看,堆栈又可以这样理解:堆栈(Stack)是操作系统在建立某个进程时或者线程(在支持多线程的操作系统中是线程)为这个线程建立的存储区域,该区域具有先进后出的特性。每一个Java应用都唯一对应一个JVM实例,每一个实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中,并由应用所有的线程共享.跟C/C++不同,Java中分配堆内存是自动初始化的。Java中所有对象的存储空间都是在堆中分配的,但是这个对象的引用却是在堆栈中分配,也就是说在建立一个对象时从两个地方都分配内存,在堆中分配的内存实际建立这个对象,而在堆栈中分配的内存只是一个指向这个堆对象的指针(引用)而已。本文出自 “魏杰的技术专栏” 博客,请务必保留此出处http://weijie.blog.51cto.com/340746/74930... 全文

java 休闲 职场

java多线程学习(三)——线程栈

一、线程栈模型线程栈模型是理解线程调度原理以及线程执行过程的基础。线程栈是指某时刻时内存中线程调度的栈信息,当前调用的方法总是位于栈顶,线程栈的内容是随着线程的运行状态变化而变化的,研究线程栈必须选择一个运行的时刻(指代码运行到什么地方)... 全文

线程 jvm java

Java栈与堆

 Java栈与堆 ----对这两个概念的不明好久,终于找到一篇好文,拿来共享1. 栈(stack)与堆(heap)都是Java用来在Ram中存放数据的地方。与C++不同,Java自动管理栈和堆,程序员不能直接地设置栈或堆。... 全文

java string integer immutable 编译器 primitive

Java:对象创建和初始化过程

分析一下Java中对象创建和初始化过程中涉及的相关概念问题,java中栈(stack)与堆(heap),对象、引用、句柄的概念。@Author:ZJ 06-11-25Blog: [url]http://zhangjunhd.blog.51cto.com/[/url]1.Java中的数据类型    Java中有3个数据类型:基本数据类型(在Java中,boolean、byte、short、int、long、char、float、double这八种是基本数据类型)、引用类型和null类型。其中,引用类型包括类类型(含数组)、接口类型。    下列语句声明了一些变量:int k ;A a; //a是A数据类型的对象变量名。B b1,b2,…,b10000;// 假定B是抽象类或接口。String s;      注意:从数据类型与变量的角度看,基本数据类型变量k、类类型变量a和s、抽象类或接口类型变量b(1万个),它们都是变量(标识符)。 2.关于句柄(handle)    为了区别引用类型的变量标识符和基本数据类型变量标识符,我们特别的使用Handle来称呼引用类型的变量标识符。上面例子中b1至b10000、a、s都是Handle。Handle直观的看就是手柄、把手,我们采用计算机界常用的中文翻译“句柄”。  2.1【Windows编程中的】句柄的含义    句柄是WONDOWS用来标识被应用程序所建立或使用的对象的唯一整数,WINDOWS使用各种各样的句柄标识诸如应用程序实例,窗口,控制,位图,GDI对象等等。WINDOWS句柄有点象C语言中的文件句柄。     从上面的定义中的我们可以看到,句柄是一个标识符,是拿来标识对象或者项目的,它就象我们的姓名一样,每个人都会有一个,不同的人的姓名不一样,但是,也可能有一个名字和你一样的人。从数据类型上来看它只是一个16位的无符号整数。应用程序几乎总是通过调用一个WINDOWS函数来获得一个句柄,之后其他的WINDOWS函数就可以使用该句柄,以引用相应的对象。    如果想更透彻一点地认识句柄,我可以告诉大家,句柄是一种指向指针的指针。我们知道,所谓指针是一种内存地址。应用程序启动后,组成这个程序的各对象是驻留在内存的。如果简单地理解,似乎我们只要获知这个内存的首地址,那么就可以随时用这个地址访问对象。但是,如果您真的这样认为,那么您就大错特错了。我们知道,Windows是一个以虚拟内存为基础的操作系统。在这种系统环境下,Windows内存管理器经常在内存中来回移动对象,依此来满足各种应用程序的内存需要。对象被移动意味着它的地址变化了。如果地址总是如此变化,我们该到哪里去找该对象呢?    为了解决这个问题,Windows操作系统为各应用程序腾出一些内存储地址,用来专门登记各应用对象在内存中的地址变化,而这个地址(存储单元的位置)本身是不变的。Windows内存管理器在移动对象在内存中的位置后,把对象新的地址告知这个句柄地址来保存。这样我们只需记住这个句柄地址就可以间接地知道对象具体在内存中的哪个位置。这个地址是在对象装载(Load)时由系统分配给的,当系统卸载时(Unload)又释放给系统。    句柄地址(稳定)→记载着对象在内存中的地址────→对象在内存中的地址(不稳定)→实际对象  2.2Java中句柄的意义    对句柄以前的【Windows编程中的】含义有了深刻的认识,我们可以说Handle是一个我们学习Java时非常需要的术语。它的意义在于区别“对象本身”和对象变量(或者严格点:对象所属的数据类型的变量标识符)。   2.3回到1中的变量声明:    现在,你应该对下面的注释一目了然。int k, j ;//k里面存放的是一个整型数。A a; //a里面存放地址。B b1,b2,…,b10000;// b1,…,b10000里面存放地址。String s; //s里面存放地址。 3.关于引用(reference)    什么是“引用”? “the identifier you manipulate is actually a ‘reference’ to an object”。(Thinking in Java 2e )    翻译是:你操纵的标识符实际上是一个对象的“引用”。或者精确些,翻译成:你操作的标识符实际上是指向一个对象的“引用”。显然,原文中reference是一个有方向感的东西。    回到Java中来,引用可以想象成对象的身份证号码、对象的ID或者对象的手机号码。当然,更多的说法是,引用是对象在内存中住的房间号码。直观的说,对象的引用是创建对象时的返回值!引用是new表达式的返回值。    new A(); 这里真正创建了一个对象,但我们没有用句柄去持有(hold、拿着、保存)该引用。从微观上看,new表达式完成了对象初始化的任务(三步曲,下文详细分析),整体上看则返回一个引用。    再次回到1中的变量声明,再看看下面的注释。A a; //声明句柄a,但未初始化,所以里面的值为null。B b1,b2,…,b10000;// 声明句柄b1,…,b10000,但未初始化,所以里面的值为null。String s; //声明句柄s,但未初始化,所以里面的值为null。 4.句柄与引用的关系A a;//声明句柄a,值为nulla=new A();//句柄的初始化(句柄 = 引用;即把引用赋值给句柄)     引用:new A()的值。引用可以简单的看作对象占据内存空间的地址;通过对象的引用,就可以方便的与其他对象区别开来,引用就是对象独特的身份标识。完成句柄的初始化后,就可以用句柄遥控对象了。    当然,这只是从一方面解释对象的创建和初始化,理解了句柄和引用的关系后,下面分析对象初始化的整个过程。先做以下准备工作,说说栈与堆。 5.java中栈(stack)与堆(heap)    在java中内存分为“栈”和“堆”这两种(Stack and Heap).基本数据类型存储在“栈”中,对象引用类型实际存储在“堆”中,在栈中只是保留了引用内存的地址值。    顺便说说“==”与“equals()方法”,以帮助理解两者(Stack and Heap)的概念。    在Java中利用"=="比较变量时候,系统使用变量在stack(栈)中所存的值来作为对比的依据,基本数据类型在stack中所存的值就是其內容值,而引用类型在stack中所存放的值是本身所指向Heap中对象的地址值。 Java.lang包中的Object类有public boolean equals (Object obj)方法。它比较两个对象是否相等。仅当被比较的两个引用指向同一对象时(句柄相等),对象的equals()方法返回true。(至于String类的equals()方法,它重写(override)equals()方法,不在本文讨论之列。) 6.对象的创建和初始化过程    在java中对象就是类的实例。在一般情况下,当把一个类实例化时,此类的所有成员,包括变量和方法,都被复制到属于此数据类型的一个新的实例中去。分析以下两段代码。  6.1  Vehicle veh1 = new Vehicle();    上面的语句做了如下的事情:①右边的“new Vehicle”,是以Vehicle类为模板,在堆空间里创建一个Vehicle类对象(也简称为Vehicle对象)。②末尾的()意味着,在对象创建后,立即调用Vehicle类的构造函数,对刚生成的对象进行初始化。构造函数是肯定有的。如果没创建,Java会补上一个默认的构造函数。③左边的“Vehicle veh1”创建了一个Vehicle类引用变量。④“=”操作符使对象引用指向刚创建的那个Vehicle对象。(回想一下句柄与引用)     将上面的语句分为两个步骤:Vehicle veh1;veh1 = new Vehicle();    这样写,就比较清楚了,有两个实体:一是对象引用变量,一是对象本身。在堆空间里创建的实体,与在栈空间里创建的实体不同。尽管它们也是确确实实存在的实体,但是似乎很难准确的“抓”住它。我们仔细研究一下第二句,找找刚创建的对象叫什么名字?有人说,它叫“Vehicle”。不对,“Vehicle”是类(对象的创建模板)的名字。一个Vehicle类可以据此创建出无数个对象,这些对象不可能全叫“Vehicle”。对象连名都没有,没法直接访问它。我们只能通过对象引用来间接访问对象。  6.2  Vehicle veh2;veh2 = veh1;    由于veh1和veh2只是对对象的引用,第二行所做的不过是把veh1的引用(地址)赋值给veh2,使得veh1和veh2同时指向唯一的一个Vehicle对象。  6.3  veh2 = new Vehicle();    则引用变量veh2改指向第二个对象。    从以上叙述再推演下去,我们可以获得以下结论:①一个对象引用可以指向0个或1个对象;②一个对象可以有N个引用指向它。 7.参考资料⑴阎宏,Java与模式,电子工业出版社,2006⑵yqj2065,句柄、引用与对象,[url]http://blog.csdn.net/yqj2065[/url]⑶Java对象及其引用,[url]http://java.chinaitlab.com/base[/url]本文出自 “子 孑” 博客,请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/17124... 全文

引用 栈/堆 java 句柄

Java数据结构和算法(五)——队列

队列,queqe,就是现实生活中的排队。1、简单队列:... 全文

Java数据结构和算法 后缀表达式 队列

前缀、中缀、后缀表达式

  前缀、中缀、后缀表达式关键字:概念, 前缀表达式, 前缀记法, 中缀表达式, 中缀记法, 波兰式, 后缀表达式, 后缀记法, 逆波兰式它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。 举例:(3 + 4) × 5 - 6 就是中缀表达式- × + 3 4 5 6 前缀表达式3 4 + 5 × 6 - 后缀表达式中缀表达式(中缀记法)中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。 虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。前缀表达式(前缀记法、波兰式) 前缀表达式的运算符位于操作数之前。前缀表达式的计算机求值: 从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。 例如前缀表达式“- × + 3 4 5 6”: (1) 从右至左扫描,将6、5、4、3压入堆栈; (2) 遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素,注意与后缀表达式做比较),计算出3+4的值,得7,再将7入栈; (3) 接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈; (4) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。 可以看出,用计算机计算前缀表达式的值是很容易的。将中缀表达式转换为前缀表达式: 遵循以下步骤: (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2; (2) 从右至左扫描中缀表达式; (3) 遇到操作数时,将其压入S2; (4) 遇到运算符时,比较其与S1栈顶运算符的优先级: (4-1) 如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈; (4-2) 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1; (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较; (5) 遇到括号时: (5-1) 如果是右括号“)”,则直接压入S1; (5-2) 如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃; (6) 重复步骤(2)至(5),直到表达式的最左边; (7) 将S1中剩余的运算符依次弹出并压入S2; (8) 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。例如,将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程如下:扫描到的元素S2(栈底->栈顶)S1 (栈底->栈顶)说明55空数字,直接入栈-5-S1为空,运算符直接入栈)5- )右括号直接入栈45 4- )数字直接入栈×5 4- ) ×S1栈顶是右括号,直接入栈)5 4- ) × )右括号直接入栈35 4 3- ) × )数字+5 4 3- ) × ) +S1栈顶是右括号,直接入栈25 4 3 2- ) × ) +数字(5 4 3 2 +- ) ×左括号,弹出运算符直至遇到右括号(5 4 3 2 + ×-同上+5 4 3 2 + ×- +优先级与-相同,入栈15 4 3 2 + × 1- +数字到达最左端5 4 3 2 + × 1 + -空S1中剩余的运算符因此结果为“- + 1 × + 2 3 4 5”。后缀表达式(后缀记法、逆波兰式) 后缀表达式与前缀表达式类似,只是运算符位于操作数之后。后缀表达式的计算机求值: 与前缀表达式类似,只是顺序是从左至右: 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。 例如后缀表达式“3 4 + 5 × 6 -”: (1) 从左至右扫描,将3和4压入堆栈; (2) 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈; (3) 将5入栈; (4) 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈; (5) 将6入栈; (6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。将中缀表达式转换为后缀表达式: 与转换为前缀表达式相似,遵循以下步骤: (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2; (2) 从左至右扫描中缀表达式; (3) 遇到操作数时,将其压入S2; (4) 遇到运算符时,比较其与S1栈顶运算符的优先级: (4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈; (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况); (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较; (5) 遇到括号时: (5-1) 如果是左括号“(”,则直接压入S1; (5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃; (6) 重复步骤(2)至(5),直到表达式的最右边; (7) 将S1中剩余的运算符依次弹出并压入S2; (8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。例如,将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下:扫描到的元素S2(栈底->栈顶)S1 (栈底->栈顶)说明11空数字,直接入栈+1+S1为空,运算符直接入栈(1+ (左括号,直接入栈(1+ ( (同上21 2+ ( (数字+1 2+ ( ( +S1栈顶为左括号,运算符直接入栈31 2 3+ ( ( +数字)1 2 3 ++ (右括号,弹出运算符直至遇到左括号×1 2 3 ++ ( ×S1栈顶为左括号,运算符直接入栈41 2 3 + 4+ ( ×数字)1 2 3 + 4 ×+右括号,弹出运算符直至遇到左括号-1 2 3 + 4 × +--与+优先级相同,因此弹出+,再压入-51 2 3 + 4 × + 5-数字到达最右端1 2 3 + 4 × + 5 -空S1中剩余的运算符因此结果为“1 2 3 + 4 × + 5 -”(注意需要逆序输出)。编写Java程序将一个中缀表达式转换为前缀表达式和后缀表达式,并计算表达式的值。其中的toPolishNotation()方法将中缀表达式转换为前缀表达式(波兰式)、toReversePolishNotation()方法则用于将中缀表达式转换为后缀表达式(逆波兰式):... 全文

java 前中后缀表达式

浅析java(多方面解读)

昨天我简单的说了一下我的编程学习之路,如果你热爱编程,而不是仅为了赚钱,我想我的经历也许会给你带来一定的启发,如果你还没有看,请先慢慢读完我的编程学习之路,您肯定会有另一番体会的。。好了,废话不多说了,进入今天的主题,我想先介绍一下java,重栈和堆的角度还有jvm,如果你不是很明白,那不要紧,在以后的文章中我还会提到,如何你学过c和c++,那么你肯定对栈,堆内存理解的比较好。我以前写过一篇文章 Java是一种什么语言,简单的介绍了一下java,今天这一块我就不多说了。。... 全文

程序员 内存 编程 存储

Java中String、StringBuffer和StringBuilder的区别和堆栈内存分配

Java中的String类是一个很常用,但最不注意其细节的类,因此大多数面试会那这个类做文章。比如String str = new String("hello");开辟了几个内存空间,String和StringBuffer的区别等等。下面就做一个我的理解:String是一个被final修饰的类,它是不能被继承的。StringBuffer也是被final修饰的类。一、JVM内存划分     在java中主要存在4块内存,这些内存空间分别为:栈内存空间、堆内存空间、全局数据区、全局代码区    1、栈内存空间:保存所有的对象名称(保所了所引用的堆内存空间的地址)    2、堆内存空间:保存每一个对象的具体内容... 全文

String StringBuffer StringBuilder 堆内存 栈内存

nyoj305表达式求值(第四届河南省程序设计大赛)

表达式求值时间限制:3000 ms  |  内存限制:65535 KB难度:3 描述 Dr.Kong设计的机器人卡多掌握了加减法运算以后,最近又学会了一些简单的函数求值,比如,它知道函数min(20,23)的值是20 ,add(10,98) 的值是108等等。经过训练,Dr.Kong设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式。假设表达式可以简单定义为:1. 一个正的十进制数 x 是一个表达式。2. 如果 x 和 y 是 表达式,则 函数min(x,y )也是表达式,其值为x,y 中的最小数。... 全文

acm Java 表达式求值 sscanf

1