算法与C++实现避坑指南)
简介针对列车编组调度问题的C解题代码包对应经典栈模拟场景。题目设定一条单轨单向铁道车厢从A端驶入经中转盲端S从B端驶出S容量有限且内部无法调头或超车需利用栈的先进后出特性判断编号序列能否在限定容量下重排为指定次序。本次资源面向数据结构课程学习者、算法竞赛选手及需要掌握栈应用的开发人员可作为课程设计参考或刷题对照实现。压缩包共1个文件类型为cpp整体大小约1KB结构紧凑便于快速查看核心逻辑并自行扩展测试。目前已有1585人学习下载代码可直接用于验证不同输入条件帮助理解容量受限时栈模拟的边界处理、出入栈顺序与合法重排序列之间的关系。1. Pa2-1 到底在解什么题一个带容量上限的列车调度栈模型Pa2-1 这套代码压缩包里只有两个文件但解决的问题比文件数量有意思得多一列编号为 1 到 n 的车厢按某个给定顺序从入口 A 驶入经过中转盲端 S 后从出口 B 驶出问最终能否以 1、2、……、n 的次序全部开出去。S 是一个单轨单向的缓冲区域容量上限为 m车厢在里面不能调头、不能超车——这个约束翻译成数据结构就是一座容量为 m 的栈。这个场景很适合正在做数据结构课程设计、刷算法题遇到“车厢调度”变形题的人也适合想看看一个经典栈模拟题如何在 O(n) 时间内写干净的人。下面把模型、代码、以及几个容易让人翻车的边界条件一起拆开。2. 把铁轨规则翻译成栈模型入口A、中转盲端S和出口B的语义映射题目给出的交通规则乍看像物理题但只要把“列车”换成“元素”、“铁道”换成“数据结构”它就是一个标准的栈模拟问题。很多人卡住是因为没有把 A、S、B 三个位置的动作边界划清楚。2.1 入口A、中转盲端S、出口B一条规则一张操作表先翻译物理规则。入口 A 是车厢的出发队列车厢按入栈序列 a1、a2、……、an 依次到达 A这个序列是题目给定的车厢必须按这个顺序一辆一辆出现在调度员面前不能跳号。中转盲端 S 是一个缓冲轨道容量为 m车厢进入 S 后只能按先进后出的方式离开不能调头、不能超车。出口 B 是车厢最终驶出的方向目标是把车厢按 1 到 n 的升序全部送出。把这三条规则列成操作表对应的数据结构关系就非常清楚铁道规则数据结构语义车厢从 A 进入 S元素从输入序列头部入栈车厢在 S 中驻留元素停留在栈中车厢从 S 驶向 B元素出栈车厢从 A 直接驶向 B元素不经过栈直接消耗S 容量为 m栈的最大深度为 mS 中不能调头/超车栈内元素只能按后进先出离开这里最容易忽略的是“从 A 直接驶向 B”这条路径。很多实现只写了入栈和出栈两个动作遇到当前需要出 B 的车厢恰好就在 A 的最前端时仍然先让它进 S 再立刻出栈这在 m 足够大时结果一致但一旦 m 很小甚至等于 0行为就会完全错误。正确的模型应当把“直达”作为一个独立的合法动作处理它不消耗栈容量。2.2 容量 m 不是一个普通限制它直接改变问题的判定结果经典的车厢调度问题通常只问“给定入栈序列某个出栈序列是否合法”栈容量默认无限。本题多了容量上限 m这不是在原有问题上多一个判断条件而是会让原本合法的序列直接失效。举例说明入栈序列为 3 2 1m3目标出栈序列为 1 2 3。推演过程是3 进 S2 进 S1 进 S此时 S 中从栈底到栈顶为 3、2、1。要出 1 只需弹出栈顶 1然后依次弹出 2、3合法。但如果把容量改成 m1同一个入栈序列就不合法3 进 S 后 S 已满2 无法进 S而当前目标是 12 被堵在 A 端无法处理直接失败。从这个例子能看到两层含义。第一容量约束在入栈动作发生时检查不在出栈时检查因为出栈只会减少占用。第二m 的取值存在两个退化分界点m0 时只有入栈序列本身就是 1..n 才能成功因为任何需要缓冲重排的操作都不可行mn 时容量不构成限制问题退化为经典无容量上限的栈匹配。实际写代码时这两个边界很多人没有显式处理导致 m0 时直接数组越界或误判。2.3 和经典出栈序列校验题的对照同一套代码换个方向经典出栈序列校验题的常见形式是入栈序列固定为 1、2、……、n给定一个出栈序列问是否合法。本题形式正好反过来入栈序列由题目给定出栈序列固定为 1、2、……、n。这两种形式在算法层面完全对称。判断一个序列能否通过栈得到另一个序列标准做法是以目标出栈序列为基准扫描每次想要得到目标中的当前元素时先看栈顶是否等于它等于就弹出不等于就从入栈序列中继续取元素压栈直到栈顶等于目标或入栈序列耗尽。目标序列和入栈序列谁是“给定的”、谁是“1..n”并不改变这个贪心校验流程。理解这一点很重要。它意味着你不需要为本题单独发明新算法只需要把经典栈校验函数做成参数化的形式入栈序列传题目给的序列目标出栈序列传 1..n 的升序数组即可。后面章节里的代码就是这个思路的直接落地。3. 核心算法与 C 实现O(n) 的栈模拟与两个版本代码原理清楚了代码就只是把操作表逐条翻译。这一章给出可以在本地直接编译运行的完整 C 实现并解释每一步为什么这么写。3.1 为什么用数组模拟栈而不是 STL stack这道题栈的最大深度是 mn 最大可能到 10^6 量级用 STL 的 std::stack 也能写但我建议用数组模拟。原因有三个第一数组支持随机访问栈顶以下的元素调试时可以一次打印整个 S 的状态stl 容器想看栈底元素必须临时拷出来第二容量上限 m 是显式参数用数组可以在压栈前直接通过下标判断 top1 是否超过 m避免先 push 再检查 size 的图形第三性能上数组操作没有函数调用和动态分配开销在 n10^6 时差距虽然不大但算法竞赛环境里能省则省。数组大小的选择有讲究。栈的深度不可能超过 n因为总共只有 n 个元素所以数组按 MAXN 开就够了不需要按 m 开。m 可能是一个极大的数如果写成 int stack[m] 这种变长数组m 超过栈内存限制时直接崩溃这是一个非常隐蔽的坑。3.2 完整 check 函数先走直达、再看栈顶、最后压栈下面这份代码是完整版显式处理了“从 A 直接驶向 B”这条路径也是我推荐直接拿去用的版本#include cstdio const int MAXN 1000005; int n, m; int inSeq[MAXN]; // 入栈序列车厢在入口A的排队顺序 int stack[MAXN]; // 模拟中转盲端S数组充当栈 bool check() { int top -1; // 栈顶指针-1 表示空栈 int cur 0; // inSeq 的读取指针指向下一个到达 A 的车厢 for (int out 1; out n; out) { // 情况1入口A最前面的车厢正好等于当前目标直接 A-B if (cur n inSeq[cur] out) { cur; continue; } // 情况2中转盲端S的栈顶正好等于当前目标从 S-B 弹出 if (top 0 stack[top] out) { --top; continue; } // 情况3都不满足只能从 A 端继续取车厢压入 S // 直到找到等于 out 的车厢或者把入栈序列读完 bool hit false; while (cur n) { int x inSeq[cur]; if (x out) { // 当前 A 端车厢就是目标不占 S 容量直接驶向 B hit true; break; } // x 不是目标必须先压入 S此时才检查容量 if (top 1 m) { return false; // S 已满且栈顶不是 out无法继续 } stack[top] x; } if (!hit) { return false; // 入栈序列读完也没找到 out失败 } } return true; }这段代码的核心逻辑按照“直达 - 出栈 - 入栈”的优先级顺序执行。先检查直达是因为它不消耗栈容量且优先级最高——当 A 端车厢就是目标时没有理由让它先进 S 占位置。再检查栈顶是因为出栈是最直接的动作。两者都不满足时才需要从 A 端继续读入并压栈。压栈动作里有一个容易写错的顺序要先读取车厢 x判断它是不是目标再检查容量并压栈。如果先把容量检查写在读取前面就会犯“栈满了但下一个要读的车厢恰好是目标可以直达却判失败”的逻辑错误。这段代码里容量检查的位置是刻意的章节后面会专门展开讲这个坑。3.3 main 函数与多组输入的读取方式题目描述没有限制输入格式比赛和课程设计里最常见的格式是每组数据第一行两个整数 n、m第二行 n 个整数表示入栈序列读到文件结束符为止。main 函数可以这样写int main() { while (scanf(%d%d, n, m) 2) { for (int i 0; i n; i) { scanf(%d, inSeq[i]); } puts(check() ? YES : NO); } return 0; }多组输入用 while 循环包住返回值为 2 表示成功读入两个整数。每组数据读完后check 函数内部的 top 和 cur 都是局部变量自动重置不需要额外清零。inSeq 在每组数据里重新覆盖也不会残留上一组的数据。要注意的是 puts 输出会自动带换行比 printf(%s\n, ...) 少一次格式化解析在高频多组数据场景下更稳妥。如果题目要求输出小写字母把 YES 改成 yes 即可逻辑不变。3.4 时间复杂度和空间复杂度整体时间复杂度是 O(n)。表面上有一个 for 套 while 的结构但 while 内部每执行一次要么消耗一个入栈序列元素cur 加 1要么成功弹出一个栈元素top 减 1cur 最多从 0 走到 n元素弹出也最多 n 次所以总操作次数是 2n 量级不是 O(n^2)。空间复杂度方面额外的存储只有 inSeq 和 stack 两个数组长度都是 n总空间 O(n)。如果题目给的 m 小于 n实际的栈占用不会超过 m但因为 m 可能不是固定小值统一按 n 开数组最简单、最安全。4. 常见问题与避坑容量 m0、先满后取值等四个翻车点这道题代码很短真正让人卡住的往往不是主流程而是几个边界条件的处理。下面这五条都是实际调试时会遇到的现象每一条都按“现象 - 原因 - 解决”说明。4.1 容量 m0合法序列被直接误判为 false现象m0入栈序列恰好是 1 2 3按题意所有车厢可以直接从 A 驶向 B答案应为 YES。但程序输出 NO有的版本甚至直接数组越界崩溃。原因两个层面的问题。第一不少实现把栈数组开成 stack[m]m0 时数组长度为 0任何对 stack[0] 的访问都是越界。第二即使数组按 MAXN 开如果压栈动作没有先判断“当前 A 端车厢是否等于目标”就直接检查容量那么 top10 在 m0 时恒成立任何需要进 S 的动作都会被拒绝导致合法序列被错杀。解决把 A-B 直达分支放在最前面并且压栈前必须先读取车厢值命中目标则直接消耗。修改后的顺序是先走直达再走栈顶弹出最后才进入“读取 判断 压栈”流程。这样 m0 时只要每个目标车厢都在入栈序列的当前头部就可以一路直达正确输出 YES。4.2 先检查容量再读取车厢把能直达的车厢挡在门外现象m1入栈序列 2 1目标 1 2。正确推演是2 入 S1 直达 B2 从 S 出结果为 YES。但代码在 while 里写成先判断 top1m 再读取 inSeq[cur]那么当目标 1 出现时S 里已有 2、容量已满直接返回 false输出 NO。原因容量检查的位置不对。容量满只表示“不能再压入新的非目标车厢”并不表示“当前 A 端车厢不能直达 B”。如果先把容量检查放在读取之前就会把直达这个不占容量的动作误判为压栈动作从而提前判死。解决把读取车厢放在容量检查之前先看读到的 x 是不是当前目标是则处理完毕不是才检查容量并压栈。这个顺序不能颠倒否则 m 很小时会大量误判。4.3 把目标变量写进 for 循环里跳过目标导致漏判现象某些用例输出和预期相反且只在特定序列下出现。比如入栈序列 2 3 1m3目标 1 2 3正确结果是 YES但程序输出 NO。原因不少初学者会把 while 循环写成“不断压栈直到栈顶等于 out”然后在 while 内部用 out 推进目标外层 for 循环又执行一次 out导致目标被跳过。比如目标 1 处理到一半时内部推进到 2外层循环又将目标推到 3最终漏掉了 2 的检测。解决目标变量 out 只在外层 for 循环里 所有 while 循环都只负责“把栈顶调整为 out”这一件事。while 结束后要么栈顶等于 out要么已经命中直达车厢要么返回 false确认当前 out 已处理完毕后再让外层 for 推进。4.4 入栈序列不是排列或有重复编号while 循环变成死循环现象程序在某些数据上运行时间异常长甚至卡死。一种情况是入栈序列包含重复值比如 inSeq 为 1 1 2目标 1 2程序始终找不到第二个 1cur 读完仍然找不到目标理论上应该返回 false但有些实现会在 cur 越界后继续循环造成死循环。原因题目本身没有明确保证入栈序列是 1 到 n 的全排列。如果数据里缺号或重复目标值 out 可能永远无法命中此时 while 依靠 curn 作为终止条件若不检查 cur 越界就会越界访问。解决在 while 循环条件里严格带上 curn循环体里每读一个数都必须让 cur 前进一旦 curn 还没命中目标立即返回 false。更稳妥的做法是在 check 前先对 inSeq 做一次全排列合法性校验统计 1 到 n 每个数是否恰好出现一次不合法直接输出 NO。4.5 m 大于 n 时按 m 开数组内存栈溢出现象n100000m1000000000如果写 int stack[m] 作为局部变量程序在函数入口直接栈溢出崩溃写成全局变量则数组占用 4GB直接内存超限。原因m 是容量上限不是实际栈大小。实际栈内最多同时驻留 n 个元素栈数组只需要 n 的容量。解决所有数组一律按 MAXN 开栈深度用 top1 与 m 比较来控制而不是用数组本身的大小来控制。这道题的约束里 m 可能远大于 n也可能等于 0只有按 n 开数组、按 m 做逻辑判断才能同时覆盖两个极端。5. 从判断到实战变式输出调度方案、参数化目标序列与超大 n能输出 YES/NO 只是第一步。把这个栈模拟改造成通用工具能覆盖更多题型也能应对更大规模的数据。5.1 从 YES/NO 到调度方案给每个操作打标记很多应用场景不只是判断可行性还要给出具体的调度动作。比如课程设计要求输出每一步是“从 A 入 S”“从 S 出 B”还是“从 A 直达 B”。在 check 函数里加一个操作序列记录即可#include cstdio #include string const int MAXN 1000005; int n, m; int inSeq[MAXN]; int stack[MAXN]; std::string ops; bool checkWithOps() { int top -1; int cur 0; ops.clear(); for (int out 1; out n; out) { if (cur n inSeq[cur] out) { cur; ops A-B ; continue; } if (top 0 stack[top] out) { --top; ops S-B ; continue; } bool hit false; while (cur n) { int x inSeq[cur]; if (x out) { hit true; ops A-B ; break; } if (top 1 m) return false; stack[top] x; ops A-S ; } if (!hit) return false; } return true; }操作序列的长度最多是 2n入栈动作和出栈动作最多各 n 次直达动作最多 n 次。每一次压入 S 的动作必然对应后续某一次从 S 弹出的动作所以如果输出 ops 后可以直接验证A-S 和 S-B 的数量相等A-B 的数量等于未经过 S 的车厢数。这个性质可以用来做自检。5.2 目标序列参数化一份代码覆盖所有出栈顺序校验题把目标出栈序列从硬编码的 1..n 改成参数这份代码就可以同时解决“给定入栈序列和目标出栈序列栈容量为 m是否合法”这一类问题。bool canArrange(int* inSeq, int* target, int n, int m) { int stack[MAXN]; int top -1; int cur 0; for (int idx 0; idx n; idx) { int out target[idx]; if (cur n inSeq[cur] out) { cur; continue; } if (top 0 stack[top] out) { --top; continue; } bool hit false; while (cur n) { int x inSeq[cur]; if (x out) { hit true; break; } if (top 1 m) return false; stack[top] x; } if (!hit) return false; } return true; }调用时如果目标序列是 1..n就构造一个 target 数组填入 1 到 n如果题目反过来比如 UVa 514 那道经典铁轨题入栈序列固定 1..n出栈序列题目给定就把入栈序列填 1..n目标序列填题目给定序列。两种题型共用同一个函数只需要调整两个实参的位置这是这个模型最大的复用价值。5.3 当 n 到 10^6常量区数组、循环不变式与容量微调数据规模变大时这段代码需要做三个工程上的调整。第一所有大数组都放全局区不要放在 main 或 check 内部否则栈内存不够。全局区的 .bss 段可以轻松容纳 10^6 个 int也就是大约 4MB没有问题。第二输入输出用 scanf/puts 而不是 cin/cout 加 endl因为后者在 10^6 量级时同步开销明显实测可能慢 3 到 5 倍。第三容量检查统一写成 top 1 m不要和栈顶指针的边界条件混在一起避免把“栈空”和“栈满”两种状态搞混。还有一个适合写注释的循环不变式在 for 循环每次迭代开始时栈中所有元素从栈底到栈顶都是入栈序列中已经被读取过、但尚未从 B 端输出的车厢。维护这个不变式调试时只需要打印 top 和 cur 两个变量就能快速定位是读入逻辑还是弹出逻辑出错。实际调试这类栈模拟题我见过太多人盯着整个数组看其实关键状态只有两个指针cur 指向 A 端下一个待入车厢top 指向 S 内部栈顶。6. 验证与对拍用手工样例和随机数据确认代码正确代码写完验证不能只靠一两组样例。手工推演几组边界用例再用随机对拍做批量验证是确认这类栈模拟题不出错的最快路径。手工样例可以先覆盖四个方向能直达、需要缓冲、容量受限、容量为 0。下面这组测试用表格列出第一行是入栈序列S 容量为 m预期输出 YES/NO入栈序列m预期理由3 2 13YES全部压入 S 后从栈顶依次弹出 1、2、33 2 11NO3 入 S 后栈满2 和 1 无法继续处理1 2 30YES每个车厢都直接从 A 驶向 B1 3 20NO需要 2 先入 S 等待但容量为 02 1 31YES2 入 S1 直达2 出栈3 直达2 4 1 33NO2、4 入栈后栈满1 直达后 2 被 4 挡住手工样例通过后再用随机对拍验证正确性。对拍需要三样东西一个随机数据生成器、一个暴力程序、一个比对脚本。生成器用 Python 写最方便import random n random.randint(1, 8) m random.randint(0, n 2) perm list(range(1, n 1)) random.shuffle(perm) print(n, m) print(*perm)暴力程序则用 DFS 枚举所有可能的操作序列状态包括当前读到入栈序列的位置、当前 S 中的车厢用元组表示、当前已经输出的车厢数。由于操作只有 A-B、A-S、S-B 三种n 不超过 8 时状态量完全可控import sys def brute(in_seq, m, target): n len(in_seq) seen set() def dfs(cur, stack, out_cnt): if out_cnt n: return True key (cur, tuple(stack), out_cnt) if key in seen: return False seen.add(key) # 直达 if cur n and in_seq[cur] target[out_cnt]: if dfs(cur 1, stack, out_cnt 1): return True # 入栈 if cur n and len(stack) m: stack.append(in_seq[cur]) if dfs(cur 1, stack, out_cnt): return True stack.pop() # 出栈 if stack and stack[-1] target[out_cnt]: x stack.pop() if dfs(cur, stack, out_cnt 1): return True stack.append(x) return False return dfs(0, [], 0)最后用 bash 脚本循环跑 1000 组生成器产生输入C 程序输出结果暴力程序输出结果diff 比对#!/bin/bash for i in $(seq 1 1000); do python3 gen.py in.txt ./pa2 in.txt out1.txt python3 brute.py in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo case $i failed cat in.txt break fi done这套对拍流程跑完之后我再没有在容量判断的顺序上翻过车。从那以后每次写这类栈模拟题我都强制先走一遍“手工边界 1000 组对拍”确认两个指针的推进逻辑在最小用例和最大用例下都成立。这个习惯帮我省下过不少调错时间希望也能帮到你。本文还有配套的精品资源点击获取
