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

32 栈的顺序存储结构-顺序栈栈的顺序存储结构简称顺序栈，它是运算受限的顺序表。顺序栈的存储结构是：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。321 顺序栈的类型定义类似于顺序表，用一维数组描述顺序栈中的数据元素的存储区域，并预设一个数组的最大空间。描述顺序栈的通常的习惯做法是以top=0表示空栈，鉴于C语言中数组的下标约定是从0开始，则当以C作描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。为此，可设定两个常量：STACKCSL（存储空间初始分配量）和STACKZL（存储空间分配增量）。下面给出顺序栈的类型定义：#includestdlib.h#define STACKCSL 64 /*顺序栈存储空间初始分配量*/#define STACKZL 8 /*顺序栈存储空间分配增量*/typedef int ElemType; /*栈元素的数据类型定义，它可以是任意的，具体问题时只需根据需要修改本定义语句即可*/typedef struct ElemType *top; /*栈顶指针*/ElemType *bottom; /*栈底指针*/int stacksize; /*当前已分配的存储空间，以栈元素为单位*/seqstack; /*顺序栈类型定义*/seqstack *seqs; /*seqs是顺序栈类型指针*/其中，stacksize指示栈的当前可使用的最大容量，初始化栈时，stacksize的值等于STACKCSL，以后根据需要按分配增量STACKZL增长。bottom是栈底指针，在顺序栈中，它始终指向栈底的位置，如果bottom的值等于NULL ，就意味着栈结构不存在。top是栈顶指针，其初值指向栈底，也就是说top=bottom可作为栈空的标记。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减一。所以，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。图3.2表示了栈顶指针top和顺序栈中数据元素之间的对应关系。18585 toptop topbottom bottom bottom(a)空栈 (b) 元素5、8、1进栈 (c)元素1出栈 top48534859485top top topbottom bottom bottom(d)元素4、3进栈 (e)元素3出栈 （f）栈满图3.2 栈顶指针与数据元素的关系322 基本运算的实现上述顺序栈的类型定义以及本小节将介绍的基本运算操作均放在文件“seqstack.c”中，使用时需要用命令：#includeseqstack.c将其包含到具体的应用程序中去。由于顺序栈的插入、删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单得多。在顺序栈上可以实现初始化栈、进栈、出栈、判栈空、取栈顶元素等几种基本运算，具体算法如下：1 初始化栈该算法用于建立一个容量为STACKCSL的空顺序栈ss。建立时首先使用malloc函数进行内存储区的分配，并将所分配的存储区的起始地址赋给栈底指针bottom。如果bottom不为空，说明分配成功，否则说明分配失败。成功时进行置空栈的操作，失败则退出。具体算法如下：算法3.1void initstack (seqstack *ss)/*初始化一个顺序栈ss*/ss-bottom=(ElemType *)malloc(STACKCSL*sizeof(ElemType);if(!ss-bottom) printf(“初始化栈失败”);return;ss-top=ss-bottom;ss-stacksize= STACKCSL;printf(初始化栈成功！);2.进栈该算法用于向顺序栈ss的栈顶插入一个元素x。算法首先判断栈是否已满，如果栈不满，就直接进行插入操作，否则就使用realloc函数为该顺序栈再多分配增量STACKZL个元素的存储空间。如果分配成功，则修改栈顶指针top的位置和栈的容量stacksize，然后将元素x插入在栈顶位置。具体算法如下：算法3.2Void push(seqstack *ss, ElemType x) /*将元素x插入顺序栈ss的顶部*/if(ss-top-ss-bottom=ss-stacksize) /*判断顺序栈是否已满*/ss-bottom=(ElemType *)realloc(ss-bottom,(ss-stacksize+STACKZL)*sizeof(ElemType);if(!ss-bottom) printf(“栈容量扩充失败”);return;ss-top=ss-bottom+ss-stacksize;ss-stacksize=ss-stacksize+STACKZL;*ss-top=x;ss-top+;注意：如果在顺序栈已满的情况下再执行进栈操作时，就会发生“上溢出”的错误，必须进行栈容量的扩充。3.判栈空该算法用于判断顺序栈ss是否为空栈。算法以栈顶指针top和栈底指针bottom是否指向同一位置为判断条件。这是因为对于栈来说，bottom永远指向栈底的位置，只有栈中没有元素时，top和bottom才可能指向同一个位置。具体算法如下：算法3.3int stackempty(seqstack *ss) /*判断顺序栈ss是否为空*/if(ss-top=ss-bottom) return 1;elsereturn 0; 4出栈该算法用于从顺序栈ss的栈顶删除一个元素，并将该元素的值通过x返回。算法进行时，首先判断栈是否为空，如果为空则是错误操作，不空则将栈顶指针向下移动一个位置。具体算法如下：算法3.4void pop(seqstack *ss，ElemType x)/*从顺序栈ss中弹出栈顶元素置于x中*/if(ss-top=ss-bottom) return ERROR;ss-top-;x=*ss-top; 需要注意的是:在该算法中，删去栈顶元素只要将栈顶指针减1即可，但该元素在下次进栈操作之前仍然是存在的，因此函数pop中应利用变量x返回被删元素。另外，当顺序栈为空时，进行出栈操作会发生“下溢出”错误，应尽量避免。5取栈顶元素将顺序栈ss的栈顶元素通过变量x返回。该算法与pop操作有所类似，只是此算法中栈顶指针不发生变化。算法3.5Void gettop (seqstack *ss, ElemType x)/*取顺序栈ss的栈顶元素置于x中*/if(ss-top=ss-bottom) exit(0);x=*(ss-top-1); 在以上顺序栈的实现算法中，虽然设置了一个存储空间分配增量STACKZL用于堆栈容量不够时进行扩容调整，但是还是要面对“溢出”问题。尤其堆栈的使用非常广泛，经常出现在一个程序中需要同时使用多个堆栈的情形。为了避免出现溢出，需要为每个堆栈分配一个足够大小的空间。然而，要做到这一点往往是很不容易的，原因之一是各个堆栈所需要的空间大小很难估计；原因之二是由于堆栈是个动态结构，各个堆栈的实际大小在使用过程中都会发生动态变化，有时其中一个堆栈发生了上溢出，而其他各堆栈还保留很多可用空间。这就要求设法来解决多栈共享空间的问题。323多栈共享空间假设将多个堆栈顺序地映射到一个已知大小为m的存储空间上。如果只有两个堆栈来共享这m个存储空间，问题比较容易解决：只需要让第一个栈的栈底位于1处，让另一个栈的栈底位于m处。在使用堆栈时，两栈各自向中间伸展，仅当两个栈的栈顶指针相遇时才发生上溢出。这样，两个堆栈之间就做到了余缺互补，互相调剂，从而大大减少了空间的浪费现象，如图3.3所示。栈1 栈2栈1底(1) 栈1顶 栈2顶 栈2底(m)图3.3 两个栈共享向量空间示意图如果有两个以上的堆栈共享空间m，问题的处理就要复杂一些。当然，如果事先知道每个堆栈可能存放的元素的最多个数，那也可以将这m个空间根据各个堆栈的大小合理分配。但是，更多的情况是人们事先并不知道各个堆栈的最大容量。一个解决的办法就是：先将m个存储空间平均分配给n个（n2）栈，每个栈占m/n (不大于m/n的最大整数)个存储空间，当其中任意一个堆栈发生上溢出而整个空间并未占满时，就要进行再调整。进行调整操作时，首先设top1.n为n个堆栈的栈顶指针的集合，topi为第i个堆栈的栈顶指针；设bot1.n+1为n+1个栈底指针的集合，boti为第i个堆栈的栈底指针，位于第i个堆栈实际栈底元素的前一个位置(为了方便对应描述，数组元素top0和bot0不使用)。其中设置第n+1个栈底指针botn+1的目的是为了测试第n个堆栈栈满与否。初始状态如图3.4所示：boti=topi=（i-1）*（m/n）（1in）botn+1=m1 m第1个栈第2个栈 第i个栈第n个栈top1 top2 topi topn botn+1bot1 bot2 boti botn图3.4 多栈共享空间初始状态示意图当没有发生溢出时，各个栈底指针的位置固定不动，只有栈顶指针随各栈的元素增减而移动。经过一段时间以后，整个空间中各个堆栈的状态可能会改变为如图3.5所示的情形。第1个栈 第2个栈 第i个栈 第n个栈 bot1 top1 bot2 top2 boti topi botn topn botn+1图3.5 多栈共享空间一般状态示意图很显然，表示第i个堆栈为栈空的条件是：topi=boti （1in）， 表示第i个堆栈为栈满的条件是：topi=boti+1 （1in）在上述情况中，很容易出现“假溢出”的情况，也就是当用户想在第i个堆栈中插入一个新元素，此时第i个堆栈已满，而其他堆栈实际上可能还很空，整个存储空间可能还有剩余。要想有效利用其他堆栈的剩余存储空间，调整第i个堆栈空间，使得该新元素能够插入到第i个堆栈中，可以进行以下调整：方法一：右移法。该方法在ijn中确定有可用空间的最小j，也就是找到第i个栈右边的第1个有可用空间的栈j（此时必然有topj=0)&(c、-*/(#opt1,则将opt2进栈，然后读下一个单词；如果opt2opt1，opt1退栈作为后缀表达式中的一员输出。此后，继续比较opt2与opt1的优先级（注意，此时的opt1已经不是先前的那个运算符了），直到opt2得到合适的处理。如果opt2=opt1,并且opt2“#”，则opt1退栈且消去opt2，然后继续读下一个单词，重复以上步骤，直到opt1=“#”、opt2=“#”时，算法结束。算法3.10#includeseqstackzztohz()/*设opt为运算符栈，op为运算符集合，super（）为运算符优先比较函数*/seqstack *opt;char c,x;initstack(opt);push(opt,#);c=getchar();while(c!=# | gettop(opt)!= #)if(!In(c,op)putchar(c); /*不是运算符就将其作为后缀表达式的部分输出*/c=getchar（）;elseswitch(super(gettop(opt),c)case :putchar(pop(opt,x);/*栈顶元素优先权高，栈顶元素退栈并输出为后缀表达式*/break;利用上述算法，中缀表达式a-(b+c*d)/e转换成后缀表达式的过程如表