日志

栈的表示和实现

已有 349 次阅读| 2016-3-21 17:44

和线性表类似，栈也有两种存储表示方法。

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，勇士附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法是以top=0表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C做描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后再应用过程中，当栈的空间使用时再逐段扩大。为此，可设定两个常量：STACK_INIT_SIZE和STACKINCREMENT，并以下述类型说明为顺序栈的定义。

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

其中，stacksize指示栈的当前可使用的最发容量。栈的初始化操作为：按设定的初始分配量进行第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。称top为栈顶指针，其初始值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶匀速的下一个位置上。