栈与队列相关题目

《栈与队列相关题目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章栈与队列4-2改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull()操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。【解答】templatevoidstack::push(constType&item){if(isFull())stackFull();//栈满，做溢出处理elements[++top]=item;//进栈}template

2、sType>voidstack::stackFull(){Type*temp=newType[3*maxSize];//创建体积大二倍的数组for(inti=0;i<=top;i++)//传送原数组的数据temp[i]=elements[i];delete[]elements;//删去原数组maxSize*=3;//数组最大体积增长二倍elements=temp;//新数组成为栈的数组空间}4-3铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为1,2,3,4

3、,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也是这种

4、情况。出栈序列325641和135426可以得到。356224444111111113323232532532563256432564153441222261113135135413542135421354264-4试证明：若借助栈可由输入序列1,2,3,…,n得到一个输出序列p1,p2,p3,…,pn(它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i

5、…,pn，如果存在下标i,j,k，满足i

6、出栈，k进栈，k出栈。此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj

7、出现pj

8、

9、!(E>F)/*注：按C++的优先级*/(6)!(A&&!((B

10、

11、(C>D)))

12、

13、(C!

14、

15、(6)ABC

16、

17、!&&!CE<

18、

19、4-7设表达式的中缀表示为a*x-b/x↑2，试利用栈将它

20、改为后缀表示ax*bx2↑/-。写出转换过程中栈的变化。【解答】步序扫描项项类型动作栈的变化输出0F'#'进栈,读下一符号#1a操作数F直接输出,读下一符号#a2*操作符Fisp('#')icp('-'),退栈输出#ax*Fisp('#')