当前位置:   article > 正文

栈以及栈的应用_(3.2) ds:栈->栈的应用 东华oj

(3.2) ds:栈->栈的应用 东华oj

一、栈的定义

栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理,插入和删除操作都在栈顶进行,一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行,因此要有一个size变量来记录当前栈的大小,当进栈时size不能超过数组长度,size+1,出栈时栈不为空,size-1。

二、顺序栈

采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置。

  • 栈顶指针:S.top,初始时设置S.top = -1;栈顶元素:S.data[S.top]。
  • 进栈操作:栈不满时,栈顶指针先加1,再送值到栈顶元素。
  • 出栈操作:栈非空时,先取栈顶元素值,再将栈顶指针减1。
  • 栈空条件:S.top = -1;栈满条件:S.top = MaxSize–1;栈长:S.top+1。

三、共享栈

利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。两个栈的栈顶指针都指向栈顶元素,top0 = -1时0号栈为空,top1 = Maxsize时1号栈为空:仅当两个栈顶指针相邻(top1-top0=1)时,判断为栈满。当0号栈进栈时top0先加1再赋值,1号栈进栈时top1先减1再赋值;出栈时则刚好相反。共享栈是为了更有效地利用存储空间两个栈的空间相互调节,只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1),所以对存取效率没有什么影响。
在这里插入图片描述

四、链栈

采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并规定所有操作都是在单链表的表头进行的。链栈没有头结点,Lhead指向栈顶元素。
在这里插入图片描述

五、栈在括号匹配中的算法思想

  1. 出现的凡是“左括号”,则进栈;出现的是“右括号”,则首先检查栈是否为空,若栈空,则表明该“右括号”多余,否则和栈顶元素比较,若相匹配,则栈顶“左括号出栈”,否则表明不匹配;
  2. 表达式检验结束时,若栈空,则表明表达式中匹配正确,否则表明“左括号”有余。

六、栈在通过后缀表达式求值的算法思想

顺序扫描表达式的每一项,然后根据它的类型做如下相应操作:若该项是操作数,则将其压入栈中;若该项是操作符,则连续从栈中退出两个操作数Y和X,形成运算指令XY,并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后,栈顶存放的就是最后的计算结果。
在这里插入图片描述
注:参考王道的《数据结构》

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号