栈顺序存储结构顺序栈.doc

---顺序栈栈的顺序存储结构简称顺序栈,它是运算受限的顺序表。顺序栈的存储结构是:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。,用一维数组描述顺序栈中的数据元素的存储区域,并预设一个数组的最大空间。描述顺序栈的通常的习惯做法是以top=0表示空栈,鉴于C语言中数组的下标约定是从0开始,则当以C作描述语言时,如此设定会带来很大不便;另一方面,由于栈在使用过程中所需最大空间的大小很难估计,因此,一般来说,在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是:先为栈分配一个基本容量,然后在应用过程中,当栈的空间不够使用时再逐段扩大。为此,可设定两个常量:STACKCSL(存储空间初始分配量)和STACKZL(存储空间分配增量)。下面给出顺序栈的类型定义:#include""#defineSTACKCSL64/*顺序栈存储空间初始分配量*/#defineSTACKZL8/*顺序栈存储空间分配增量*/typedefintElemType;/*栈元素的数据类型定义,它可以是任意的,具体问题时只需根据需要修改本定义语句即可*/typedefstruct{ElemType*top;/*栈顶指针*/ElemType*bottom;/*栈底指针*/intstacksize;/*当前已分配的存储空间,以栈元素为单位*/}seqstack;/*顺序栈类型定义*/seqstack*seqs;/*seqs是顺序栈类型指针*/其中,stacksize指示栈的当前可使用的最大容量,初始化栈时,stacksize的值等于STACKCSL,以后根据需要按分配增量STACKZL增长。bottom是栈底指针,在顺序栈中,它始终指向栈底的位置,如果bottom的值等于NULL,就意味着栈结构不存在。top是栈顶指针,其初值指向栈底,也就是说top=bottom可作为栈空的标记。每当插入新的栈顶元素时,指针top增1;删除栈顶元素时,指针top减一。所以,非空栈中的栈顶指针始终在栈顶元素的下一个位置上。。┋┋185┋┋85┋┋ top top top bottom bottom bottom (a)空栈(b)元素5、8、1进栈(c)元素1出栈top┋┋485┋34859┋┋485toptoptopbottombottombottom(d)元素4、3进栈(e)元素3出栈(f)“”中,使用时需要用命令:#include""将其包含到具体的应用程序中去。由于顺序栈的插入、删除只在栈顶进行,因此顺序栈的基本操作比顺序表要简单得多。在顺序栈上可以实现初始化栈、进栈、出栈、判栈空、取栈顶元素等几种基本运算,具体算法如下:。建立时首先使用malloc函数进行内存储区的分配,并将所分配的存储区的起始地址赋给栈底指针bottom。如果bottom不为空,说明分配成功,否则说明分配失败。成功时进行置空栈的操作,失败则退出。具体算法如下:(seqstack*ss)/*初始化一个顺序栈ss*/{ss->bottom=(ElemType*)malloc(STACKCSL*sizeof(ElemType));if(!ss->bottom){printf(“初始化栈失败”);return;};ss->top=ss->bottom;ss->stacksize=STACKCSL;printf("初始化栈成功!");}。算法首先判断栈是否已满,如果栈不满,就直接进行插入操作,否则就使用realloc函数为该顺序栈再多分配增量STACKZL个元素的存储空间。如果分配成功,则修改栈顶指针top的位置和栈的容量stacksize,然后将元素x插入在栈顶位置。具体算法如下:(seqstack*ss,ElemTypex)/*将元素x插入顺序栈ss的顶部*/{if(ss->top-ss->bottom>=ss->stacksize)/*判断顺序栈是否已满*/{ss->bottom=(ElemType*)realloc(ss->bottom,(ss->stacksize+STACKZL)*sizeof(ElemType));if(!ss->bottom){printf(“栈容量扩充失败”)