4-2改写顺序栈的进栈成员函数Push(x),要求当栈满时执行一个 stacke硎()操作进行栈满处理。其功能 是:动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组,原来栈数组中的元素占据新数组 的前 Maxsize位置。 【解答】 template≤ lass Type> void stack<Iype>;psh( const Type&iem){ if( is Full()stackFull (; ∥栈满,做溢出处理 elements [+top]=item; ∥进栈 template<class Type> void stack<Type>:: stackFul(t Type*lemp= new Type[3* maxie];∥创建体积大二倍的数组 for(inti=0;i<=p;汁+) ∥传送原数组的数据 delete elements 删去原数组 maxSice *=3: ∥数组最大体积增长二倍 elements temp: ∥新数组成为栈的数组空间 4-3铁路进行列车调度时,常把站台设计成栈式结构的站台,如右图所示。试问: (1)设有编号为123.456的六辆列车,顺序开入栈式结构的站台,则可能I 的出栈序列有多少种? 34 (2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641 154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何 得到即写出"进栈”或"出栈"的序列)。 【解答】 (1)可能的不同出栈序列有(1/(6+1)*CB2=132种。 (2)不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈,则1,2必须 直在栈中,此时1先进栈,2后进栈,2应压在1上面,不可能1先于2出栈。154623也是这种情况。 出栈序列325641和135426可以得到。 3253256 32564325641 135 1354 1354213542135426 4-4试证明:若借助栈可由输入序列1,2,3,…n得到一个输出序列p,P2P3,…,pn(它是输入序列的某 种排列),则在输出序列中不可能出现以下情况,即存在i<j<k,使得p<P<p。(提示:用反证法) 【解答】 因为借助栈由输入序列1,2,3,…,n,可得到输出序列p,P,p,…,p,如果存在下标i,j,k,满足< j<k,那么在输出序列中,可能出现如下5种情况:(1/(6 1)) 132 6 + C12 = 4-2 改写顺序栈的进栈成员函数 Push (x )，要求当栈满时执行一个 stackFull ( )操作进行栈满处理。其功能 是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组 的前 MaxSize 位置。 【解答】template<class Type>void stack<Type> :: push ( const Type & item ) { if ( isFull ( ) ) stackFull ( ); //栈满，做溢出处理 elements [ ++top ] = item; //进栈 } template<class Type> void stack<Type> :: stackFull ( ) { Type * temp = new Type [ 3 * maxSize ]; //创建体积大二倍的数组 for ( int i = 0; i <= top; i++ ) //传送原数组的数据 temp[i] = elements[i]; delete [ ] elements; //删去原数组 maxSize *= 3; //数组最大体积增长二倍 elements = temp; //新数组成为栈的数组空间 } 4-3 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (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 可以得到。 3 5 6 2 2 4 4 4 4 1 1 1 1 1 1 1 1 3 32 32 325 325 3256 32564 325641 5 3 4 4 1 2 2 2 2 6 1 1 13 135 1354 13542 13542 135426 4-4 试证明：若借助栈可由输入序列 1, 2, 3, …, n 得到一个输出序列 p1, p2, p3, …, pn (它是输入序列的某一 种排列)，则在输出序列中不可能出现以下情况，即存在 i < j < k，使得 pj < pk < pi。(提示：用反证法) 【解答】 因为借助栈由输入序列 1, 2, 3, …, n，可得到输出序列 p1, p2, p3, …, pn ，如果存在下标 i, j, k，满足 i < j < k，那么在输出序列中，可能出现如下 5 种情况：