扫码获取更多资源

●栈的类型定义

在日常生活中，有很多“后进先出”的例子。例如，把餐厅里洗净的一摞碗看作一个栈。 通常，后洗净的碗总是摞在先洗净的碗上面，最后洗净的碗摞在最上面； 而使用时却是从这 摞碗顶端拿取，即后洗净的先取用。栈的操作特点正是上述实际的抽象。

●栈的定义

栈(Stack)是限定仅可以在表尾进行插入和删除操作的线性表。允许插入和删除的一 端称为栈顶(Top),栈顶将随着栈中数据元素的增减而浮动，且通过栈顶指针指明当前数据 元素位置；不允许插入和删除的一端称为栈底(Bottom),栈底指针并不随着栈中数据元素 的增减而移动，它是固定的。不含任何数据元素的栈称为空栈(Empty Stack) o 栈中有3个数据元素，插入元素(也称入栈)顺序 入栈是a1.a2.a3，当需要删除元素(也称岀栈)时，其顺序只能为a3.a2. alo换言之，在任何时候出栈的数据元素都只能是栈顶元素，即最后 入栈者最先出栈，所以栈中元素除了具有线性关系外，还具有后进 先岀(Last In First Out,LIFO)的特性。栈也可以简称为LIFO表。

在程序设计语言中，也有很多栈的应用例子。例如，在对程序设计语言编写的源程序进 行编译时,类似于表达式括号匹配问题就是用栈来解决的。又如，计算机系统在处理子程序 之间的调用关系时，用栈来保存处理执行过程中的调用层次，等等。

●栈的抽象数据类型

联系我们：