java共享栈实现代码 共享栈的实现

Java中实现栈时的问题----------Java高手请进

p2=p1不是Point对象赋值，而是引用赋值。这和C++不一样。

在java里边，p1、p2、point和temp都是引用，而不是对象本身，引用就象C++的指针。上面的程序中，p2=p1的结果是，p2指向的对象和p1相同，他们都指向了p1=new Point()语句创建的对象。而Point p2=new Point(); 创建的对象，因为p2不再引用它而变成垃圾，java会自动删除。

java的引用赋值就象C++的指针赋值，就类似C++程序：

Point * p1=new Point();

Point * p2=new Point();

p2=p1;

所以你上面的程序也有这个问题，temp=point;其实没什么用，效果把Point temp=new mypoint(); 创建的对象删除了，被压栈的对象还是point，所以去掉这两句，效果完全一样。

如果你想复制一个新对象压栈，应该用java的clone方法，

temp=point.clone();

不过Point必须实现Clonable接口，并且正确实现它。

相关问答

Q1: 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会自动指引java共享栈实现代码你到放东西的位置,java共享栈实现代码你所要做的只是把东西放下来就行.退出函数的时候，修改栈指针就可以把栈中的内容销毁.这样的模式速度最快, 当然要用来运行程序了.需要注意的是,在分配的时候,比如为一个即将要调用的程序模块分配数据区时,应事先知道这个数据区的大小,也就说是虽然分配是在程序运行时进行的,但是分配的大小多少是确定的,不变的,而这个"大小多少"是在编译时确定的,不是在运行时.

堆是应用程序在运行的时候请求操作系统分配给自己内存，由于从操作系统管理的内存分配,所以在分配和销毁时都要占用时间，因此用堆的效率非常低.但是堆的优点在于,编译器不必知道要从堆里分配多少存储空间，也不必知道存储的数据要在堆里停留多长的时间,因此,用堆保存数据时会得到更大的灵活性。事实上,面向对象的多态性,堆内存分配是必不可少的,因为多态变量所需的存储空间只有在运行时创建了对象之后才能确定.在C++中，要求创建一个对象时，只需用 new命令编制相关的代码即可。执行这些代码时，会在堆里自动进行数据的保存.当然，为达到这种灵活性，必然会付出一定的代价:在堆里分配存储空间时会花掉更长的时间！这也正是导致我们刚才所说的效率低的原因,看来列宁同志说的好,人的优点往往也是人的缺点,人的缺点往往也是人的优点(晕~).

2.3 JVM中的堆和栈

JVM是基于堆栈的虚拟机.JVM为每个新创建的线程都分配一个堆栈.也就是说,对于一个Java程序来说，它的运行就是通过对堆栈的操作来完成的。堆栈以帧为单位保存线程的状态。JVM对堆栈只进行两种操作:以帧为单位的压栈和出栈操作。

我们知道,某个线程正在执行的方法称为此线程的当前方法.我们可能不知道,当前方法使用的帧称为当前帧。当线程激活一个Java方法,JVM就会在线程的 Java堆栈里新压入一个帧。这个帧自然成为了当前帧.在此方法执行期间,这个帧将用来保存参数,局部变量,中间计算过程和其他数据.这个帧在这里和编译原理中的活动纪录的概念是差不多的.

从Java的这种分配机制来看,堆栈又可以这样理解:堆栈(Stack)是操作系统在建立某个进程时或者线程(在支持多线程的操作系统中是线程)为这个线程建立的存储区域，该区域具有先进后出的特性。

每一个Java应用都唯一对应一个JVM实例，每一个实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中,并由应用所有的线程共享.跟C/C++不同，Java中分配堆内存是自动初始化的。Java中所有对象的存储空间都是在堆中分配的，但是这个对象的引用却是在堆栈中分配,也就是说在建立一个对象时从两个地方都分配内存，在堆中分配的内存实际建立这个对象，而在堆栈中分配的内存只是一个指向这个堆对象的指针(引用)而已。

Q2: 用java实现数据结构“栈

Java栈的实现

public class MyStack { //定义一个堆栈类

int[] array; //用int数组来保存数据，根据需要可以换类型

int s_size; //定义堆栈的宽度

public MyStack(int i){ //定义一个带参数构造器

array=new int[i]; //动态定义数组的长度

s_size=0; //堆栈的默认宽度为0

}

public MyStack(){ //默认构造器

this(50); //默认构造器可容纳50个元素

}

public void push(int i){ //压栈

array[this.s_size]=i;

this.s_size++;

}

public int pop(){ //从堆栈中取元素，从栈顶开始取

if(this.s_size!=0){

int t=array[s_size-1]; //用中间变量保存栈顶的元素

array[s_size-1]=0; //取完元素该位置设为0

s_size--; //栈的大小减1

return t; //返回栈顶元素

}else{

System.out.println("This stack is empty"); //当栈为空时显示提示信息，返回0

return 0;

}

}

public boolean isEmpty(){ //判断栈是否为空

return this.s_size==0;

}

public int top(){ //从栈顶取值，功能和 pop() 方法一样

if(!this.isEmpty()){

int t=array[this.s_size-1];

array[this.s_size-1]=0;

this.s_size--;

return t;

}else{

System.out.println("This stack is empty!");

return 0;

}

}

public void printAll(){ //打印出堆栈中的所有元素的值，不是取出，元素依然在堆栈里

if(!this.isEmpty()){

for(int i=this.s_size - 1;i=0;i--){

System.out.println(array[i]);

}

}

}

//下面是测试代码

public static void main(String[] args){

MyStack stack=new MyStack();

stack.push(4);

stack.push(5);

stack.push(6);

stack.push(7);

//System.out.println(stack.isEmpty());

stack.printAll();

System.out.println("===========");

System.out.println(stack.top());

System.out.println(stack.top());

System.out.println(stack.top());

System.out.println(stack.top());

System.out.println(stack.top());

}

}

Q3: 对Java中堆和栈的概念不太理解。请大神帮我解释下面代码的情况。请详细说明！谢谢

Java中String是一个特殊的包装类数据有两种创建形式：

String s = "abc";

String s = new String("abc");

第一种先在栈中创建一个对String类的对象引用变量s，然后去查找"abc"是否被保存在字符串常量池中，如果没有则在栈中创建三个char型的值'a'、'b'、'c'，然后在堆中创建一个String对象object，它的值是刚才在栈中创建的三个char型值组成的数组{'a'、'b'、'c'}，接着这个String对象object被存放进字符串常量池，最后将s指向这个对象的地址，如果"abc"已经被保存在字符串常量池中，则在字符串常量池中找到值为"abc"的对象object，然后将s指向这个对象的地址。

第一种特点：JVM会自动根据栈中数据的实际情况来决定是否有必要创建新对象。

第二种可以分解成两步1、String object = "abc"; 2、String s = new String(object); 第一步参考第一种创建方式，而第二步由于"abc"已经被创建并保存到字符串常量池中，因此jvm只会在堆中新创建一个String对象，它的值共享栈中已有的三个char型值。

第二种特点：一概在堆中创建新对象，而不管其字符串值是否相等，是否有必要创建新对象。

Q4: 单共享栈

栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性数据结构。应用广，作用大。

一、1、 栈的定义：限定仅在表尾进行插入或删除操作的线性表，因此，对栈来说，表尾端有其特殊含义，表尾—栈顶(top) ，表头—栈底(bottom) ，不含元素的空表称空栈。

例4：计算机系2001年考研题（程序设计基础）

设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：

A）a，b，c，d B）c，d，a，b

C）b，c，d，a D）a，c，d，b

A、D可以（ B、C不行）。

答：

例5、习题集P22 3.4

status algo1(stack s)

{int i,n,a[255];

n=0;

While(!stackempty(s))

{n++;

pop (s,a[n]);}

For(i=1;i=n;i++) push (s,a[i]);

}

5、补充公式：

若输入的序列为1、2、3 ….n，则可能出现的输出序列符合卡塔南数列：

验证：

二、 栈的表示和实现：

顺序存贮结构__顺序栈；

链式存贮结构__链栈；

（一） 顺序栈

利用一组地址连续的存贮单元依次自栈底到栈顶存放栈的数据元素.

栈底元素是最先进入的，实际上是线性表的第一个元素

数组（静态数组）：空间固定

动态数组：动态申请空间（用指针表示）

表示容量；

表示数据元素个数；

// 顺序栈的C表示

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置；base表示栈底指针；

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct

{ SElemType *Base; // 栈底指针

SElemType *Top; // 栈顶指针

int StackSize;//当前已分配的存储空间，以元素为 单位。

}SqStack

空栈

A

A进栈

top

base

top

base

s.top=0 或s.top=s.base 表示空栈；

s.base=NULL表示栈不存在；

当插入新的栈顶元素时，指针s.top++；

删除栈顶元素时，指针s.top--；

当s.top-s.base=stacksize时，栈满，溢出

顺序栈初始化

SqStack s;

s.Base = NULL;

s.Top = NULL;

s.StackSize = 0;

base

stacksize

top

s

s.base = s.top =

( SElemType *)malloc( STACK_INIT_SIZE * sizeof( SElemType ));

顺序栈的C图示

base

top

空栈：

base = top;

A

base

top

*top = A;

top ++;

E

C

B

A

D

base

top

B

A

base

top

出栈：

if( top != base )

{

top --;

e = *top;

}

入栈：

if( 没有空间 )

{

//realloc，调整top

}

顺序栈基本算法_InitStack

// 初始化顺序栈, 构造一个空栈

Status InitStack( SqStack S )

{

s.base = (SElemType *)malloc(

STACK_INIT_SIZE * sizeof( SElemType));

if( !s.base )

{

return OVERFLOW;

}

s.top = s.base;

s.stacksize = STACK_INIT_SIZE;

return OK;

}// InitStack

顺序栈基本算法：GetTop

// 用e返回栈S的栈顶元素，若栈空，函数返回ERROR

Status GetTop( SqStack S, SElemType e)

{

if( s.top != s.base ) // 栈空吗？

{

e = *( s.top – 1 );

return OK;

}

else

{

return ERROR;

}

}// GetTop

顺序栈基本算法：Push

//把元素e入栈

Status Push(SqStack S, SElemType e )

{

// 若栈，追加存贮空间

if( s.top == s.base + s.stacksize )

{

p = (SElemType *)realloc( s.base,

(s.stacksize + STACKINCREMENT)*sizeof(SElemType));

if( !p )

{

return OVERFLOW;

}

s.base = p;

顺序栈基本算法：Push

s.top = s.base + s.stacksize;

s.stacksize += STACKINCREMENT;

}

*s.top = e;

s.top++;

return OK;

}// Push

顺序栈基本算法：Pop

// 出栈

Status Pop( SqStack S, SElemType e )

{

if( s.top == s.base ) // 空吗？

{

return ERROR;

}

s.top --;

e = *s.top;

return OK;

}// Pop

顺序栈基本算法：其他

// 取顺序栈长度

int StackLength( SqStack S )

{

return s.top – s.base;

}// StackLength

#define StackLength( S ) ((S).top – (S).base)

// 顺序栈空吗？

Status StackEmpty( SqStack S )

{

return s.top == s.base ? TRUE:FALSE;

}

#define StackEmpty( S ) (((S).top == (S).base )?TRUE:FALSE)

顺序栈基本算法：ClearStack

// 清空栈

Status ClearStack( SqStack S )

{

if( s.base )

{

s.top = s.base;

}

return OK;

}// ClearStack

顺序栈基本算法：DestroyStack

// 销毁栈

Status DestroyStack( SqStack S )

{

if( s.base )

{

free( s.base );

s.stacksize = 0;

s.base = s.top = NULL;

}

}// DestroyStack

3.1.3 链栈

栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。

链栈的类型说明如下：

栈的链接存储结构

链栈的结点定义

typedef struct node

{ ElemType data;

struct node *next;

} LinkStack;

栈的链接表示 — 链式栈

链式栈无栈满问题，空间可扩充

插入与删除仅在栈顶处执行

链式栈的栈顶在链头

适合于多栈操作

链栈的进栈算法

LinkStack *PUSH (LinkStack *top, ElemType x)

{ LinkStack *p;

p＝malloc(sizeof(LinkStack));

p-data＝x; p-next＝top;top=p;

return top;

}

链栈的出栈算法

linkstack *POP (linkstack *top, ElemType *datap)

{ linkstack *p;

if (top==NULL)

{printf(“under flow\n”); return NULL;}

else

{ *datap＝top-data;

p＝top;

top＝top-next;

free(p);

return top;

}

}

栈的共享存储单元

有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。

栈的应用---基本应用

void read_write()

{ stack S;

int n,x;

cout”Please input num int n”;

cinn; //输入元素个数

init_stack(S); //初始化栈

for (i=1; i=n; i++)

{ cinx; //读入一个数

push_stack(S,x); //入栈

}

while (stack_empty(S)!=TRUE)

{stack_top(S,x); //取出栈顶元素

coutx; //输出

pop_stack(S); //退栈

}

}

读入一个有限大小的整数n，并读入n个整数，然后按输入次序的相反次序输出各元素的值。

3.2 栈的应用举例

一、 数制转换

二、 括号匹配的检验

三、 行编辑程序问题

四、 表达式求值

五、 迷宫求解

六、 实现递归

一、数制转换

十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:

N=(n div d)*d+n mod d

( 其中:div为整除运算,mod为求余运算)

例如 (1348)10=(2504)8，

其运算过程如下：

n n div 8 n mod 8

1348 168 4

168 21 0

21 2 5

2 0 2

计算顺序

输出顺序

算法分析：

由十进制转换为其他进制的数的规则，可知，求得的余数的顺序为由低位到高位，而输出则是由高位到低位。

因此，这正好利用栈的特点，先将求得的余数依次入栈，输出时，再将栈中的数据出栈。

void conversion () {

InitStack(S); // 构造空栈

scanf ("%d",N); //输入一个十进制数

while (N) {

Push(S, N % 8); // "余数"入栈

N = N/8; // 非零"商"继续运算

}

while (!StackEmpty(S)) {

Pop(S,e);

//和"求余"所得相逆的顺序输出八进制的各位数

printf ( "%d", e );

}

} // conversion

二、 括号匹配的检验

假设在表达式中

(〔〕（））或〔（〔 〕〔 〕）〕

等为正确的格式，

（〔]（ ） 或（（）））或 〔（ 〕）均为不正确的格式。

则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。

算法的设计思想：

读入表达式

1）凡出现左括弧，则进栈；

2）凡出现右括弧，首先检查栈是否空

若栈空，则表明该“右括弧”多余，

否则和栈顶元素比较，

若相匹配，则“左括弧出栈” ，

否则表明不匹配。

3）表达式检验结束时，

若栈空，则表明表达式中匹配正确，

否则表明“左括弧”有余。

Status matching(char exp[ ] ) {

while (i=Length(exp)) {

switch exp[i] {

case '(‘ || '[' :{Push(S,exp[i]); i++; break;}

case ')' : {

if( ！StackEmpty(S) GetTop(S)= '(' ）

{Pop(S,e); i++;}

else return ERROR;

break; }

case ‘]' : {

if( ！StackEmpty(S) GetTop(S)= ‘[' ）

{Pop(S,e); i++;}

else return ERROR;

break; } }

if (StackEmpty(S)) return OK;

}

三、行编辑程序问题

“每接受一个字符即存入存储器” ?

并不恰当！

设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“@”为退行符。

在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。

合理的作法是：

假设从终端接受了这样两行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);

则实际有效的是下列两行：

while (*s)

putchar(*s++);

可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判断：

1、既不是退格也不是退行符，则将该字符压入栈顶；

2、如果是一个退格符，则从栈顶删去一个字符；

3、如果是一个退行符，则将字符栈清为空栈 。

while (ch != EOF ch != '\n') {

switch (ch) {

case ‘#’ : Pop(S, c); break;//栈非空，退栈

case '@': ClearStack(S); break;// 重置S为空栈

default : Push(S, ch); break; //未考虑栈满

}

ch = getchar( ); // 从终端接收下一个字符

}

ClearStack(S); // 重置S为空栈

if (ch != EOF) ch = getchar( );

}

DestroyStack(S); }

Void LineEdit( ) {

InitStack(S);

ch=getchar();

while (ch != EOF) { //EOF为全文结束符

将从栈底到栈顶的字符传送至调用过程的数据区；

补充习题：

1、设计一个算法，用栈的基本运算，判定一个字符串是否为对称字符串，若是，则返回1，否则返回0。（abccba)

四、表达式求值

1、算术表达式的组成：

将表达式视为由操作数、运算符、界限符（称为单词）组成。

操作数：常数、变量或符号常量。

算符：运算符、界限符

表达式求值是程序设计语言编译的一个最基本的问题。它的实现是栈应用的又一典型例子。 仅以算术表达式为例

2、算术表达式的形式：

中缀(infix)表达式——表达式的运算符在操作数的中间。 操作数 操作符 操作数

例：A*B 例：5+9*7

后缀(postfix)算术表达式(逆波兰式)——将运算符置两个操作数后面的算术表达式。 操作数 操作数 操作符

例：AB* 例：5 9 7*+

前缀(prefix)表达式(波兰式)又称波兰式，与后缀表达式相反。把运算符放在两个运算数的前面， 操作符 操作数 操作数

例：*AB 例：+5*9 7

3、介绍中缀算术表达式的求值

例如：3*（7 – 2 ）

（1）算术四则运算的规则：

a. 从左算到右

b. 先乘除，后加减

c. 先括号内，后括号外

由此，此表达式的计算顺序为：

3*（7 – 2 ）= 3 * 5 = 15

（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2 ，都要比较优先权关系。

一般任意两个相继出现的两个算符p1和p2之间的优先关系至多有下面三种之一：

p1p2 p2的优先权高于p1

p1=p2 二者优先权相等

p1p2 p2的优先权低于p1

算符优先法所依据的算符间的优先关系

见教材P53表3.1

θ1θ2，表明不能进行θ1 的运算，θ2 入栈，读 下一字符。

θ1θ2，表明可以进行θ1 的运算，θ1退栈，运算，运算结果入栈。

θ1=θ2，脱括号，读下一字符或表达式结束。

（3）算法思想：

设定两栈：操作符栈 OPTR ，操作数栈 OPND

栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 ‘#’；

依次读入字符：是操作数则入OPND栈，是操作符则要判断：

if 操作符 栈顶元素，则退栈、计算，结果压入OPND栈；

操作符 = 栈顶元素且不为‘#’，脱括号（弹出左括号）；

操作符 栈顶元素，压入OPTR栈。

扫描基本符号

是否操作数？

Y

栈顶运算符低

于当前运算符？

操作数

入栈

N

Y

N

运算符

入栈

取出S栈顶运算符和

O栈顶的两个操作数

运算，结果入栈O

定义运算符栈S

和操作数栈O

栈S为空？

Y

结束

Y

一般作为相同运算符，先出现的比后出现的优先级高；

先出现的运算符优先级低于“(”，高于“)”；

后出现的运算符优先级高于“(”，低于“)”；优先权相等的仅有“(”和“)”、“#”。

#：作为表达式结束符，通常在表达式之前加一“#”使之成对，当出现“#”=“#”时，表明表达式求值结束，“#”的优先级最低。

OPTR

OPND

INPUT

OPERATE

3*(7-2)#

Push(opnd,’3’)

#

*(7-2)#

3

#

Push(optr,’*’)

#,*

3

(7-2)#

Push(optr,’(’)

#,*,(

3

7-2)#

Push(opnd,’7’)

#,*,(

3,7

-2)#

Push(optr,’-’)

#,*,(,－

3,7

2)#

Push(opnd,’2’)

#,*,(,－

3,7,2

)#

Operate(7-2)

#,*,(

3,5

)#

Pop(optr)

#,*

3,5

#

Operate(3*5)

#

15

#

GetTop(opnd)

例：3*（7-2）

Status EvaluateExpression( OperandType result) {

InitStack(OPND); InitStack(OPTR);

Push(OPTR ,’#’);c=getchar();

while((c!=‘#’)(GetTop(OPTR)!=‘#’))

{ if (!In(c,OP) { Push(OPND,c); c=getchar();}

else switch(compare(c,GetTop(OPTR)))

{case ‘’ : Push(OPTR , c); c=getchar();break;

case ‘=’: Pop(OPTR);c=getchar();break;

case ‘’ : temat=Pop(OPTR); b=Pop();a=Pop();

result= Operate(a,temat,b);Push(OPND,result);

c=getchar();break;

} //switch }//while

result=GetTop(OPND);}//EvaluateExpression

此函数在哪里？

4、计算后缀表达式

（1）为什么要把中缀表示法变为后缀表示法？

计算机计算表达式是机械执行，只能从左至右扫描。计算中缀表达式比较困难。

后缀表达式的求值过程是自左至右运算符出现的次序和真正的计算次序是完全一样的。

顺序扫描表达式的每一项，根据它的类型做如下相应操作：

若该项是操作数，则将其压栈；

若该项是操作符op，则连续从栈中退出两个操作数Y和X，形成运算指令XopY，并将计算结果重新压栈。

当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计

算结果。

人们仍然使用中缀表达式 ，而让机器把它们转换成后缀表达式。

（2）后缀表达式求值实例：

A=B*C + D*(E-F)

ABC*DEF-*+=

ABC*—做 B*C=T1

AT1DEF- –—做E-F=T2

AT1DT2*—做D*T2=T3

AT1T3+—做T1+T3=T4

AT4=—做A=T4

后缀表达式“32422*+13*-^*5-”，栈中状态变化情况：

typedef char elemtype ;

double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结果*/

{ Seq_Starck s ;

ch=*A++ ; Init_SeqStack(s) ;

while ( ch != ’#’ )

{ if (ch!=运算符) Push_SeqStack (s , ch) ;

else { Pop_SeqStack (s , a) ;

Pop_SeqStack (s , b) ; /*取出两个运算量*/

switch (ch).

{ case ch= =’+’： c=b+a ; break ;

case ch= =’-’： c=b-a ; break ;

case ch= =’*’： c=b*a ; break ;

case ch= =’/ ’： c=b/a ; break ;

case ch= =’%’： c=b%a ; break ; }

Push_SeqStack (s, c) ; }

ch=*A++ ;

}

Pop _SeqStack ( s , result ) ;

return result ;

}

（3）中缀表达式变后缀表达式

表达式中操作数次序不变,，运算符次序发生变化,运算符放在操作数的后面。同时去掉了圆括号 。

例：3+（7*8-9）

运算符的优先数表

5

4

3

2

1

优先数

^

*，/

＋，－

＝

）

（

操作

存储结构

W（I）存放表达式的第I个字符。

利用一个栈S（）。P为栈指针。

算法设计

Step1：输入是变量则输出它；

Step2：是左括号“（”，无条件地压入堆栈；

Step3：输入运算符优先数是2，3，4，5时，如果栈空，则进栈。如果栈不空，则将它与栈顶元进行比较。倘若优先数大于顶元，则进栈；小于顶元，则顶元退栈并输出之。然后再继续比较，直到大于顶元或栈空时它进栈；

Step4：若是右括号“）”，同时栈顶元又为左括号“（”，则退栈，并抹去“）”。否则按Step3处理；

Step5：输入完而栈非空，则将栈内内容逐一退栈，并输出之。

模拟算法执行过程

A=B*C+D*(E-F)

ABC*DEF-*+=

)

F

-

E

(

*

D

+

C

*

B

=

A

W（I）:

栈s （）:

top=0

A

变量,输出

输出:

说明:

)

F

-

E

(

*

D

+

C

*

B

=

A

W（I）:

栈s （）:

A

算符,栈空,入栈

=

输出:

说明:

top=0

top=0

top=1

)

F

-

E

(

*

D

+

C

*

B

=

A

W（I）:

=

栈s （）:

top=1

A

变量,输出

输出:

说明:

B

)

F

-

E

(

*

D

+

C

*

B

=

A

W（I）:

=

栈s （）:

AB

算符*,优先级等于4,大于栈顶元素=优先级,入栈

输出:

说明:

*

top=1

top=1

top=2

)

F

-

关于java共享栈实现代码和共享栈的实现的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。