栈的定义及抽象数据类型

3.1　栈的定义及抽象数据类型

栈（stack）是一种特殊的线性表,这种表只能在固定的一端进行插入与删除运算。通常称固定插入、删除的一端为栈顶（top）,而另一端称为栈底（bottom）。位于栈顶和栈底的元素分别称为顶元和底元。当表中没有元素时,称为空栈。为了与一般的线性表相区别,通常将栈的插入操作称为入栈,将删除操作称为出栈。

假设线性表S＝（a,b,c,d,e）是一个栈数据结构,并且规定只能在末尾进行插入和删除操作,则该线性表的尾端为栈顶,起始端为栈底,元素e为顶元,元素a为底元。栈最大的特点在于利用这种数据结构能够将元素按照入栈顺序的逆序进行输出。例如:将S中的元素按照a、b、c、d、e的顺序依次入栈,则出栈的元素顺序为e、d、c、b、a,如图3－1所示。可以发现,最先进入栈中的元素a最后才出栈,最后入栈的元素e最先被出栈,因为栈的这一特性,故又将其称为后进先出的线性表（last in first out,简称为LIFO）。现实生活中很多活动都具有栈的特性,例如,一摞盘子或一摞书,要从这样的一摞物体中取出一件物体或多放入一件物体,只有在顶部操作才是最方便的。

图3－1　栈的示例

栈也因为其后进先出的特性在程序设计领域有着广泛的应用。例如,考虑图3－2所示的函数调用的过程,其中包含1个main函数和3个自定义函数a1,a2,a3。在执行主函数main（）时,首先调用函数a1,当a1执行完毕后,应由a1返回到主函数,并从语句r开始继续执行。同样,在函数a1执行时,要调用a2,返回后应从语句s开始接着执行。最后,在函数a2执行时,要调用a3,返回后从语句t开始继续执行。由于返回的顺序和调用的顺序正好相反,所以,处理嵌套调用最简单的方法是设置一个返回地址栈,每次进行函数调用时,就把相应的返回地址送进栈；而当函数执行完毕时,再从栈顶取出返回地址。如上例中,返回地址按r、s、t依次进栈,而出栈的顺序却是t、s、r,栈数据结构使这一问题得到了圆满解决。类似的函数的递归调用问题也需要栈记录函数的返回地址。

图3－2　函数的嵌套调用

栈的基本操作除了入栈和出栈之外,还包括栈的初始化、判空及获取栈顶元素等。栈的抽象数据类型的定义如下。