NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 7 题

设栈 $S$ 的初始状态为空，元素 $a,b,c,d,e,f$ 依次入栈 $S$，出栈的序列为 $b,d,f,e,c,a$，则栈 $S$ 的容量至少应该是（ ）。

拿到题别急着套公式，先模拟入栈出栈过程，盯着栈里同时存在的最大值，那才是容量的下限。

很多同学容易把入栈总数6当成答案，或者在模拟时漏掉某次出栈导致栈高算错。其实只要按顺序走一遍：a进、b进、b出（此时栈里只有a）、c进、d进、d出、e进、f进、f出、e出、c出、a出。你会发现栈里最多同时住着a、c、e、f四个元素，所以容量至少是4。

考点与概念

这道题考的是栈的"容量"（能容纳的最大元素数），属于数据结构基础。栈是"后进先出"（LIFO）：只能从栈顶 push 入栈、pop 出栈。题目给定了入栈顺序 a→b→c→d→e→f 和出栈序列 b,d,f,e,c,a，要求推断栈的最小容量。

命题视角

命题人喜欢用"给定入栈顺序和出栈序列，求栈容量"这类题，因为答案往往不是6（元素总数）也不是3（看起来够用的数字），而是中间某个峰值。坑点在于：学生容易只关注"能不能出栈"，而忽略"出栈瞬间栈里到底有多少个元素"。容量必须大于等于"任意时刻栈内元素数的最大值"。