首页 > 试题广场 >

现有初始状态均为空的栈X和队列Y,元素a、b、c、d、e、f

[单选题]

现有初始状态均为空的栈X和队列Y,元素a、b、c、d、e、f、g依次进入栈X,每个元素出栈后即进入队列Y,如果出队列的顺序为b、c、f、e、g、d、a,则要求栈X最小容量为()

  • 6
  • 5
  • 4
  • 3
由于队列是先进先出线性表,队列Y的出队顺序为b、c、f、e、g、d、a,则入队顺序必定也是b、c、f、e、g、d、a,这一顺序就是栈X的出栈顺序。又由于入栈顺序为a、b、c、d、e、f、g,因此入栈和出栈顺序是:a、b入栈,b出栈,c入栈,c出栈, d、e、f入栈,f、e出栈,g入栈,g、d、a出栈。因此栈中驻留元素最多是4个,因此栈X的容量至少应该为4。
发表于 2018-07-27 15:46:48 回复(0)
C
发表于 2019-03-20 17:40:43 回复(0)
发表于 2019-03-10 15:30:40 回复(0)
小技巧:

队列顺序遍历的每个元素,
判断当前元素之后有几(n)个元素 在其原本入栈位置之前,依次判断每个元素,找出最大值MAXn
则栈的最小容量为MAXn+1 
例如:
入栈顺序 a、b、c、d、e、f、g
出队列(也是出栈)顺序:b、c、f、e、g、d、a
① 出队列元素b,其后面只有a原本在它前面,则n=1;(b出栈时,a还驻留在栈中)
② 出队列元素c,其后面也只有a原本在它前面,则n=1;(c出栈时,a还驻留在栈中)
③ 出队列元素f,其后面有a、d、e原本在它前面,则n=3;(f出栈时,a、d、e还驻留在栈中,所以加上f容量总共为4)
④ e,...a、d...,n=2;
⑤ g,...a、d...,n=2;
⑥ d,...a...,n=1;
最大为3,因此最小容量为n+1=4;
以上是个人的脑回路,有什么错误欢迎指正。
编辑于 2019-01-26 21:25:35 回复(0)