栈的顺序存储结构顺序栈

1、3. 2栈的顺序存储结构-顺序栈栈的顺序存储结构简称顺序栈，它是运算受限的顺序表。顺序栈的存储结构是：利 用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。3. 2. 1顺序栈的类型定义类似于顺序表，用一维数组描述顺序栈中的数据元素的存储区域，并预设一个 数组的最大空间。描述顺序栈的通常的习惯做法是以top=0表示空栈，鉴于C语言 中数组的下标约定是从0开始，则当以C作描述语言时，如此设定会带来很大不便； 另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说， 在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为

2、栈分配一个 基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。为此，可设定 两个常量：STACKCSL存储空间初始分配量）和 STACKZ（存储空间分配增量）。 下面给出顺序栈的类型定义：#in cludestdlib.h#define STACKCSL 64 /*顺序栈存储空间初始分配量*/#define STACKZL 8 /*顺序栈存储空间分配增量*/typedef int ElemType; /*栈元素的数据类型定义，它可以是任意的，具体问题时 只需根据需要修改本定义语句即可*/typedef struct ElemType *top; /*栈顶指针 */ElemType *

3、bottom; /* 栈底指针 */int stacksize; /*当前已分配的存储空间，以栈元素为单位 */seqstack; /* 顺序栈类型定义*/seqstack *seqs; /*seqs是顺序栈类型指针*/其中，stacksize指示栈的当前可使用的最大容量，初始化栈时， stacksize 的值等于STACKCSL以后根据需要按分配增量STACKZL曾长。bottom是栈底指针，在顺序栈中，它始终指向栈底的位置，如果bottom的值 等于NULL，就意味着栈结构不存在。top是栈顶指针，其初值指向栈底，也就是说top=bottom可作为栈空的标记。 每当插入新的栈顶元素时，指针

4、top增1；删除栈顶元素时，指针top减一。所以, 非空栈中的栈顶指针始终在栈顶元素的下一个位置上。图3.2表示了栈顶指针top和顺序栈中数据元素之间的对应关系。1 1 13top片4optop *bottombottombottom（a）空栈（b） 元素5、8 1进栈（c）元素1出栈top（d）元素4、3进栈（e）元素3出栈（f）栈满图3.2栈顶指针与数据元素的关系3. 2. 2基本运算的实现上述顺序栈的类型定义以及本小节将介绍的基本运算操作均放在文件“seqstack.c ”中，使用时需要用命令：#includeseqstack.c将其包含到具体的应用程序中去。由于顺序栈的插入、删除只在栈

5、顶进行，因此顺序栈的基本操作比顺序表要简 单得多。在顺序栈上可以实现初始化栈、进栈、出栈、判栈空、取栈顶元素等几种 基本运算，具体算法如下：1. 初始化栈该算法用于建立一个容量为STACKCS的空顺序栈ss。建立时首先使用malloc 函数进行内存储区的分配，并将所分配的存储区的起始地址赋给栈底指针bottom 如果 bottom 不为空，说明分配成功，否则说明分配失败。成功时进行置空栈的操 作，失败则退出。具体算法如下：算法 3.1void initstack ( seqstack *ss )/* 初始化一个顺序栈 ss*/ss-bottom=( ElemType *)malloc( STA

6、CKCS*sLizeof( ElemType); if(!ss-bottom) printf( “初始化栈失败” );return; ss-top=ss-bottom;ss-stacksize= STACKCS;Lprintf( 初始化栈成功！ );2. 进栈该算法用于向顺序栈SS的栈顶插入一个元素x。算法首先判断栈是否已满， 如果栈不满， 就直接进行插入操作， 否则就使用 reallo c 函数为该顺序栈再多分配 增量STACKZ个元素的存储空间。如果分配成功，则修改栈顶指针top的位置和栈 的容量 StackSize ，然后将元素 x 插入在栈顶位置。具体算法如下： 算法 3.2Void

7、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

8、;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出栈该算法用于从

9、顺序栈 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返回被删元素。另外，当顺序栈为空时，进行出栈操作

10、会发生“下溢出”错误，应尽量避免。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 用 于堆栈容量不够时进行扩容调整，但是还是要面对“溢出”问题。尤其堆栈的使用 非常广泛， 经常出现在一个程序中需要同时使用多个堆栈的情形。 为了避免出现溢 出，需要

11、为每个堆栈分配一个足够大小的空间。 然而，要做到这一点往往是很不容 易的，原因之一是各个堆栈所需要的空间大小很难估计； 原因之二是由于堆栈是个 动态结构， 各个堆栈的实际大小在使用过程中都会发生动态变化， 有时其中一个堆 栈发生了上溢出， 而其他各堆栈还保留很多可用空间。 这就要求设法来解决多栈共 享空间的问题。323 多栈共享空间假设将多个堆栈顺序地映射到一个已知大小为 m的存储空间上。如果只有两个堆栈 来共享这m个存储空间，问题比较容易解决：只需要让第一个栈的栈底位于 1处,让另一个栈的栈底位于 m处。在使用堆栈时，两栈各自向中间伸展，仅当两个栈的 栈顶指针相遇时才发生上溢出。这样，两个堆

12、栈之间就做到了余缺互补，互相调剂, 从而大大减少了空间的浪费现象，如图 3.3所示。1丨栈1栈2_人_栈1底栈1顶栈2顶栈2底(m)图3.3两个栈共享向量空间示意图如果有两个以上的堆栈共享空间m问题的处理就要复杂一些。当然，如果事先知道每个堆栈可能存放的元素的最多个数，那也可以将这m个空间根据各个堆栈的大小合理分配。但是，更多的情况是人们事先并不知道各个堆栈的最大容量。一个解决的办法就是：先将m个存储空间平均分配给n个(n2)栈，每个栈占|lm/n (不 大于m/n的最大整数)个存储空间，当其中任意一个堆栈发生上溢出而整个空间并 未占满时，就要进行再调整。进行调整操作时，首先设top1.n为n

13、个堆栈的栈顶指针的集合，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)( K i 人人A -bot1 top1 bot2 top2 boti topi botn topn botn+1图 3.5 多栈共享空间一般状态示意图很显然，表示第i个堆栈为栈空的条件是：topi=boti (K i

14、 n),表示第i 个堆栈为栈满的条件是：topi=boti+1( K i n)在上述情况中,很容易出现“假溢出”的情况,也就是当用户想在第 i 个堆栈中 插入一个新元素,此时第 i 个堆栈已满,而其他堆栈实际上可能还很空,整个存储 空间可能还有剩余。 要想有效利用其他堆栈的剩余存储空间, 调整第 i 个堆栈空间, 使得该新元素能够插入到第 i 个堆栈中,可以进行以下调整：方法一：右移法。该方法在i j n中确定有可用空间的最小j，也就是找到第 i 个栈右边的第 1 个有可用空间的栈 j (此时必然有 topjbotj+1 ),然后将 第i+1、i+2第j个栈的所有元素连同栈底指针与栈顶指针都右

15、移一个位置， 使得第 i 个栈空出一个空间。方法二： 左移法。 该方法相对于右移法而言，当第 i 个栈的右边不再有可用空间 时，就在 Kj 1），并作 为一个新的运算对象重复进行上述过程，直到表达式处理完毕。例如：abcd*+e/-的运算过程如表3.1所示。表3.1后缀表达式的计算过程操作顺序后缀表达式Tk c*dabT1+e/-T2 J b+TaEe/-T3 J T2/eaT3-T4 a-T3T4从上面的讨论知道，后缀表达式之所以容易被编译程序处理，是由于它具有 以下特点：（1）后缀表达式中不出现括号；（2） 后缀表达式与中缀表达式的运算对象的先后次序相同，只是所读到的运算符先后次序可能有所

16、改变。正是由于后缀表达式具有以上特点，所以，处理时不必考虑运算符的优先关系。 在具体的处理过程中，需要设置一个堆栈，用来保存已经读到的运算对象。也就是 说，从左至右依次扫描后缀表达式，每读到一个运算对象就将其压入堆栈； 每读到 一个运算符，就从堆栈中取出相应的运算对象进行该运算符所代表的操作，并把运算结果作为一个新的运算对象压入堆栈。 表达式最后的计算结果就是位于堆栈中栈 顶的值。综上所述，表达式的值的计算过程需要经过两个步骤：一是把中缀表达式变 换为后缀表达式； 二是根据后缀表达式产生计算表达式的机器指令序列。 相对而言， 第二个步骤较为简单些，我们先讨论实现第二个步骤的算法。算法 3.8#

17、includeseqstack.cVoid evalution() char c;int op1,op2,c1,result,x=0,val();seqstack *opd; /* 栈 opd 存放操作数及计算结果 */ initstack(opd); /*初始化栈 */空格则读入下一个字符 */若读入字符是数字 */ 将字符数字转化为数值数字 */ 将该数值数字作为操作数进栈 */ 若读入字符为运算printf( “请从键盘输入后缀表达式：”)； while(c=getchar()!=n) /* 后缀表达式未结束 */ if(c= ) continue; /* if(c=0)&(c、-*/(

18、#opt1,则将opt2进栈，然后读下一个单词；如果 opt2opt1 , opt1退栈作为后缀表达式中的一员输出。 此后，继续比较opt2与opt1 的优先级（注意，此时的opt1已经不是先前的那个运算符了），直到 opt2得到合 适的处理。如果opt2=opt1,并且opt2工“ #”，则opt1退栈且消去opt2，然后继 续读下一个单词，重复以上步骤，直到opt仁“#”、opt2= “#”时，算法结束。算法3.10#in cludeseqstackzztohz()/*设opt为运算符栈，op为运算符集合，super ()为运算符优先比较函数*/seqstack *opt;char c,x;in itstack(opt);push(opt, #);c=getchar();while(c!= # | gettop(opt)!= #)if(!I n( c,op)putchar(c); /*不是运算符就将其作为后缀表达式的部分输出*/c=getchar ();elseswitch(super(gettop(opt),c)case :putchar(pop(opt,x);/*栈顶元素优先权高，栈顶元素退栈并输出为后缀表达式*/break;利用上述算法，中缀表