408考研逐题详解：2009年第2题

2009年第2题

设栈 S 和队列 Q 的初始状态均为空，元素 a，b，c，d，e，f，g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b，d，c，f，e，a，g，则栈 S 的容量至少是（ ）

A.1 \qquad B.2 \qquad C.3 \qquad D.4

知识点提炼及解释

1. 栈（Stack）：一种只能在一端进行插入或删除操作的线性表，遵循先进后出（Last In First Out, LIFO）的原则。
2. 队列（Queue）：一种只允许在一端进行插入操作，在另一端进行删除操作的线性表，遵循先进先出（First In First Out, FIFO）的原则。
3. 栈的容量：指栈在任何时候能够容纳的最大元素数目。

方法 1

由于队列遵循“先进先出”的原则，所以，最终队列 Q 的出队序列，即为其入队序列。根据题目已知，每个元素出站后立即入队，则此序列也就是元素的出栈序列。因此，各个元素入栈和出栈过程描述如下：

1. a, b 进栈，而后 b 出栈
2. c, d 进栈，而后 d 出栈
3. c 出栈
4. e, f 进栈，而后 f 出栈
5. e 出栈
6. a 出栈
7. g 进栈，再出栈

如此即得到了出栈序列 b, d, c, f, e, a, g 。

则本题答案为：C，栈的容量至少是 3.

方法 2

对于栈 S 而言，只有进栈（Push(S,x)）和出栈（Pop(S, x)）两种操作，只要执行了进栈操作，则意味着栈内元素数量增 1，执行了出栈操作，则意味着栈内元素数量减 1。根据题目可知，对于栈 S 而言，其进栈和出栈的顺序如下表，并同时在表中列出元素数的变化（初始为 0 ）

从上表可知，栈内元素最多数量是 3 个，所以本题中栈的容量至少是 3。