火车排号问题：用栈模拟判断出站序列合法性与卡特兰数应用

火车排号问题最常出现在数据结构期末模拟卷的第二题位置题面讲的是一个火车编组站只有一条死胡同轨道编号从 1 到 n 的列车按顺序开进来让你判断给定的出站序列是否真的能实现。我第一次在试卷上看到这题时第一反应是这不是考全排列吗后来才明白它真正考的是栈——进站顺序固定、只有一个缓冲区、先进去的车会被后进去的车堵住这其实就是教科书上栈的现场版。这篇文章打算把这道题从题面拆解、手推模拟、代码实现到高频变体一次讲透期末复习的同学可以按这个顺序重新过一遍正在学栈的大一同学也能把它当成一个完整案例来参考。1. 题目到底在说什么一个开进死胡同的列车编组场1.1 一句人话版题面题目通常是这样描述的一个车站只有一条轨道这条轨道一端是入口另一端也是出口也就是说列车只能从同一端进、同一端出轨道内部没有任何岔路可以超车。现在有 n 节车厢编号分别是 1 到 n。它们严格按照编号从小到大的顺序驶向车站入口也就是先进站的是 1 号然后是 2 号再是 3 号依次类推。但不要求每节车厢一到入口就必须立刻进站它可以稍微等一等让后面的车厢先进去同样已经进入轨道的车厢也可以选择随时从出口驶出。题目会给你一个长度为 n 的出站序列比如 3 2 1 4 5问你能不能通过合理安排每节车厢的进站时机和出站时机让列车最终真的按照这个序列从另一端驶出如果能够做到输出 YES做不到输出 NO。这个例子里的 3 2 1 4 5 是能做到的1 号先进2 号进3 号进3 号立刻出2 号出1 号出最后 4 号 5 号按顺序直接穿过。整个过程就像一辆接一辆车开进一条死胡同后面的车不出前面的车就别想走。1.2 为什么这道题一定会用栈把轨道抽象出来你会发现它完全符合栈的三个特性后进先出、只能操作顶部元素、容量有限。进站操作对应 push出站操作对应 pop而当前停在轨道出口处的车厢就是栈顶元素。整道题没有一个地方明确写着请使用栈但只要你把物理场景翻译成数据结构语言所有规则都严丝合缝地对上了。这也是出题人喜欢把模板题包装成工程场景的原因。剥掉题面中的火车、轨道、编组场这些词剩下的是一个再朴素不过的问题给定入栈顺序 1 到 n判断某个出栈序列是否合法。1.3 最常见的认知误区它不是考全排列我见过不少同学拿到这题的第一反应是枚举所有可能的出站顺序然后拿题目给的序列去比对。如果 n 只有三四个这种暴力思路还能跑一旦 n 到了几百甚至几千枚举 2^n 种进出时机、n! 种排列就已经完全离谱了。但更根本的问题在于把思路局限在全排列上会让人忽略这道题的本质它在考栈操作的合法性而不是考排列组合的数量。举个例子出站序列 3 1 2 和 3 2 1 都是 1 2 3 的排列但前者做不到后者做得到。原因后面会详细推演这里先记住一个结论合法的出站序列一定是合法栈操作的输出序列不是随便一个排列都可以。另一类误区是认为只要序列整体呈现某种规律就行比如以为必须是倒序、或者必须是原序。这也是错的。n 5 时像 2 5 4 3 1 这种看似半乱序的序列其实也是合法的只要你能在纸上完整模拟一遍。1.4 用堵车来理解栈顶的约束想快速理解这道题可以把轨道想象成一条只能倒车的窄巷子最先进去的车停在巷子最里面后进去的车停在巷子口后进去的车不先出来里面的车就只能干等。因此一旦某节车厢选择进站它出来的时候就必须被它之后进站的车压制着。说得专业一点在任意时刻能够出站的车只有栈顶那一节栈顶不满足出站序列的要求时你只能继续让新车入栈而不能跳过栈顶去拿更里面的车厢。这个约束就是整道题的灵魂。理解了它后面的模拟逻辑就顺理成章了。2. 手推栈模拟合法出站与非法出站各跑一遍2.1 先定义好三根指针在做任何代码之前先把三个核心概念定下来。第一个是当前进站车厢编号 cur因为进站顺序固定为 1 到 n所以 cur 的初始值是 1每入栈一节车厢就加 1。第二个是出站序列指针 idx它指向出站序列中当前需要匹配的位置初始为 0。第三个是栈本身栈底到栈顶保存着已经进站但还没有出站的车厢。模拟的策略非常简单不断尝试让当前车厢出站。能出站的情况只有两种第一当前要进站的车厢编号恰好等于出站序列需要的编号那就直接进站并立刻出站等价于 cur 和 idx 同时前进第二当前栈顶元素恰好等于出站序列需要的编号那就弹出栈顶idx 前进。如果这两种情况都不满足就把当前车厢压入栈中cur 前进等待后续匹配。当所有车厢都已经进过站也就是 cur 大于 n而出站序列还没匹配完此时如果栈顶仍然不等于目标编号就说明没有任何操作可以继续了序列非法。2.2 合法序列 3 2 1 4 5 的完整推演以 n 5、出站序列 3 2 1 4 5 为例跟着流程走一遍。第 1 步cur 1目标 3。1 不等于 3且栈为空压入 1。栈内1。第 2 步cur 2目标 3。2 不等于 3栈顶 1 不等于 3压入 2。栈内1 2。第 3 步cur 3目标 3。cur 等于目标进站即出站cur 变为 4idx 指向 2。栈内1 2。第 4 步cur 4目标 2。cur 不等于 2但栈顶是 2弹出 2idx 指向 3。栈内1。第 5 步cur 4目标 1。cur 不等于 1栈顶是 1弹出 1idx 指向 4。栈内为空。第 6 步cur 4目标 4。cur 等于目标进站即出站cur 变为 5idx 指向 5。第 7 步cur 5目标 5。cur 等于目标进站即出站idx 指向 6匹配结束。整个过程没有任何一步卡住所以 3 2 1 4 5 是合法序列。注意这里的一个关键点1 号车厢很早就进站了但它一直等到 2 号和 3 号都出完才出来因为它在栈底被上面两节车厢堵住这是完全符合物理直觉的。2.3 非法序列 5 4 1 2 3 究竟卡在哪里再来看一个非法序列5 4 1 2 3。第 1 步cur 1目标 5。压入 1。第 2 步cur 2目标 5。压入 2。第 3 步cur 3目标 5。压入 3。第 4 步cur 4目标 5。压入 4。第 5 步cur 5目标 5。5 进站即出站cur 6idx 指向 4。栈内1 2 3 4。第 6 步cur 6目标 4。cur 已经大于 n没有新车可进。栈顶是 4等于目标弹出 4idx 指向 1。栈内1 2 3。第 7 步cur 6目标 1。栈顶是 3不等于 1也没有新车能入栈模拟卡死输出非法。问题出在最后一步1 号车厢虽然在栈里面但它是最早入栈的此时上面压着 2 号和 3 号。想让它出站必须先让 2 号和 3 号出站可出站序列要求 1 先出这就形成了一辆被堵死的火车。整个序列只能作废。2.4 判定条件的本质只有一种情况会让模拟卡死把上面两个例子放在一起就能提炼出唯一的失败条件当所有车厢都已经进过站栈顶元素依然不等于出站序列当前需要的编号。为什么这是唯一失败条件因为在其他任何时刻你都至少还有三种选择之一要么当前车厢正好可以被直接出站要么栈顶能满足要求要么还能把新车压进栈里等待后续。只有新车已经全部进场、栈顶又不匹配这一个瞬间所有路径都被封死游戏结束。这个结论非常重要它是后面代码实现里 while 循环退出条件和 ok 标志位的直接依据。理解了它你甚至不需要背代码现场都能把逻辑写出来。3. 从手推变成代码数组栈实现和三类 WA 现场3.1 一份可以直接跑的 C 代码有了上面的模拟思路代码写起来非常自然。数据结构考试通常允许用 C/C 写我习惯用数组模拟栈完整代码是这样#include stdio.h #define MAXN 100005 int target[MAXN]; int stack[MAXN]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%d, target[i]); } int top 0; // 栈顶指针指向栈中元素数量 int cur 1; // 下一节要进站的车厢编号 int idx 0; // 出站序列当前匹配位置 int ok 1; while (idx n) { if (cur n cur target[idx]) { // 当前车厢正好是需要的进站后立即出站 cur; idx; } else if (top 0 stack[top - 1] target[idx]) { // 栈顶车厢正是需要的弹出 top--; idx; } else if (cur n) { // 暂时匹配不上先压栈 stack[top] cur; } else { // 所有车都进过站栈顶却匹配不上 ok 0; break; } } printf(%s\n, ok ? YES : NO); return 0; }这段代码的核心就是那四分支判断。很多人会纠结分支顺序其实顺序是固定的先判断当前进站车厢等于目标再判断栈顶等于目标最后才压栈。如果一上来就压栈就等于假设当前车厢一定要先进站这会丢失进站后立即出站的情况导致把合法序列误判成非法。3.2 为什么我坚持用数组而不是库里的栈不少同学会问C 里不是有 std::stack 吗直接用不好吗如果你只是为了 AC当然可以。但在考试和平时训练里我更推荐数组模拟原因有三个。第一个原因是中间态可见。数组本质上允许你随机访问栈内任意位置打印调试时可以直接把 stack[0] 到 stack[top-1] 全部输出一眼就能看出是哪节车厢堵住了问题。用库里的栈只能看到栈顶排错效率低很多。第二个原因是逻辑更贴合手推过程。手推时我们会说栈内1 2 3数组模拟可以直接打印出来和草稿纸上的过程一一对应。用库栈时反而要不停地 pop 才能看到内部容易打乱调试节奏。第三个原因是考题环境的不确定性。有些在线评测系统或者学校机房环境老旧C 版本兼容性一般而纯 C 数组栈在任何环境里都能编译运行不会因为标准库差异出问题。3.3 边界用例n 很小的时候反而最容易错我见过很多同学大用例全对、小用例翻车问题往往出在边界条件上。把常见的极端情况整理成一张表复习时直接过一遍用例出站序列预期结果模拟中的关键点n 11YES只有一个车厢直接进站即出站n 1无输入非法实际题面会保证长度但代码要能处理n 31 2 3YES每节车都进站即出站n 33 2 1YES全部压栈后从栈顶依次弹出n 33 1 2NO3 出站后栈顶是 21 被压在下面n 52 5 4 3 1YES2 先出5 进站后 4 3 依次压栈再出最后一行的 2 5 4 3 1手动推一遍就能体会半乱序才是这类题的常态。很多同学只记住了全倒序合法遇到这种混合序列就懵了其实是没把模拟过程走熟。3.4 三类典型 WA 以及排查思路如果提交后答案错误大概率是下面三种情况之一。第一类是目标序列没有先校验。题目说的是1 到 n 的一个排列但有些题的输入并没有保证这一点比如出现重复数字、或者出现大于 n 的数字。如果不在模拟前检查序列元素是否恰好是 1 到 n 的排列代码可能对某些非法输入给出错误输出。稳妥做法是加一个标记数组统计每个数字出现次数。第二类是循环结束条件写错。有人会把循环写成 while (cur n || top 0)这在某些题目里没问题但会破坏四分支结构的简洁性。我的建议是坚持以 idx n 作为唯一循环条件所有失败情况在循环体内处理这样逻辑更不容易漏。第三类是输出格式问题。题目要求输出 YES 还是 Yes输出 Legal 还是 OK每次都要先看清楚。这种错误最冤枉属于样例过了、格式跪了。建议把输出语句单独写避免在复杂表达式里拼字符串出错。4. 一道题背后的一串题卡特兰数与高频变体4.1 合法的火车出站序列一共有多少种很多期末卷不会只满足于让你判断一个序列是否合法还会追加一问n 节车厢进站后总共可能有多少种不同的合法出站序列这个问题的答案就是卡特兰数。n 个元素入栈出栈合法出栈序列的数量是第 n 个卡特兰数公式为 C_n C(2n, n) / (n 1)。n 3 时是 5n 4 时是 14n 5 时是 42。为什么是这个数把每节车厢的入栈记作 1出栈记作 -1整个过程的任意前缀都要满足入栈次数始终不少于出栈次数因为栈不能弹出空元素。这等价于从坐标原点出发、每次向右上或右下走一步、但永远不落到 x 轴以下的一条路径恰好就是卡特兰数的经典模型。这个结论对备考很有用。比如某道题要求你输出所有合法序列或者统计数量你可以先用卡特兰数算一个预期值来验证自己程序的正确性能省下大量调试时间。4.2 变体一进站顺序不再是 1 到 n有些题目会把进站顺序固定为 1 到 n改成给定一个任意的进站序列再给你一个出站序列问能不能通过栈操作实现。比如进站顺序是 2 5 3 4 1出站序列是 5 4 3 2 1。这不代表答案一定是 YES需要重新模拟。代码改动很小把前面代码里的 cur 从当前编号改成进站序列数组的下标指针每次压栈时压入的是进站序列此时的元素而不是 cur 本身。我见过有的同学碰到这种变体就慌了觉得题目变难了。其实完全没有核心的判定逻辑一模一样只是进站车厢编号换成进站序列当前指向的车厢而已。理解这一点就能以不变应万变。4.3 变体二车厢重排问题——缓冲轨道不是栈而是队列还有一个出场率很高的亲戚题叫做车厢重排问题。题面是入口处停着一列乱序车厢比如 5 3 1 4 2出口方向要求按 1 到 n 的顺序驶出。中间有若干条缓冲轨道轨道两端都可以操作。这里的两端都可以操作很重要它意味着每条缓冲轨道是队列而不是栈。策略是把每节车厢放到某条合适轨道的末尾让每条轨道内部的队列保持单调性质最终按顺序驶出。这种题和你今天做的火车排号有本质区别栈只能从一头进出队列可以从两头进出栈靠后进先出约束队列靠先进先出约束。如果你把今天的栈模型硬套到车厢重排上十有八九会写错。复习时可以把两种模型对照着做一道判断序列合法性一道计算最少需要的缓冲轨道数一个题组就把栈和队列两个知识点全串起来了。4.4 变体三顺带求栈的最小容量第三种变体更隐蔽。题目可能不问序列是否合法而是问给定一个合法出站序列车站轨道至少需要能同时停多少节车厢解法就是在模拟过程中记录栈的最大深度。每压入一节车厢就统计一下当前 top 的值最后取最大值输出。有时候题目还会加上容量限制比如轨道最多只能停 3 节车厢判断序列是否还能实现。那就更简单了在压栈分支里加一句 if (top 1 limit) 直接判非法。这个变体让我联想到实际工程里的缓冲区设计。很多调度系统的核心问题就是在保证处理顺序正确的前提下缓冲区最小该设多大。把栈最大深度算出来本质上就是在做缓冲区容量的静态分析。5. 考场上的 30 秒速判与自查清单5.1 不写代码怎么快速判断一个序列合不合法考试时间紧张时有时候你不需要在代码里模拟只用在草稿纸上人工判断。这里分享一个我常用的快速规则。从左到右看整个出站序列遇到一个比较大的数 x 出站时关注它后面所有比 x 小的数。这些数在被 x 挡住之前一定都已经在栈里了。x 出站后它们只能按照后进先出的栈顺序依次弹出所以它们在出站序列里必须呈现严格递减的顺序。举个例子判断 4 2 5 3 1 是否合法第一个出站的是 4后面比 4 小的数有 2、3、1但实际顺序是 2、3、1不是严格递减因为 2 在 3 前面却比 3 小这就违反了栈序直接判非法。再验证一个合法例子 2 5 4 3 1第一个出站的是 2后面比 2 小的只有 1没问题第二个出站的是 5后面比 5 小的是 4、3、1顺序是 4、3、1递减没问题继续检查 4后面比 4 小的是 3、1递减最终合法。这个规则在手推和检查代码时非常快。它本质上就是栈的后进先出约束在数列上的一种表现不需要记忆复杂公式只需要反复朗读一句话大数先走后小数段必须倒着走。5.2 出题人藏在题面里的三个小改动考场上最怕的不是题目难而是题面里藏着不显眼的小改动让你把旧题直接套上去。针对火车排号这个模型我总结过三个高频改动。第一个改动是可以延迟进站还是到站必须立刻进站。如果是后者那问题就退化成按顺序进站每一辆要么直接出要么压栈判定的本质还是栈但可操作空间更小。第二个改动是轨道是死胡同还是轨道两端都能进出。前者是栈模型后者是队列模型解题思路完全不同。看到两端两个字一定要立刻警惕这不是同一个题。第三个改动是输出要求的侧重点。有的题要求输出是 YES/NO有的要求输出最小栈容量有的要求输出全部合法序列。提前看清楚最后一问能避免写完主程序才发现漏了第二问的尴尬。5.3 从踩坑经验里总结的自查清单每次做完这类题我都会按下面的清单过一遍基本能堵住大部分疏漏。序列本身必须是 1 到 n 的排列重复或越界要提前拦截。while 循环的唯一推进条件设置为出站序列指针而不是栈空或新车指针。分支顺序固定当前进站等于目标然后栈顶等于目标最后压栈。所有车厢都进过站后若栈顶还不匹配果断判非法。若题目附带求栈最大容量在压栈分支更新最大值。输出前确认是 YES/NO、Legal/Illegal 还是数字形式。这套清单看起来琐碎但每次考试前扫一眼真的能拦下很多低级错误。尤其是分支顺序这一条我见过太多同学因为把压栈写在前面把 1 2 3 这种原序序列都判成了非法。说实话火车排号这类题在数据结构里属于典型的模型一眼看穿、代码量不大、细节决定成败的题目。我自己最大的体会是不要急着写代码先在草稿纸上用三根指针完整推两个序列一个合法一个非法推完再动手写循环。这个习惯帮我避免过很多次逻辑混乱。如果你在复习这套期末模拟卷建议把这道题当作栈章节的标准例题反复温习因为它把所有栈的核心特性都浓缩在了一个画面里一列火车开进一条死胡同出不来的车只能等上面的车先走。