我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 栈地址 >

栈的经典运用

归档日期:07-02       文本归类:栈地址      文章编辑:爱尚语录

  栈是计算机术语中比较重要的概念,实质上栈就是一段内存区域,但是栈满足一定的特性,那就是只有一个口,具有先入后出的特性,这种特性在计算机中有很广泛的运用。其实在程序员无时无刻不在运用栈,函数的调用是我们间接使用栈的最好例子,因此可以说栈的一个最重要的运用就是函数的调用。但是栈的运用还不止这些,还有很多,其中几个典型的运行如下:判断平衡符号,实现表达式的求值(也就是中缀表达式转后缀表达式的问题以及后缀表达式求值问题),在路劲探索中实现路劲的保存也可以说是栈的经典运用之一。具体的问题具体分析,只要满足先入后出特性的问题都能找到现成的数据结构---栈。

  本文采用C++中的vector实现栈结构,然后利用栈实现判断平衡符号,实现中缀表达式到后缀表达式的转换,并依据栈实现简单的整数加减乘除运算。

  首先栈的实现,由于在C++中采用了vector来代替原始的数组操作,这种比较方便的容器能较好的实现数组的功能,当然栈也可以采用链表实现,但是我认为链表没有数组直观,而且在实际的计算机里也是采用连续的存储空间作为栈空间的,因此选择Vector。主要实现三个操作,push、pop以及为空判断。基本的形式如下:

  在语言中往往需要判断一些符号是否是成对出现的,比如,{},[],(),通常在C++中也只有这几种对称问题,如何让判断符号的对称也是很多代码判断的首要任务。当然实现的方式是多种多样的,采用栈的实现会相对更加简单。基本的实现思路如下:

  假设在读入一串字符串以后,如果遇到对称符号的左边部分,则将其压入栈中,当遇到对称符号的右边部分,则弹出栈中的一个对象,实现比对,如果是对称的,则说明当前的符号是平衡的,如果不对称,则说明当前字符串是不平衡的,当字符串读完以后,如果所有的符号都是平衡的,栈中此时应该就是为空,通过判断栈中是否为空,说明字符串是否是符号平衡的。

本文链接:http://apawoodbury.com/zhandizhi/112.html