“火车排号”这道题凡是期末卷里出现过一次基本年年都会换张小票卷土重来。它表面上是在讲火车进站、出站、避让实际上考的就是数据结构里最基础的那个“后进先出”模型栈。期末模拟卷把它放在第二题通常不是想难倒你而是想用它来检验你有没有真正理解栈的操作顺序。很多同学第一次见到题目时会懵火车不来不往的怎么就和栈扯上关系了等我把场景还原完你会发现这其实就是一道“手写栈模拟”的送分题熟练之后从读题到写完代码用不了十分钟。我先把这道题最常见的原型给你摆出来。某个编组站有一条主线和一条侧线侧线只有一个出入口车开进侧线之后想出来就只能从同一头倒出来。编号为 1 到 n 的火车按 1、2、3……n 的顺序从入口驶入调度员可以把车先开进侧线暂存也可以让车直接从入口开到出口。现给你一个出站顺序的编号序列要你判断这个出站顺序能不能实现。请你注意“侧线只有一个出入口”这八个字它就是整道题的全部要害。这一条侧线等价于一个栈开进侧线是入栈从侧线倒出来是出栈。主线和出口之间没有其他绕行通道所以车不能“插队”更不能“掉头”每辆车一旦进了侧线就被后面的车压住了。想明白这一点题目就已经解决一半了。1. 题目核心场景与考点定位1.1 原题场景编号 1~n 的火车排队过侧线为什么出题老师喜欢用火车而不是直接用数组因为火车场景能把“栈”的物理限制讲得非常直观。编组站里的火车不能像数组里的元素那样随便跳来跳去它只能沿铁轨走直线。主线是唯一的通道侧线是唯一可以暂时停车的地方而侧线的形状是一个只能从同一端进出的“死胡同”。想象一下这个画面1 号车先到如果此时 3 号车还没到1 号车又不能直接走因为出站顺序要求第一个出的是 3 号。那么 1 号车只能先进侧线等着。随后 2 号车来了看到侧线里已经有 1 号车它如果想等 3 号也只能进侧线而且会停在 1 号车的外侧。等 3 号车一到它可以直接从主线开到出口完成“第一个出站”的任务。接下来要出站的是 2 号车它可以倒出来因为它在侧线最外面再接下来才是压在里面的 1 号车。这个过程的每一步都对应栈的 push 和 pop。主线入口的每一辆车要么马上 push 进栈要么先压栈等一等出口每出一辆车就是从栈顶 pop 一次。提示题目里只要出现“只能从一端进出”“先到的被压在后面”“侧线”“避让线”“死胡同”这类描述基本就是在考栈不要往队列上想。1.2 侧线、栈、主线的对应关系把场景翻译成数据结构术语其实非常整齐火车场景数据结构概念编号为 1..n 的火车按序到达入栈序列固定为 1,2,3,...,n把当前车开进侧线push(当前编号)把侧线最外面的车倒出来pop()侧线最外面的那辆车stack.top()车直接从入口开到出口push 后立刻 pop出口给出的编号序列出栈序列为什么要强调“编号按 1 到 n 依次到达”因为它让题目变得非常简单编号越小到得越早。出栈序列里排在前面的某个编号 k有可能是第一个到但不先出也有可能还没到站。最核心的一条约束是如果某个编号已经进了侧线而它又不是当前栈顶那它出不来因为外面压着后面到的车。把“火车排号”当成纯数据结构题来记就是一句话给定入栈序列 1..n 和一个出栈序列判断这个出栈序列是否合法。至于题里到底是火车、汽车、集装箱还是盘子都不影响解法。1.3 合法出站顺序的本质约束先举个例子入站顺序是 1、2、3出站顺序是 3、2、1这个合法吗合法。过程是 1 进栈2 进栈3 进栈然后 3 出、2 出、1 出最后栈空。那出站顺序是 3、1、2 呢不合法。原因也很简单3 要第一个出说明 1、2 都已经进了侧线而且 2 压在 1 外面。3 从主线直接出去后下一个该出的是 1可侧线最外面是 21 被 2 挡住根本出不来。这个例子已经把题目的本质说清楚了。合法的出栈序列必须保证“先进入侧线但编号更大的车不能挡在编号更小的车前面出站”。也就是说一个元素能不能出栈不取决于它本身编号大小只取决于它上面还有没有别人。这个问题不涉及任何复杂的存储结构只需要按题意模拟侧线的进出过程就能判断一个序列是否合法。2. 核心解法用栈模拟出站过程2.1 三步模拟法先记住框架判断过程不复杂我习惯把它归纳成三步准备一个空栈把目标出站序列存进数组用一个指针 j 指向当前需要匹配的目标出站编号。按编号 1 到 n 的顺序依次把当前编号 push 进栈。push 完之后立刻检查栈顶是否和 out[j] 相等如果相等就循环 pop让 j 不断后移直到栈顶不再匹配或栈空为止。全部车辆都入过栈之后如果 j 刚好走到序列末尾说明每个目标出站编号都在合适的时机从栈顶弹了出来答案是合法如果 j 没走到末尾说明后面的编号被挡死了答案是非法。这个框架看起来简单但第三步“循环 pop”是很多人第一次写会漏掉的关键。为什么是“循环”而不是“判断一次就算”因为一个栈顶元素弹出之后新露出来的栈顶有可能仍然等于 out[j]。比如入栈 1、2、3出站目标是 3、2、1压入 1、2、3 后栈顶 3 等于目标 3弹掉之后新的栈顶是 2而下一个目标正是 2于是还要继续弹。只有把这一步写成 while才能完整模拟连续出站的过程。2.2 栈顶能弹就弹为什么这个贪心不会错你可能会问一个问题如果在某个时刻栈顶等于 out[j]但我不想让它出先继续让后面的车进站行不行结论是没必要而且这样做只会更差。因为输入顺序固定是 1 到 n后面的车编号都比当前栈顶更大它们进来只会压在栈顶上面不可能帮助当前 out[j] 更早出站。当前这个编号已经出现在出站序列的正确位置了让它立刻出站只会把下面的元素提前释放出来不会破坏任何未来的出站顺序。反过来如果栈顶不等于 out[j]那说明 out[j] 要么还被压在栈里面要么还没进站。还没进站时只能继续 push 后面的车已经被压在栈里时做什么都没有用只能继续尝试 push。所以整个模拟过程里唯一的决策点就是“能弹立刻弹”这是一个安全且必要的贪心策略。我在给同学讲这个证明时常用一个生活类比你面前放了一摞盘子现在要按指定顺序把它们拿走。如果最上面那个恰好是下一个要拿的你当然应该先拿它如果最上面不是那你就只能先把还没放上来的盘子继续放上来再继续看最上面是谁。这个逻辑和火车侧线完全一致。2.3 复杂度其实很低别被双重循环吓到有人一看到代码里 for 里面套 while就担心是不是 O(n²)。不是。虽然 while 可能会触发多次 pop但每个元素只会被 push 一次、pop 一次所以所有 while 加在一起的总操作次数不会超过 n。整体时间复杂度是 O(n)空间复杂度也是 O(n)因为栈里最多同时存在 n 个元素。对考试来说这个复杂度意味着什么n 取到 10 万甚至 100 万都可以轻松跑完。很多题目会故意把 n 设成 10^5 左右把时间复杂度卡在“必须是 O(n)”这个级别。你只要写出栈模拟就天然满足要求如果你用“枚举所有可能的出入顺序再比对”的思路去做n 稍大一点就直接指数爆炸。3. 完整代码与手算演示3.1 C 参考代码可以直接抄下面这份代码是这道题最通用的模板既能判断合法序列也能作为后面各种变形题的基础。我写 C 版本时会习惯把目标序列用 vector 存起来下标从 0 开始判断时和栈顶比较。#include bits/stdc.h using namespace std; bool check(int n, const vectorint out) { stackint st; int j 0; // j 指向当前要匹配的出站编号 for (int i 1; i n; i) { st.push(i); // 第 i 号车进侧线 while (!st.empty() j n st.top() out[j]) { st.pop(); // 栈顶正好是目标编号放行 j; } } return j n; // 所有目标都匹配上才算合法 } int main() { int n; cin n; vectorint out(n); for (int i 0; i n; i) cin out[i]; cout (check(n, out) ? Yes : No) endl; return 0; }这个写法里有一点要特别提醒while 条件里必须先判断栈非空再访问栈顶。很多人一上来就写 st.top() out[j]结果栈空时还在访问栈顶轻则越界重则段错误。空栈是不存在栈顶的所以这个判断顺序一定不能反。3.2 Python 版五行业务逻辑Python 写起来会更短。如果你平时用 Python 刷题核心逻辑就是下面这几行。 list 的 append 和 pop 天然就是栈操作直接拿列表当栈用即可。def check(n, out): stk [] j 0 for i in range(1, n 1): stk.append(i) while stk and j n and stk[-1] out[j]: stk.pop() j 1 return j n n int(input()) out list(map(int, input().split())) print(Yes if check(n, out) else No)代码里 stk[-1] 就相当于 C 的 st.top()。很多 Python 初学者会把判断写成 stk[0]那是队列的取队头方式不是栈的取栈顶方式。栈只能操作末尾这个细节也正好呼应了题目里的“侧线只有一个口”。3.3 用 n3 的全部出站序列验证一遍口说无凭把 n3 时所有可能的出站序列都列出来用代码逻辑手算一遍你会对这道题更有信心。n3 时一共 3! 6 种排列其中合法序列有 5 个出站序列是否合法模拟过程1 2 3合法1进1出2进2出3进3出1 3 2合法1进1出2进3进3出2出2 1 3合法1进2进2出1出3进3出2 3 1合法1进2进2出3进3出1出3 1 2非法3想先出1和2被压住1出不来3 2 1合法1进2进3进3出2出1出这个表建议你亲手在纸上推一遍尤其是非法的 3 1 2把它推透比背任何公式都管用。以后只要看到类似“大、小、中”这种怪异的相对顺序你就能快速嗅出不对劲。4. 如果题目问“一共有多少种合法排号顺序”4.1 合法出站序列总数卡特兰数公式考试并不总是只让你判断一个序列合不合法有时候会换个问法n 辆车按 1 到 n 进站总共有多少种不同的合法出站顺序这就是卡特兰数问题。答案是第 n 个卡特兰数记作 C_n。计算公式有两个常用形式递推式C_0 1C_{n1} C_0 * C_n C_1 * C_{n-1} ... C_n * C_0通项式C_n C(2n, n) / (n1)前几个卡特兰数是C_0 1C_1 1C_2 2C_3 5C_4 14C_5 42。你留意一下n3 时合法序列是 5 个正好等于 C_3。这不是巧合而是同一个问题的两种表达方式。为什么卡特兰数和火车排号能对应上因为每一次进侧线可以写成左括号“”每一次从侧线出来可以写成右括号“”一个合法操作序列必须满足任何前缀中“进侧线”的次数不少于“出侧线”的次数也就是左括号数量不小于右括号数量。这正是卡特兰数最经典的括号匹配模型。注意如果题目里 n 比较大比如 n 100卡特兰数是一个巨大的数字C 的 long long 放不下。这时候要么上大数要么看题目是否要求对某个大质数取模。真到考试n 一般不会超过 20可以直接用 long long 递推。4.2 把“判合法”改成“数方案”的常用套路如果题目要求你数出所有合法序列的数量而不是列举具体内容一般有两种做法。第一种是动态规划本质就是在递推卡特兰数第二种是直接套公式。我个人建议考试优先用递推式因为不容易写漏取模而且能顺便把前若干项的卡特兰数都打表打出来方便后面继续使用。做这类题时还要警惕一种陷阱题目可能会把“入站顺序”改成一个任意排列而不是 1 到 n。这种问题就不能直接套卡特兰数了卡特兰数只适用于入站顺序严格为 1,2,3,...,n 的经典模型。如果入站顺序是随机排列合法出站顺序的数量就不是卡特兰数而是要用更一般的动态规划去算考试中极少出现。先看清楚输入格式再决定用哪个方法。4.3 用卡特兰数快速排除错误答案卡特兰数在考场上的另一个作用是做“合理性检查”。如果你写程序枚举出 n4 的合法出站序列结果数量不是 14而是 16 或者 12那基本可以断定算法有问题而不是样例有歧义。我自己写这类题时会把卡特兰数当成一把尺子写完代码先跑一个 n3 或 n4 的小数据核对数量是不是 5 和 14这样可以挡住大量低级错误。5. 考场常见翻车点与避坑清单5.1 五大高频错误你踩过几个我批过不少期末卷子发现这道题的翻车点非常集中。这里直接给你列一个速查表考试前看一遍能省很多调试时间。症状原因正确做法直接比较数组元素而不使用栈没理解侧线模型建一个栈用栈模拟while 里先访问 st.top()忽略空栈情况先判空再取栈顶只判断一次栈顶就结束漏掉连续弹栈的可能用 while 循环弹到不匹配为止把目标序列从头到尾遍历比较想用双指针直接匹配输入顺序固定必须用栈承载等待中的车最后用“栈空”判断结果想当然觉得栈必须空正确判断 j 是否等于 n栈空通常伴随 jn最后一条值得多说一句。在出站序列是 1 到 n 的排列时如果所有目标编号都匹配完成那栈自然就是空的但如果你遇到的是变形题出站序列可能只是部分序列此时只靠栈空判断会出错。最稳妥的判断标准始终是目标数组有没有被完整匹配完。5.2 遇到“请输出 push/pop 操作序列”的变形题有些期末题不满足于判断 Yes/No会让你输出具体的操作序列。比如输入出站顺序 2 1 3要你输出“push 1, push 2, pop, pop, push 3, pop”这样的操作记录。解法在模拟时顺手记录即可。push 时记录“当前车辆进侧线”pop 时记录“某编号出站”。核心逻辑和判断合法完全一样只是把原来的返回值变成了一组操作字符串。如果中途发现没法匹配再输出类似“Impossible”的提示。这个变体其实更考察你对模拟过程的理解。很多同学能背出判断代码但真要手写操作序列就卡壳因为脑子里没有一个“栈过程图”。建议平时练习时把每一辆车的入栈、出栈动作都写在纸上哪怕慢一点也要养成“边模拟边记录”的习惯。5.3 边界条件别忽略n0 和 n1n1 没什么好说的任何单一编号都合法因为 1 进栈后立刻弹出即可。n0 时空序列应该返回合法但很多代码里 out 是空数组栈也是空栈直接返回 j n 就会得到 true这没问题。问题往往出在输入格式上如果你用 cin 读 n 后再循环读 n 个数n0 时什么都不用读代码别多读一行否则会把下一组数据的第一个数吃掉。考试时这种边界坑虽然小但一旦踩中整组测试全废。6. 一般化进阶入站顺序不是 1 到 n 怎么办6.1 通用栈模拟代码期末考试喜欢在经典题上做点小改动最常见的是把入站顺序 từ“1、2、3……n”改成任意排列比如输入顺序是 2 1 3让你判断出站顺序 3 1 2 能否实现。这个改动并不可怕模拟框架完全不变只需要把“依次 i1 到 n 入栈”改成“按给定 in 数组依次入栈”。bool checkSeq(const vectorint in, const vectorint out) { stackint st; int j 0; for (int x : in) { st.push(x); while (!st.empty() j (int)out.size() st.top() out[j]) { st.pop(); j; } } return j (int)out.size(); }这里唯一要小心的是如果 out 不一定是 in 的排列代码要防止越界。我在 while 里加了 j out.size()确保 j 不会跑到数组外面。如果题目保证两者都是长度为 n 的排列其实不加这个条件也能跑但加上更保险。6.2 用例子验证通用写法来一个实际例子。入站顺序是 2、1、3出站顺序是 3、1、2。按代码模拟读入 2压栈。栈顶是 2但当前目标是 3不匹配。读入 1压栈。栈顶是 1当前目标还是 3不匹配。读入 3压栈。栈顶是 3匹配目标 3弹出j 指向 1。栈顶变成 1匹配目标 1弹出j 指向 2。栈顶变成 2匹配目标 2弹出j 走到末尾。返回合法。整个过程中1 号和 2 号车虽然入站顺序颠倒但恰好符合侧线的先进后出规则。如果你还停留在“i 从 1 到 n 按顺序遍历”的思路里遇到这种一般化输入就会卡住。所以背通用版代码比背特化版更有价值。6.3 把“火车题”提成“通用栈模板”通用代码的价值在于它其实是一个可以解决很多同类题的模板。括号匹配、表达式求值、浏览器后退、函数调用栈全都共享同一套“后进先出”的核心逻辑。你只要把 in 数组换成输入字符序列把 out 数组换成期望得到的处理结果判断逻辑几乎不用动。我记得有同学问我“为什么我感觉每道栈的题长得都不一样”因为外层场景不同但内层操作全是 push 和 pop。火车排号题的价值就是帮你固化这个模板下一个输入压栈栈顶能匹配就弹匹配不了就继续压。这套思维一旦建立很多题就不再是“新题”而是“老模板换皮”。7. 考场速判技巧与复习锦囊7.1 肉眼快速排查法发现 312 型模式要警惕虽然最终判断应该以栈模拟为准但考场上需要快速评估一个序列时可以用一个小技巧一个合法出站序列里不能出现“编号较大、编号较小、编号介于两者之间”这样的三段模式。简单说就是不能存在三个位置 ijk使得 out[i] 出得最早但最大out[j] 居中却最小out[k] 最后却大小在两者之间这种模式在特化到 1..n 输入时等价于非法的“3 1 2”。举个例子n4 时序列 4 1 3 2 就明显非法。因为 4 最大却第一个出说明 1、2、3 都已经进栈了而下一个该出 1可栈顶是 33 压着 1根本出不来。这类模式肉眼多看几次就能形成条件反射。但我必须强调这不是万能判法最稳妥的还是脑海里的栈过程手边有纸就画没纸就在脑子里跑模拟。7.2 考前十分钟手推一遍核心 while 循环这道题不需要背大段代码我建议考前只做一件小事把三行核心逻辑亲手默写一遍。push(当前入站元素) while 栈不空 且 栈顶 当前目标: pop() 目标指针后移能默写出这个循环且能解释清楚“为什么能连续弹出”这道题就有了八成胜算。剩下的两成在细节先判空再访问栈顶、判断目标是否匹配完、处理输入格式。这三处小点分别对应空栈访问、逻辑判断、边界输入三类常见考试扣分项。7.3 这题的“亲戚”都在哪些章节出现火车排号并不是一个孤立考点。它和以下题目共享同一套解题模板括号匹配问题左括号入栈右括号出栈处理完看栈空不空。表达式求值数值和运算符交替入栈按优先级出栈计算。浏览器的前进后退页面栈和后退栈来回倒腾本质是两个栈。函数调用栈调用函数时压入返回地址函数返回时弹出。迷宫求解的深度优先搜索递归本身就是栈结构。所以复习这道题不只是为了拿这一题的分更是为了把“栈”这一章的框架盘活。你甚至可以自己设计一个变体把火车换成长方体集装箱把侧线换成只能从一侧打开的仓库编号换成货物品类题意一点不变。能顺手写出这类变体的解法说明你是真懂了。最后分享一个我自己的检查习惯。每次写完栈模拟题我都会用 n3 的全部 6 个序列做一次手算测试其中 5 个合法、1 个非法如果代码结果正好是 5 个 Yes 和 1 个 No我才会交卷。这个习惯看起来有点笨但它的好处是能从结果反推逻辑漏洞。比如当你发现自己输出了 6 个 Yes那一定是少了某些匹配条件如果输出了 0 个 Yes那通常是 while 条件写法反了。火车排号这道题难点从来不在“会不会用栈”而在“模拟过程中有没有漏掉约束”。把约束在纸上推一遍考场上的你就不会再被它绊住。