题目
设栈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。
这个问题很常见