扫码获取更多资源

●栈的存储表示及操作实现

和线性表类似，栈也有两种存储表示：顺序存储表示和链式存储表示。

●顺序栈及操作实现

顺序栈的定义

把自栈底到栈顶的元素按照逻辑顺序依次存放在一组地址连续的存储单元里的方式称 为栈的顺序存储结构，釆用这种存储结构的栈称为顺序栈（Sequential Stack） e同时附设指 针top指示栈顶元素在顺序栈中的位置（相对地址）。

通常的做法是以top = 0表示“空栈”。鉴于C语言中数组下标约定从0开始，因此对用 C语言描述的顺序栈需要以top= —1表示空栈。图3-3给出了顺序栈中的栈顶指针和栈 中元素之间的关系。

顺序栈的类型定义

釆用结构类型来定义顺序栈类型，在顺序栈的结构定义中：

（1）类似于顺序表，用一维数组描述顺序栈中数据元素的存储区域。

（2）考虑到栈顶位置是随着进栈和出栈操作而变化的，应该设计一个整型量top（通常 称为栈顶指针）来指示当前栈顶数据元素的相对位置。

（3）考虑到栈的长度可变，需要设计一个表示栈当前存储空间的域。

因为栈所需要的容量会随问题不同而异，所以为顺序栈定义了一个“存储空间的分配增 补量”，为动态扩充数组容量提供方便；也就是说，一旦因为插入数据元素造成空间不足时 可进行再分配，为顺序栈增加一个大小为STACKJNCREMENT个数据元素的空间。

顺序栈的操作实现

初始化操作

联系我们：