CSP-J 2022 第一轮 第 5 题：栈和队列配合操作，求栈的最小容量

题目

对假设栈 $S$ 和队列 $Q$ 的初始状态为空。存在 $e_1\sim e_6$ 六个互不相同的数据，每个数据按照进栈 $S$、出栈 $S$、进队列 $Q$、出队列 $Q$ 的顺序操作，不同数据间的操作可能会交错。已知栈 $S$ 中依次有数据 $e_1$、$e_2$、$e_3$、$e_4$、$e_5$ 和 $e_6$ 进栈，队列 $Q$ 依次有数据 $e_2$、$e_4$、$e_3$、$e_6$、$e_5$ 和 $e_1$ 出队列。则栈 $S$ 的容量至少是（ ）个数据。

选项

• A. $2$
• B. $3$
• C. $4$
• D. $6$

答案

B

题解

答案是 B．\(3\)。

队列是先进先出的，因此数据进入队列的顺序与出队顺序相同，也就是栈的出栈顺序： \[ e_2,\ e_4,\ e_3,\ e_6,\ e_5,\ e_1。 \]

按这个顺序模拟（栈内元素从左到右表示栈底到栈顶）：

整个过程最多同时存放 3 个数据，所以容量为 3 足够。

为什么不能是 2？ 因为 \(e_4\) 进栈时，\(e_1\) 和 \(e_3\) 都还不能出栈，栈中必须同时容纳 \(e_1,e_3,e_4\)。因此最小容量就是 3。