题目
设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是()。
A.1
B.2
C.3
D.4
解答
答案: C
由于队列的特点是先进先出,即栈S的出栈顺序就是队Q的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。
序号 | 说明 | 栈内 | 栈外 | 序号 | 说明 | 栈内 | 栈外 |
1 | a入栈 | a | 8 | e入栈 | ae | bdc | |
2 | b入栈 | ab | 9 | f入栈 | aef | bdc | |
3 | b出栈 | a | b | 10 | f出栈 | ae | bdcf |
4 | c入栈 | ac | b | 11 | e出栈 | a | bdcfe |
5 | d入栈 | acd | b | 12 | a出栈 | bdcfea | |
6 | d出栈 | ac | bd | 13 | g入栈 | g | bdcfea |
7 | c出栈 | a | bdc | 14 | g出栈 | bdcfeag |
栈内的最大深度为3,故栈S的容量至少是3。
【另解】元素的出栈顺序是b,d,c,f,e,a,g,可推出进栈出栈顺序为Push(S,a),Push(S,b),Pop(S,b),Push(S,c),Push(S,d),Pop(S,d),Pop(S,c),Push(S,e),Push(S,f),Pop(S,f),Pop(S,e),Pop(S,a),Push(S,g),Pop(S,g)。假设初始所需容量为0,每做一次Push进行一次“+1”操作,每做一次Pop进行一次“-1”操作,记录容量的最大值为3,所以选C。
这个问题很常见