《计算机软件基础：12第四章数据结构栈_队列》由会员分享，可在线阅读，更多相关《计算机软件基础：12第四章数据结构栈_队列（12页珍藏版）》请在金锄头文库上搜索。
1、计算机软件基础多媒体教程第十二讲第四章 数据结构4.3 栈和队列4.3.1 栈 定义 只能对始结点(又称始端)进行操作的线性表称为stack(栈，堆栈)。 栈的始端称为栈顶，栈的终端称为栈底。 栈的主要操作包括push(进栈)和push(出栈或者退栈)，它们只涉及到栈顶结点。 进栈操作是指在栈顶添加一个结点，使原来的栈顶结点成为栈顶的下一结点。 出栈操作是从栈内取出栈顶结点，并使原来的栈顶下一结点成为栈顶结点。由此可以看到，最先进栈的结点将最后出栈。因此，栈又被称为先进后出表，记为FILO表(First In Last Out List)。 栈的基本操作和存储空间测试设计一个栈，要给予分配一定
2、的空间，因此在进栈或退栈操作时应注意到栈空间的变化情况。如果在满栈(结点已经占满栈的容量)时执行进栈操作，称为上溢出(overflow)。如果在空栈(栈内没有结点)时执行出栈操作，称为下溢出(underflow)。通常根据栈顶指针的变化来判断是否发生上溢出和下溢出。在程序实现时，必须对上溢出和下溢出的情况加以处理，否则将引起出错。 栈的存储方式按照栈的存储方式，可以分为顺序栈和链接栈。用顺序存储方式实现的栈称为顺序栈，通常可以用数组来构造顺序栈。用链接存储方式实现的栈称为链接栈，通常可以用链表来构造链接栈。【例4-3.1】栈的应用示例：铁路车厢编组下图中铁路的右侧是一个车厢的堆栈，规定从上边轨
3、道进入堆栈的操作为P(push)，从堆栈退出进入下边轨道的操作为O(pop)。通过一系列的进栈和出栈操作，可以对火车车厢进行重新编组。例如经过PPO的操作，原来按1, 2, 3编组的车厢被牵引到各条轨道。而经过PPOPOO的操作，原来按1, 2, 3编组的车厢可以重新编组为2, 1, 3的序列。待编组的火车车厢经过PPO操作的车厢编组编组后的火车车厢4.3.2 顺序栈 数据定义#defineM1000#defineMAXM-1/* 栈容量 */#defineMIN0/* 栈底指针值*/shortStackM; /* 用数组存放栈*/shortTop = MIN-1; /* 栈顶指针，初始为空栈
4、 */ 进栈函数void push(short key) /* 结点值*/if(Top=MAX /* overflow*/| TopMIN-1) /* 非法指针值*/error(); /* 结点进栈，指针加1 */Stack+Top = key; 出栈函数short pop(void)if(TopMAX) /* 非法指针值*/error();/* 返回栈顶结点, 指针减1 */return(StackTop-); 调用方法示例push(key); 调用方法示例key = pop( ); 顺序栈存储空间的讨论上面在函数push和pop中，遇到上溢出(overflow)和下溢出(underflow
5、)时，仅调用了一个出错处理函数error。实际应用中应该能对溢出的情况加以具体处理。下溢出表示程序设计有误，应该检查后加以修改。上溢出表示初始给定的空间太少了。为此，需要重新构造栈。应用中可能要在同一段存储空间使用一个或几个栈，可以采用同向双栈或者相向双栈。 同向双栈在同一个数组中同向存放A栈和B栈。A栈指针：TopA，A栈栈底：MIN，A栈容量：L-1。B栈指针：TopB，B栈栈底：L，B栈容量：MAX。同向双栈出栈的溢出下处理出栈时需要测试是否发生下溢出(underflow)。问题：程序出错(误操作)，须改正。 同向双栈进栈的溢出处理进栈时需要测试是否发生上溢出(overflow)。若A栈
6、和B栈没有同时满栈，可移动B栈，调整栈容量。A栈满，B栈未满：B栈向后移动。B栈满，A栈未满：B栈向前移动。 相向双栈使用A栈和B栈两个栈，在同一个数组中相向存放。A栈指针：TopA，A栈栈底：MIN，A栈容量：TopB-1。B栈指针：TopB，B栈栈底：MAX，B栈容量：TopA+1。 相向双栈出栈的溢出处理出栈时需要测试是否发生下溢出(underflow)。空栈判据：TopA=MIN-1，TopB=MAX+1问题：程序出错(误操作)，须改正。 相向双栈进栈的溢出处理进栈时需要测试是否发生上溢出(overflow)。满栈判据：TopA=TopB-1，或 TopB=TopA+1处理：A栈和B栈
7、没有同时满栈时，能够自动调节，而不需要移动A栈或B栈。4.3.3 链接栈 数据定义#define NODE struct nodeNODEshort num;NODE*next;； /* 用链表存放栈 */ NODE *Top=NULL; /* 栈指针，初始为空栈 */ 进栈函数void push(short key) /* 结点值*/ NODE *node; node=(NODE *)malloc(sizeof(NODE); if(node = NULL)error();/* 满栈(overflow)*/ /* 填入结点数据*/ node-num = key; /* 插入结点*/ node-
8、next = Top; Top=node; 出栈函数short pop(void)short key;NODE *node;if(Top=NULL) error(); /* 空栈(underflow) */ key = Top-number;node = Top; /* 删除结点*/Top = node-next; free(node);/* 释放结点*/return(key); 调用方法示例push(key); 调用方法示例key = pop( ); 空栈管理在链接栈的进栈函数push()中需要调用malloc()申请空间，出栈函数pop()中需要调用free()释放空间。反复调用mallo
9、c()和free()，实际上是增加了与系统打交道的时间。如果次数频繁，将降低程序的运行速度。通常在实用的软件中可以采用空栈管理的办法。采用空栈管理的做法是集中申请一批存储单元，放在空栈内。需要使用结点(进栈)时从空栈取出结点，用完(出栈)后将结点放回空栈，从而提高软件的效率。分别设计空栈的出栈函数popfree()和进栈函数pushfree()，其程序参见教材第252页。从而可以修改链接栈的进栈函数和出栈函数中的相关语句如下： 修改进栈函数申请空间的语句if( ( node=(NODE *)malloc(sizeof(NODE) ) = NULL)改为：if( (node= popfree()
10、 = NULL) 修改出栈函数释放空间的语句free(node);改为：pushfree(node);【例4-3.2】栈的应用示例：PFE的计算 算法描述PFE(无括号表达式，又称后缀表达式或者逆波兰表达式)的计算，是栈的一种应用。即K=kj, (j = 1, , n | kj = 数字或算术运算符+，-，*，/)。以此为程序的输入序列，求PFE的计算结果。求解PFE计算结果的算法为：for(j=1; j=n; j+)if(kj是数字)push(kj)else if(kj是算术运算符op)data = pop()result = pop()result = result op datapush
11、(result)输出result 求解过程以K = -2, 4, *, -7, -为例，用图示法来演示PFE的求解过程。4.3.4 队列 定义 只能在终端添加终结点和只能在始端删除始结点的线性表称为queue(队列，队)。 队的终端称为队尾，队的始端称为队首。 队的主要操作包括enqueue(进队)和dequeue(出队)。 进队操作是在队尾添加一个结点(队尾结点)，并使新加入的结点成为新的队尾结点。 出队操作是在队首取出一个结点(队首结点)，并使原来队首后面的一个结点成为新的队首结点。由此可以看到，最先进队的结点必定最先出队。因此，队又被称为先进先出表，记为FIFO表(Fist In Fis
12、t Out List)。 队的基本操作和存储空间测试类似于栈的情况，设计一个队列，要给予分配一定的空间，因此在进队或出队操作时应注意到队列空间的变化情况。如果在满队(结点已经占满队列的容量)时执行进队操作，称为上溢出(overflow)。如果在空队(队内没有结点)时执行出队操作，称为下溢出(underflow)。通常根据队首指针和队尾指针的变化来判断是否发生上溢出和下溢出。在程序实现时，必须对上溢出和下溢出的情况加以处理，否则将引起出错。 队的存储方式按照队的存储方式，可以分为顺序队和链接队。用顺序存储方式实现的队称为顺序队，通常可以用数组来构造顺序队。用链接存储方式实现的队称为链接队，通常可
13、以用链表来构造链接队。【例4-3.3】队列的应用示例：遗产分割案例某律师受委托执行某富豪留下50亿美元遗产的分割。根据法律，富豪的遗孀为第一继承人，第二继承人是他的子女，第三继承人是他的孙辈，如此往下。根据富豪的遗嘱，第一继承人可得遗产的60%。第二继承人可在遗产余额的60%进行平均分配，第三继承人可在第二继承人遗产余额的60%进行平均分配，如此往下分割。但是每个继承人得到的遗产份额不得超过上一代继承人份额的60%。同时，遗嘱还规定，每人所得的遗产必须是百万美元的整数，如果有余数，留给下一代分配。如果到最后一代分割后还有余数，将捐给慈善机构。需要律师求出每一代继承人的个人份额，每一代继承人的数量，以及留给慈善机构的金额。由于富豪后代众多，七嘴八舌，谁也数不清。律师请一位软件工程师帮忙，采用队列来设计了一个统计继承人的算法。首先，采用一个登记方法，给每个人发一个编号n。然后让每人申报数据D(n,g,b,s)，g(generation)是继承顺序，b(brother)是下一个弟弟妹妹的编号，s(son)是长子编号。通过登记并且输入这些数据，从而可获得对应的家谱图。例如，D(1,1,0,2)表示遗孀的编号为1，她没有兄弟，长子的编号为2。D(10,2,11,9)表示第二继承人为10，下一个弟弟妹妹为11，其长子为9。D(n,g,b,s) 1, 1, 0, 2
