设栈 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

[tag_link]

正确答案：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。