《数据结构习题解析第4章》由会员分享，可在线阅读，更多相关《数据结构习题解析第4章（24页珍藏版）》请在金锄头文库上搜索。
1、第4章 栈和队列一、复习要点本章主要讨论3种线性结构：栈、队列与优先级队列。这3种结构都是顺序存取的表，而且都是限制存取点的表。栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。而队列不调整，其特点是先进先出。这几种结构在开发各种软件时非常有用。本章复习的要点：1、基本知识点要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为1, 2, 3, , n时，
2、可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。还需要理解优先级队列的定义和特点。优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。2、算法设计 栈的5种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。 使用栈的后缀表达式计算算法 双栈共用一个数组的进栈、退栈、置空栈、判栈空算法及栈满、栈空条件 使
3、用两个栈模拟一个队列时的进队列和出队列算法 循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 使用tag区分队列空和队列满的循环队列的进队列和出队列操作的实现 链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 使用队尾指针rear和队列长度length的链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 队列在分层处理中的使用事例（杨辉三角形按层次打印） 双端队列的顺序存储表示及其进队列、出队列算法及队空、队满条件二、难点和重点1、栈：栈的特性、栈的基本运算栈的数组实现、栈的链表实现 栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的
4、应用：用后缀表示计算表达式，中缀表示改后缀表示3、队列：队列的特性、队列的基本运算队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件 队列的链表实现：链式队列中的队头与队尾指针的表示、4、双向队列：双向队列的插入与删除算法5、优先级队列：优先级队列的插入与删除算法 三、教材中习题的解析4-1 改写顺序栈的进栈成员函数Push (x )，要求当栈满时执行一个stackFull ( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。【解答】templatevoid stack : push (
5、const Type & item ) if ( isFull ( ) ) stackFull ( );/栈满，做溢出处理 elements +top = item;/进栈template void stack : stackFull ( ) Type * temp = new Type 3 * maxSize ;/创建体积大二倍的数组 for ( int i = 0; i = top; i+ ) tempi = elementsi;/传送原数组的数据 delete elements; /删去原数组 maxSize *= 3; /数组最大体积增长二倍 elements = temp;/新数组成
6、为栈的数组空间4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。【解答】(1) 可能的不同出栈序列有 种。(2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后
7、进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 1354264-3 试证明：若借助栈可由输入序列1, 2, 3, , n得到一个输出序列p1, p2, p3, , pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i j k，使得pj pk pi。(提示：用反证法)【解答】充分性：由j k，pj pk，则pj必须在pk入栈之前
8、就出栈；而i j，pj pi，则意味着pi必须先于pj进栈且pj必须先于pi出栈；此外，i k，则表明pk必须在pi之后出栈，这与pj pk pi相矛盾（因为这意味着pj必须在pk之前和pi之后离开，但pi又出现在pk之后）。下面详细解释一下。借助栈由输入序列1, 2, 3, , n，可得到输出序列p1, p2, p3, , pn ，如果存在下标i, j, k，满足i j k，那么在输出序列中，可能出现如下5种情况： i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pi pj pk, 不可能出现pj
9、pk pi的情形； i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有pi pk pj , 不可能出现pj pk pi的情形； i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj pi pk, 不可能出现pj pk pi的情形； i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk pi pj, 也不可能出现pj pk pi的情形； i进栈
10、，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面pi 位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有pk pj pi, 也不可能出现pj pk pi的情形；4-4 将编号为0和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第0号栈的栈顶指针top0等于-1时该栈为空，当第1号栈的栈顶指针top1等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top0增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top1减1得到新的栈顶位置。当top0+1 = top1时或top0 = top1-1时，栈空间满，此时不能再
11、向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。0 m-1bot0 top0 top1 bot1【解答】双栈的类定义如下：#include template class DblStack /双栈的类定义 private: int top2, bot2;/双栈的栈顶指针和栈底指针 Type *elements;/栈数组 int m;/栈最大可容纳元素个数 public: DblStack ( int sz =10 );/初始化双栈, 总体积m的默认值为10 DblStack ( ) delete elements; /析构函数
12、void DblPush ( const Type& x, int i );/把x插入到栈i的栈顶 int DblPop ( int i );/退掉位于栈i栈顶的元素 Type * DblGetTop ( int i );/返回栈i栈顶元素的值 int IsEmpty ( int i ) const return topi = boti; /判栈i空否, 空返回1, 否则返回0 int IsFull ( ) const return top0+1 = top1; /判栈满否, 满则返回1, 否则返回0 void MakeEmpty ( int i ); /清空栈i的内容template DblStack : DblStack ( int sz ) : m(sz), top0 (-1), bot0(-1), top1(sz), bot1(sz) /建立一个最大尺寸为sz的空栈, 若分配不成功则错误处理。 elements = new Typem;/创建栈的数组空间 assert ( elements != NULL );/断言: 动态存储分配成功与否template void DblStack : DblPush ( const Type& x, int i ) /如果IsFull ( )
