3.4 栈

栈（Stack）是一种特殊的线性表。由于其先进后出的运算特性，被广泛用于进程控制或数据恢复。

3.4.1 栈的逻辑结构

栈也是一种线性表，它与普通线性表的区别就在于对其运算仅限定在表尾。

栈的形式化定义为

S ={ D , R }

其中， D ={ a _i | a _i ∈ ElemSet , i =1,2,…, n , n ≥0}； R ={＜ a _i-1 , a _i ＞| a _i-1 , a _i ∈ D , i =2,3,…, n }。

假定栈s=（ a ₁ , a ₂ , a ₃ , ,…, a _{i -1} , a _i , a _{i +1} , …, a _n ），则 a ₁ 为栈底元素， a _n 为栈顶元素。进栈的顺序是 a ₁ , a ₂ , a ₃ , ,…, a _n ，出栈的顺序是 a _n , a _{n -1} , …, a ₃ , a ₂ , a ₁ 。它的显著特点是后进先出，如图3-15所示。

3.4.2 栈的存储结构

顺序存储或链式存储都可以作为栈的存储结构。由于栈的容量一般是可以预见的，而且其运算仅限于栈顶，所以通常采用顺序存储作为栈的存储结构。

3.4.3 栈的运算及应用

1.栈的运算

（1）建立一个栈

栈的存储结构用数组s[n]。设m为栈的上界，则在C语言中，由于第1个数组元素是s[0]，所以栈的上界m等于n-1。设一栈顶指针为TOP，它不必指向数据元素的实际地址，只记录数据元素的逻辑序号即可。当元素尚未进栈时，令TOP等于-1。

（2）数据元素进栈

如果有数据元素进栈，首先检查栈顶指针TOP，如果TOP等于m，则表示栈满，显示出错信息，否则将发生上溢。如果TOP＜m，则令TOP=TOP+1，将该元素赋给s[TOP]。

（3）数据元素出栈

出栈即取走栈顶元素。首先检查栈顶指针TOP，如果TOP=-1，则表示栈空，显示出错信息，否则将发生下溢。如果TOP＞-1，则出栈元素为s[TOP]，然后令TOP=TOP-1。出入栈操作如图3-16所示。

2.栈的应用

栈是一种应用很广的数据结构。举例如下。

1）在交互式图形系统中，将显示区域存入栈中，需要时可以恢复前几次的显示状态。用栈存放每次操作的命令，可以恢复到前几个命令时的状态。

2）自定义表达式中括号作用域的合法性检查。

检查括号作用域的合法性就是检查一个算术表达式中使用的括号是否正确。关于检查的原则，一是左右括号的数目应该相等，二是每一个左括号都一定有一个右括号与之匹配。检查方法为对表达式从左到右扫描。当遇到左括号时，左括号入栈；当遇到右括号时，首先将栈顶元素弹出栈，再比较弹出元素是否与右括号匹配，若匹配，则操作继续，否则，查出错误，并停止操作。当表达式全部扫描完毕时，若栈为空，说明括号作用域嵌套正确，反之说明表达式有错误。 PO8oS0WSxXy4u8dnIJ+KNanWgfW5zcF0nwO7FfspLZErLvs4bZLX8hgxRC6c4TZ5