简介：围绕“列车进站”车厢调度问题整理的课程实验资料，面向学习数据结构、栈与队列的本科生及编程初学者。内容以“丁”字形铁路调度系统为背景，要求对任意排列的 n 节车厢借助辅助铁轨完成次序调整，使列车按 1～n 顺序出站，适合用来练习栈的先进后出、队列的先进先出以及模拟调度过程。压缩包共 9 个文件，包含 C++ 源文件、多个头文件、Dev-C++ 工程文件、Makefile.win，以及可执行文件与目标文件，整体约 128KB，可直接在本地编译运行并对照调试。已有 1942 人学习下载。资料提供完整的实验实现框架与链栈、链队列等基础结构，读者可据此理解辅助铁轨的入栈出栈规则、状态转移和输出序列判定，并借助工程配置快速复现实验、修改测试数据，完成课程实验或算法练习。

1. 站台只有一条股道：列车进站为什么是栈与队列最省事的练手场

很多课设题目名字起得温和，实际动手才发现边界条件一大堆。「列车进站」就是典型：站台只有一条股道，两端封死一头，先进去的车被堵在最里面，最后到的车反而先开走，这正是栈的后进先出；站外等候线先到先排、先排先放行，是队列的先进先出。这个资源把栈和队列塞进同一个调度场景里，让两种结构的差别肉眼可见。适合正在做数据结构课设、想把顺序栈和循环队列一次写对的人，也适合已经会写 push/pop、但一遇到“站台满了还要不要进站”“发车次序根本凑不出来”就卡住的人。它解决的正是“结构会背、场景不会用”这个中间地带。

2. 把站台和候车线映射成结构体：顺序栈与循环队列的选型与边界

这一章先把现实物件翻译成数据结构，再谈具体写法。概念不清楚就上手写代码，最后往往会在“栈顶指针到底指哪儿”这种地方反复返工。选型不是拍脑袋，每种结构都有它在这个场景下的具体代价。

2.1 站台是栈、候车线是队列：模型到内存的一一对应

建模的第一步是把实体、元素和操作分离。这个资源里只有三类东西：列车、站台、候车线。列车用整数编号表示，编号同时充当车次标识和出栈顺序的比较依据；站台是一条只能从同一端进出的股道，映射成栈；候车线是一端进、另一端出，映射成队列。调度过程就是在这两个容器之间搬数据，再加上一个“发车目标序列”作为外部约束。

映射关系可以整理成下面这张表，写代码前先在纸上画一遍，比对着函数原型硬猜要快得多：

一个容易被忽略的点：站台容量是硬约束。股道长度有限，站台满了以后即使候车线还有车，也不能再放进来了。很多实现把这一步写成“数组够大就无限进站”，跑小数据没事，一上大样本立刻露馅。常见做法是给站台设一个MAX_TRAIN宏，判满逻辑写进stack_push里，失败返回-1而不是静默扩容。课设要演示的恰恰是“站台满了怎么办”，静默扩容等于把这个考点删掉了。

选型上，顺序栈比链栈更合适：容量固定、没有频繁扩容、调试时可以直接gdb看数组内容，出错点少。队列同理，循环队列在一段固定长度上反复入队出队，不会像链队列那样每来一趟车就malloc一次，跑几千次调度也不会产生内存碎片。代价是循环队列的判空判满要多写一行取模，这个代价在后文 2.3 里专门讲。

2.2 顺序栈的 top 约定：指向栈顶元素还是下一个空位

栈只有两个变量：一个数组、一个top。翻车点几乎全部集中在top的语义上。两种写法都正确，但绝对不能混用：

这个资源采用的是第一种，理由是判空写成top == -1比top == 0更容易在一堆if里一眼认出来，而且data[top]可以直接读栈顶，不用减一。定好之后，所有函数必须严格按这套语义写，包括那个最容易被随手写错的取栈顶：

#define MAX_TRAIN 64 typedef struct { int data[MAX_TRAIN]; /* 车厢编号，0 号不用作有效车次 */ int top; /* 指向栈顶元素；空栈约定为 -1 */ } SeqStack; /* 初始化：只做一件事，把 top 拉回空栈约定值 */ void stack_init(SeqStack *s) { s->top = -1; } int stack_empty(const SeqStack *s) { return s->top == -1; /* 空栈判据，与约定严格一致 */ } int stack_full(const SeqStack *s) { return s->top == MAX_TRAIN - 1; /* 数组下标上界，不是 MAX_TRAIN */ }

stack_full里MAX_TRAIN - 1这个减一是边界感的来源。容量为MAX_TRAIN的数组，合法下标是0到MAX_TRAIN - 1，如果写成top == MAX_TRAIN，那么top到MAX_TRAIN - 1时判满返回假，下一次++top直接把top推到MAX_TRAIN，写入就越界了。这种越界在本地跑十条数据时往往不报错，因为刚好踩到结构体后面的填充字节，一换编译器或者加上-fsanitize=address立刻炸出来。

提示：top的约定一旦选定，就在结构体定义旁边写一行注释钉死，后面所有函数都照着这一行写，不要凭记忆。

2.3 循环队列判空判满：牺牲一个单元，还是加一个计数器

循环队列的麻烦在于队空和队满的条件长得一样。head == tail既可以解释成“一个元素都没有”，也可以解释成“转了一整圈刚好装满”。三种常见解法各有取舍：

这个资源用第一种。原因很直接：课设的评判标准是逻辑清晰、边界正确，牺牲一个单元换来的是判空判满两个条件永远不模糊，调试时看head和tail两个数就能推断状态。代价是数组要开MAX_TRAIN + 1，实际能排的列车数还是MAX_TRAIN。

#define QCAP (MAX_TRAIN + 1) /* 多开一个单元，专门用来区分队空队满 */ typedef struct { int data[QCAP]; int head; /* 队首下标，指向当前队首元素 */ int tail; /* 队尾下标，指向下一个可写入位置 */ } CircQueue; void queue_init(CircQueue *q) { q->head = 0; q->tail = 0; /* 初始状态队空：head == tail */ } int queue_empty(const CircQueue *q) { return q->head == q->tail; } int queue_full(const CircQueue *q) { /* tail 再走一步就撞上 head，说明只剩那个被牺牲的空单元 */ return (q->tail + 1) % QCAP == q->head; } int queue_length(const CircQueue *q) { /* 先加 QCAP 再取模，避免 tail - head 出现负数 */ return (q->tail - q->head + QCAP) % QCAP; }

queue_length这一行值得单独说：tail - head在tail已经绕回数组前部时会变成负数，C 语言的%对负数取模结果仍为负，直接拿去做循环上界就是灾难。先加一个模数再取模，是循环队列里最常用的一句后悔药。凡是涉及两个环形下标的差值，都按这个写法补一遍，别指望编译器替你兜底。

3. 从骨架到跑通：一次完整进站调度的实现步骤与参数

结构定义好之后，接下来的活是把四个原子操作写对，再把它们串成一个不会死循环的主循环。这一步的关键不在代码量，而在优先级顺序：先发车还是先进站，直接决定模拟结果是成功还是误判卡死。

3.1 结构体定义与初始化：容量、编号、返回值约定

动手前先把三条约定写死，后面所有函数都遵守：

• 车次编号从 1 开始，0保留为“无效车次”，这样打印日志时看到 0 就知道是初始化残留。
• 所有可能失败的操作统一返回int：0成功，-1失败。不要混用1/0和true/false，一个项目里两种风格并存，最后一定会有人把成功当失败。
• 容量统一由MAX_TRAIN控制，栈和队列都引用它，改容量只改一处。

/* 站台（栈）+ 候车线（队列）的完整状态，打包成一个结构便于整体传递 */ typedef struct { SeqStack platform; /* 站台：后进先出 */ CircQueue waiting; /* 候车线：先进先出 */ int departed; /* 已发车数量，用于和 {目标序列} 的 done 对齐 */ } Station;

把两个容器打包进Station，好处是主循环的签名短，dispatch(&st, target, n)一个参数搞定，调试时打印st就能看到全貌。代价是结构体在栈上占的空间变大（64 + 65个int，约 516 字节），这个量级完全不用担心，别为了省这点内存拆成三个全局变量，全局变量一多，重入和单元测试都做不了。

3.2 四个原子操作：入栈、出栈、入队、出队

四个函数写法固定，重点在失败路径的处理。入栈失败要能区分“站台满”，出栈失败要能区分“站台空”，调用方才能给出有意义的日志。

int stack_push(SeqStack *s, int id) { if (stack_full(s)) return -1; /* 站台占满，拒绝进入 */ s->data[++s->top] = id; /* 先自增再写入，配合 top 指向栈顶的约定 */ return 0; } int stack_pop(SeqStack *s, int *out) { if (stack_empty(s)) return -1; /* 空站不能发车 */ *out = s->data[s->top--]; /* 先取值再自减 */ return 0; } int queue_push(CircQueue *q, int id) { if (queue_full(q)) return -1; /* 候车线排满 */ q->data[q->tail] = id; q->tail = (q->tail + 1) % QCAP; /* 尾指针环形前进 */ return 0; } int queue_pop(CircQueue *q, int *out) { if (queue_empty(q)) return -1; *out = q->data[q->head]; q->head = (q->head + 1) % QCAP; /* 头指针环形前进 */ return 0; }

参数说明：out用指针传出，是为了让返回值专门表示成败，避免“返回值既当数据又当状态”这种经典混用。如果车次编号本身可能为0，就必须走指针传出，否则调用方没法区分“取出的是 0 号车”和“出队失败”。这份实现里编号从 1 起，理论上可以用返回值，但保留指针写法更稳妥，后面扩展到字符串车次也不用改接口。

还有一个隐含约定：stack_pop传NULL会崩。防御性写法是在函数开头加if (out == NULL) return -1;，两行代码，能在调试期省下不少定位时间。

3.3 调度主循环：先发车还是先进站

主循环是整份代码的核心，也是最容易写成死循环的地方。逻辑骨架只有三步，但顺序不能乱：

1. 如果站台顶端就是下一趟该发的车，立刻发车，然后回到第 1 步重新判断。
2. 否则，如果候车线非空且站台未满，放队首列车进站，然后回到第 1 步。
3. 两步都做不了，说明当前状态凑不出目标序列，判定卡死。

/* 按目标发车序列 target 调度，成功返回 0，卡死返回 -1 */ int dispatch(Station *st, const int target[], int n) { int done = 0; /* 已发出的列车数，同时是 target 的下标 */ while (done < n) { int id; /* 步骤 1：能发就发。这一步必须放在最前面，理由见下方说明 */ if (!stack_empty(&st->platform) && st->platform.data[st->platform.top] == target[done]) { stack_pop(&st->platform, &id); printf("[发车] %d\n", id); done++; continue; /* 发完立刻重判，不急着进站 */ } /* 步骤 2：发不出去，就往站台里放车 */ if (!queue_empty(&st->waiting) && !stack_full(&st->platform)) { queue_pop(&st->waiting, &id); stack_push(&st->platform, id); printf("[进站] %d\n", id); continue; } /* 步骤 3：既发不了也进不了，卡死，把现场打出来 */ printf("[卡死] 目标车次 %d，站台顶 %d，候车线长度 %d\n", target[done], stack_empty(&st->platform) ? -1 : st->platform.data[st->platform.top], queue_length(&st->waiting)); return -1; } return 0; }

“先发车”这条优先级不是风格问题，而是正确性问题。举例：候车线是[1, 2]，目标发车序列是[1, 2]，站台容量足够。如果先把两趟车都放进站台，站台从底到顶变成1, 2，栈顶是 2，而当前该发的是 1，发不出去，站台又满了，主循环直接判定卡死；但实际这个序列完全可行——1 进站后立刻发走，2 再进站发走。反过来的优先级（能发就发）不会出现这种误判。这条经验在缓冲轨、车厢重排这类题里通用：只要栈顶能满足当前需求，就不要往里塞新东西。

continue的作用也值得说一句。发完车后直接跳回循环开头重新判断，而不是继续往下走去执行进站，这样保证每一轮循环最多做一个动作，日志顺序和真实调度顺序严格一致。如果去掉continue，一轮里既发车又进站，打印出来看着没问题，但对拍时状态序列对不上，排查起来非常费劲。

4. 发车次序能不能实现：出栈序列合法性判定与对拍

调度跑通以后，下一个问题自然浮出来：给定进站顺序1..n，某个发车顺序到底可不可行？这不是靠眼睛看能解决的，需要写一个判定器，而且要能证明判定器本身是对的。

4.1 判定原理：一遍扫描 + 贪心入栈

判定算法只有一句话：按目标序列从左到右扫描，对每个目标车次，先把所有还没进站且编号不大于它的车依次压栈，然后检查栈顶是不是它。是就弹出，继续下一个；不是就说明这个次序不可能出现，直接返回不可行。

为什么贪心是对的？因为进站顺序固定为1..n，当目标要求某个车次x时，比x小的车次只有两种去处：已经在栈里，或者还没进来。如果还没进来，那它必须在x之前进来（否则以后更没机会），所以“一路压到x”是唯一选择，没有分支可挑。这个论证在纸上写两行就够，但它决定了算法复杂度是O(n)而不是指数级搜索。

/* 判断 target 是否是 1..n 的一个合法出栈序列，合法返回 1 */ int is_valid_pop_seq(const int target[], int n) { SeqStack s; int next_in = 1; /* 下一趟待进站的车次，固定从 1 开始 */ stack_init(&s); for (int i = 0; i < n; i++) { int x = target[i]; if (x < 1 || x > n) return 0; /* 越界车次直接判非法 */ /* 把 1..x 中还没进站的全部压进去 */ while (next_in <= x) { if (stack_push(&s, next_in) != 0) return 0; next_in++; } /* 此时栈顶必须是 x，否则这个次序永远凑不出来 */ if (stack_empty(&s) || s.data[s.top] != x) return 0; int dropped; stack_pop(&s, &dropped); /* 弹出并丢弃，只关心状态推进 */ } return 1; }

参数说明：target是长度为n的目标序列，元素取值范围1..n，函数内部做了越界检查，所以调用方不用重复校验。next_in是单调递增的，整个函数里它只增不减，所以总压栈次数不超过n，复杂度O(n)，空间是栈的O(n)。

4.2 实现与自证：用卡特兰数给判定器做对拍

判定器写完后，怎么确信它没写错？靠肉眼看几个例子不够，样本一多必然漏。这里有个很实用的自证手段：n个车次的合法出栈序列总数恰好是第n个卡特兰数C(2n, n) / (n + 1)。用暴力枚举所有排列，过滤出判定器认为合法的那些，数一数，和卡特兰数比对，两边一致就说明判定器在n这个规模上没有系统性偏差。

from itertools import permutations from math import comb def valid(target): """与 C 版本同一套逻辑，用来做交叉验证""" stack, nxt = [], 1 for x in target: while nxt <= x: stack.append(nxt) nxt += 1 if not stack or stack[-1] != x: return False stack.pop() return True for n in range(1, 8): cnt = sum(1 for p in permutations(range(1, n + 1)) if valid(p)) catalan = comb(2 * n, n) // (n + 1) flag = "OK" if cnt == catalan else "MISMATCH" print(f"n={n} 合法序列={cnt} 卡特兰={catalan} {flag}")

这段脚本不需要优化，n = 7时是5040个排列，秒出结果，n = 8也只要几秒。跑出来n从 1 到 7 全部OK，判定器的基本正确性就有了底。再挑几个手工能算的例子做定点检查，比如n = 3时合法的只有123、132、213、231、321五个，312不合法——因为 3 先出栈意味着 1、2 都压在栈里，栈顶是 2，不可能先出 3。这种“手算一个、脚本跑一批”的组合，比单靠任何一种都可靠。

注意：对拍脚本和 C 实现要分两处写，不要复制粘贴改语言。两份独立实现同时错成一样是小概率事件，复制粘贴则会让错误同步，对拍就失去意义了。

5. 避坑与排查：五个让我返工的现场记录

下面五条都是实际调试时踩过的，按“现象 → 原因 → 解决”记，遇到同类问题可以直接对照。

5.1 下标与边界：站台顶取不出、队满后静默覆盖

现象一：站台里明明有车，发车函数返回失败，日志里一个元素都没发出去。

原因是top的约定混用。初始化写的是top = -1（指向栈顶元素的约定），但stack_empty里写成了top == 0，于是空栈判断永远为假，而取栈顶又用data[top - 1]（指向下一个空位的约定），top = -1时直接读到data[-2]。同一份代码里两种约定并存，症状会随数据规模飘忽不定。解决方式是把约定写在结构体注释里，并且只写一个stack_top(s)内联函数负责取顶，其他地方一律调它，不直接摸data[top]。

现象二：候车线排到第MAX_TRAIN趟时，最早的那趟车无声无息消失了。

原因是判满条件写成了tail == head，和判空一模一样。队满时queue_push认为还能写，覆盖掉head指向的元素，而head没动，看起来就像凭空少了一趟车。解决方式是严格按 2.3 的“牺牲一个单元”写法，把(tail + 1) % QCAP == head作为判满条件，并且在queue_push失败时打印当前head/tail/length三个值，一眼就能看出是判满误判还是容量确实不够。

5.2 流程与状态：调度死循环、打印顺序和实际执行错位

现象三：程序不崩，但卡在某一行日志之后再无输出，CPU 占用拉满。

原因是主循环里某个分支执行了操作却没有continue，一轮内反复进出同一个状态而不推进done。典型写法是发车之后忘了continue，直接落到进站分支，进站又把站台填回去，下一轮再发同一趟车——done加了一次，但站台状态被还原，形成有限状态机里的自环。解决方式有两条：一是每个成功分支后强制continue；二是在循环末尾加一个“本轮是否有动作”的布尔量，如果一整轮什么都没做还done < n，直接判定卡死退出，绝不无限重试。

现象四：日志顺序看着完全正确，但对拍脚本报状态序列不一致。

原因是先打印再操作，或者先操作再打印，两种情况混在一份代码里。比如发车分支里先printf再stack_pop，而进站分支里先queue_pop再printf，日志的时间点和状态变化点错位，人眼看不出问题，机器一比就露馅。解决方式是统一约定“先改状态、再打印、最后continue”，并且打印时把关键状态一起输出，例如[发车] id=3 站台剩余=2 已发=5，这样日志本身就是一份可断言的状态快照。

5.3 输入与接口：车厢号读串、返回值被忽略

现象五：输入序列里有换行或多余空格时，后面所有车次全变成 0 或者重复值。

原因是scanf("%d", &x)的返回值没检查，遇到非数字字符时读取失败，x保持上一次的旧值，循环继续跑，于是同一趟车被反复压进站台。解决方式是写成while (scanf("%d", &x) == 1) { ... }，把返回值当作循环条件；如果数据来自一行逗号分隔的编号，就换成strtok切分后逐个strtol并检查endptr，别指望格式错误能自动被发现。接口层面的同类问题是：stack_push返回-1表示站台满，但调用方写成了stack_push(...)后直接往下走，满站被当成成功，后面所有状态全错。所有带返回值的操作，要么处理，要么用assert卡住，中间态最危险。

6. 让它能自证：随机对拍、不变量断言和一份可复现的记录

代码跑通只是起点，能证明它一直对，才算把这份资源用透。我后来给这个调度模拟加了三层自证，成本都不高，但返工率明显下降。

第一层是随机对拍。用脚本生成随机的进站序列和随机目标序列，跑一遍dispatch，再把dispatch的每一步动作序列喂给一个独立的 Python 状态机重放，两边的done、站台内容、候车线内容在每个时间点都必须一致。Python 那份实现故意写得笨一点，用list直接当栈和队列，不做任何环形下标优化，越笨越好核对。两边同时对错的概率远低于单边出错。

第二层是不变量断言，挂在主循环每轮开头。这个场景下值得断言的条件不多，但每一条都能挡住一类 bug：

这些断言用assert写就行，调试版本打开、发布版本-DNDEBUG关掉，代价几乎为零。关键是断言失败时要打印现场，光一个Assertion failed什么也说明不了。我一般写一个dump_station(st)函数，把栈从底到顶、队列从头到尾、done和当前目标车次一次性打出来，断言失败时先调它。

第三层是留一份可复现的记录。每次修完 bug，把触发问题的最小输入存成一个文本文件，命名成case_站台满_01.txt之类，配一行期望输出。时间一长这就是自己的回归测试集，改一处逻辑跑一遍全部用例，几十秒的事。比起“改完再手输一遍试试”，这套东西在改第三个 bug 的时候就能回本。

还有一个进阶方向值得一试：把单股道扩展成多条缓冲轨。经典的车厢重排问题里，站台不止一条，需要判断用k条缓冲轨能否完成指定重排，这时候单纯的后进先出不够用，要在“放哪条轨”上做搜索。我一般先写一个k = 1的退化版本，确认基础调度和第 4 章的判定器都对得上，再逐步放开k，每一步都用前面的对拍脚本兜底，绝不允许“一次改到位”。

血泪经验是：这类调度模拟的 bug，八成不在算法，而在下标约定、判空判满和循环优先级这三件小事上。从那以后我每次写站台、缓冲轨、括号匹配这类栈队列题，都强制先把不变量写成assert挂在主循环里，再开始调业务逻辑，宁可多写二十行断言，也不想再对着满屏日志猜栈顶到底指向谁。希望帮到你。

本文还有配套的精品资源，点击获取