rambo

栈的应用(转载)

栈是计算机术语中比较重要的概念,实质上栈就是一段内存区域,但是栈满足一定的特性,那就是只有一个口,具有先入后出的特性,这种特性在计算机中有很广泛的运用。其中几个典型的运用如下:判断平衡符号,实现表达式的求值(也就是中缀表达式转后缀表达式的问题以及后缀表达式求值问题),在路径探索中实现路径的保存也可以说是栈的经典运用之一。具体的问题具体分析,只要满足先入后出特性的问题都能找到现成的数据结构---栈。

本文采用C++中的vector实现栈结构,然后利用栈实现判断平衡符号,实现中缀表达式到后缀表达式的转换,并依据栈实现简单的整数加减乘除运算。
首先栈的实现,由于在C++中采用了vector来代替原始的数组操作,这种比较方便的容器能较好的实现数组的功能,而且在实际的计算机里也是采用连续的存储空间作为栈空间的,因此选择vector。主要实现三个操作,push、pop以及为空判断。

补充:栈也可以采用单向链表实现,在表顶端插入元素来实现push,通过删除表顶端元素实现pop。top操作访问表顶。

基本的形式如下:

栈的链表实现

stacktop1

stacktop2

finaltop2

topfinal

典型应用一:当函数调用时,系统会做以下工作:
1)建立栈空间
2)保护现场。将当前主调函数的执行状态和返回地址保存在栈中。
3)为被调函数中的局部变量(包括形参)分配栈空间,并将实参传递给形参。
4)执行被调函数。
5)释放被调函数的所有局部变量栈空间。
6)恢复现场。取出主调函数的执行状态及返回地址,释放栈空间。

典型应用二:符号的平衡问题

在语言中往往需要判断一些符号是否是成对出现的,比如<>,{},[],(),通常在C++中也只有这几种对称问题,如何让判断符号的对称也是很多代码判断的首要任务。

典型应用三:表达式的求值问题

表达式的求值问题主要设计到操作符的优先级问题,比如()、*/、+-这几种符号的优先级是不一样的,其中括号的优先级最高,乘除其次,加减最低,我们通常看到的表达式都是中缀表达式。

转换规则:当读到一个操作数的时候,立即将它放到输出中。操作符不立即输出,而是存放在栈中。当遇到左括号时(有最高优先级),放入栈中。如果遇到右括号,将栈元素弹出,将符号写出直到遇到一个对应的左括号(被弹出而不输出)。

如果遇到其他的符号,那么从栈中弹出栈元素直到发现优先级更低的元素为止。当输入为空时,将栈中元素全部弹出并置空。