文档介绍：第4章栈和队列一、复****要点本章主要讨论3种线性结构:栈、队列与优先级队列。这3种结构都是顺序存取的表,而且都是限制存取点的表。栈限定只能在表的一端(栈顶)插入与删除,其特点是先进后出。队列和优先级队列限定只能在表的一端(队尾)插入在另一端(队头)删除,不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整,令优先级最高的对象调整到队头,其特点是优先级高的先出。而队列不调整,其特点是先进先出。这几种结构在开发各种软件时非常有用。本章复****的要点:1、基本知识点要求理解栈的定义和特点,栈的抽象数据类型和在递归和表达式计算中的使用,在栈式铁路调车线上当进栈序列为1,2,3,?,n时,可能的出栈序列计数,栈的顺序存储表示和链接存储表示,特别要注意,链式栈的栈顶应在链头,插入与删除都在链头进行。另外,需要理解队列的定义和特点,队列的抽象数据类型和在分层处理中的使用,队列的顺序存储表示(循环队列)和链接存储表示,需要注意的是,链式队列的队头应在链头,队尾应在链尾。还需要理解优先级队列的定义和特点。优先级队列的最佳存储表示是堆(heap),本章介绍的表示看懂即可。2、算法设计栈的5种操作(进栈、退栈、取栈顶元素、判栈空、置空栈)的在顺序存储表示下的实现,以及在链接存储表示下的实现。使用栈的后缀表达式计算算法双栈共用一个数组的进栈、退栈、置空栈、判栈空算法及栈满、栈空条件使用两个栈模拟一个队列时的进队列和出队列算法循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现使用tag区分队列空和队列满的循环队列的进队列和出队列操作的实现链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现使用队尾指针rear和队列长度length的链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现队列在分层处理中的使用事例(杨辉三角形按层次打印)双端队列的顺序存储表示及其进队列、出队列算法及队空、队满条件二、难点和重点1、栈:栈的特性、栈的基本运算栈的数组实现、栈的链表实现栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用:用后缀表示计算表达式,中缀表示改后缀表示3、队列:队列的特性、队列的基本运算队列的数组实现:循环队列中队头与队尾指针的表示,队满及队空条件队列的链表实现:链式队列中的队头与队尾指针的表示、4、双向队列:双向队列的插入与删除算法5、优先级队列:优先级队列的插入与删除算法??132)16/(1612???C三、教材中****题的解析4-1改写顺序栈的进栈成员函数Push(x),要求当栈满时执行一个stackFull()操作进行栈满处理。其功能是:动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组,原来栈数组中的元素占据新数组的前MaxSize位置。【解答】template<classType>voidstack<Type>::push(constType&item){if(isFull())stackFull();//栈满,做溢出处理elements[++top]=item;//进栈}template<classType>voidstack<Type>::stackFull(){Type*temp=newType[3*maxSize];//创建体积大二倍的数组for(inti=0;i<=top;i++)temp[i]=elements[i];//传送原数组的数据delete[]elements;//删去原数组maxSize*=3;//数组最大体积增长二倍elements=temp;//新数组成为栈的数组空间}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后进栈,2应压在1上面,不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。356224444111111113323232532532563256432564153441222261113135135413542135421354264-3试证明:若借助栈可由输入序列1,2,3,…,n得到一个输出序列p1,p2,p3,…,pn(它是输入序列的某一种排列),则在输出序列中不可能出现以下情况,即存在i<j<k