栈以及栈的应用_(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，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。

注：参考王道的《数据结构》