简介一份围绕“丁”字型铁路调度系统的编程实验资源面向正在学习数据结构中栈与队列应用的本科生或自学者解决n节车厢按给定次序进入后利用辅助铁轨这一后进先出结构进行调整最终以1至n顺序出站的问题。例如5节车厢以5、3、1、2、4次序进入程序可模拟出以1、2、3、4、5开出的完整调度过程。压缩包仅128KB共9个文件包含C源码、头文件、Dev-C工程文件、可执行exe及编译中间文件便于查看算法实现、直接运行验证也适合在Dev-C环境中打开工程进行调试。已有1935人学习下载。通过阅读源码和运行程序能直观理解辅助铁轨对应的栈操作与队列的配合掌握用栈模拟进出过程的编程思路为完成相似实验题目、撰写实验报告和算法设计提供有价值的参考。1. 列车进站先到先走还是后到先走数据结构说了算列车进站这个经典场景是理解栈Stack和队列Queue的最佳入口。一条尽头式股道几列列车按顺序进站出站时是「后进先出」还是「先进先出」完全取决于调度规则——而这规则落到程序里就是栈和队列的本质差别。我见过太多学习者背得住「先进后出、先进先出」八个字真到写代码时却翻车top 初始值设 0 还是 -1、front 和 rear 谁指向元素、出站前要不要判空全凭感觉。下面这套拆解把列车进站场景讲到底先讲两种结构的 C 语言实现和参数细节再讲数组与链表怎么选然后是四个高频坑的排查记录最后落到循环队列、双端队列以及真实系统中的消息队列选型。正在学数据结构、准备机试、或者想快速捡起栈和队列的应用开发者都适合往下看。2. 用栈实现列车进站调度后到的先走代码与参数拆解2.1 为什么列车进站天然匹配栈一条尽头式股道只有一个出入口列车从这一端进去也只能从这一端出来。第 1 列列车先进去停在最里面第 2 列进去挡在它后面第 3 列再进去……如果现在调度员喊发车能动的只能是最后进去的那一列。这个「只能从同一端进出、操作永远发生在最外侧」的约束就是栈的语义。很多人背「先进后出」背得很熟但没意识到这个例子真正的价值在于两个约束栈只有一端能操作而且操作只发生在这一端。理解了这两个约束你就不会再问「栈能不能从中间取元素」这种问题——能取但那就不是栈了是数组。栈的抽象是靠约束约束出来的不是结构天然长成那样。调度员喊「推」和「拉」对应到代码就是 push 和 pop理解了约束代码就不会写歪。2.2 数组版栈定容、压栈、出栈的完整实现先看最常用的数组实现。用固定数组模拟股道MAX_TRAIN 是股道容量top 是栈顶下标-1 表示空栈#include stdio.h #include stdbool.h #define MAX_TRAIN 10 // 股道最多容纳 10 列列车 typedef struct { int data[MAX_TRAIN]; // 列车编号数组 int top; // 栈顶下标-1 表示空栈 } Stack; void initStack(Stack *s) { s-top -1; } bool isEmpty(Stack *s) { return s-top -1; } bool isFull(Stack *s) { return s-top MAX_TRAIN - 1; } // 列车进站等价于入栈 bool push(Stack *s, int trainNo) { if (isFull(s)) { printf(股道已满列车 %d 无法进站\n, trainNo); return false; } s-data[s-top] trainNo; // 先移动 top再写入数据 return true; } // 列车出站等价于出栈 int pop(Stack *s) { if (isEmpty(s)) { printf(股道已空没有列车可出站\n); return -1; } return s-data[s-top--]; // 先取数据再回退 top } int peek(Stack *s) { if (isEmpty(s)) return -1; return s-data[s-top]; }压栈那行s-data[s-top] trainNo是关键先让 top 从 -1 走到 0再在 data[0] 写入第一列列车。出栈反过来s-data[s-top--]先取走当前栈顶再把 top 回退一格。顺序不能反反了就会覆盖掉还没取走的数据。提示top 的初始值决定了整组代码的写法。-1 表示栈顶下标0 表示下一个空位两套约定都有人用但混用必出 bug。全项目统一一种约定比靠记性好用得多。peek 只读栈顶不弹出相当于调度员看一眼最外面是哪列列车不做实际发车动作。top 的范围是 -1 到 MAX_TRAIN-1初始化成 -1 之后空栈和满栈的判断都靠它这套约定前后必须一致。2.3 链表版栈动态扩容与内存释放数组栈容量固定列车超过 MAX_TRAIN 就进不来了。如果调度场景的列车数不可预知常见做法是换链表实现每个节点就是一列列车用头插法让新节点永远在栈顶#include stdio.h #include stdlib.h typedef struct TrainNode { int trainNo; struct TrainNode *next; } TrainNode; typedef struct { TrainNode *top; // 栈顶指针 } LinkedStack; void initLinkedStack(LinkedStack *s) { s-top NULL; } // 进站头插法新列车永远在栈顶 void pushL(LinkedStack *s, int trainNo) { TrainNode *node (TrainNode *)malloc(sizeof(TrainNode)); if (node NULL) { printf(内存分配失败列车 %d 无法进站\n, trainNo); return; } node-trainNo trainNo; node-next s-top; // 新节点指向原栈顶 s-top node; // 栈顶更新到新节点 } // 出站删掉栈顶节点 int popL(LinkedStack *s) { if (s-top NULL) { printf(股道已空没有列车可出站\n); return -1; } TrainNode *tmp s-top; int trainNo tmp-trainNo; s-top s-top-next; // 栈顶后移 free(tmp); // 释放节点避免内存泄漏 return trainNo; }注意node-next s-top这行它把新节点的 next 指向旧的栈顶再把栈顶指针更新到新节点。顺序不能反过来否则旧栈顶丢失链表就断了。malloc 之后一定要判空虽然大多数时候不会失败但在嵌入式或长时间运行的场景里内存不足是真实存在的。链表栈的代价是每个节点都要一次 malloc 和一次 free。入栈出栈本身是 O(1)但 malloc 的系统调用开销比数组下标访问大一个数量级。调度频率低、数据量小无所谓如果是高吞吐场景数组栈加动态扩容往往更划算。2.4 用进站序列验证出站序列为什么顺序进站会反序出站实现写完了怎么证明它没写错最简单的方式是拿一个已知序列跑一遍。进站顺序 101、202、303用栈调度出站必然是 303、202、101int main(void) { Stack yard; initStack(yard); int inbound[] {101, 202, 303}; int n sizeof(inbound) / sizeof(inbound[0]); printf( 列车依次进站 \n); for (int i 0; i n; i) { push(yard, inbound[i]); printf(列车 %d 进站当前栈顶: %d\n, inbound[i], peek(yard)); } printf( 列车依次出站 \n); while (!isEmpty(yard)) { printf(列车 %d 出站\n, pop(yard)); } return 0; }跑出来的输出是「列车 303 出站、列车 202 出站、列车 101 出站」。这个验证思路可以推广任何入栈序列和出栈序列的组合都可以用一个模拟程序去验证合法性。判断一个出站序列能不能由某个进站序列通过栈操作得到经典做法是双指针模拟出栈过程——出站序列的当前元素如果是栈顶就出栈否则继续按进站顺序压栈。这个思路在机试里几乎是必考的。这里还可以顺带提一句单调栈如果栈内元素始终保持某种单调性从栈底到栈顶递增或递减那就是单调栈典型用途是求「下一个更大元素」和直方图最大矩形。列车进站的栈是普通栈单调栈只是在这个结构上多了一条约束理解普通栈之后再去碰单调栈会顺很多。3. 用队列实现列车接发先到的先走两种实现对比3.1 队列语义对应的调度场景栈对应的是尽头式股道列车只能从同一端进出。但如果换一种场景列车进站后要按到达顺序排队等待旅客换乘先到的先发车这时候再用栈就不对了。先到先走是队列的语义队头是等待最久的列车队尾是最新到达的列车进站加到队尾发车从队头走。这种队列场景在真实世界里太常见了车站售票窗口的排队、打印机任务队列、消息队列里的请求……全都是同一个模型。队列的两个操作叫 enqueue入队和 dequeue出队一个发生在队尾一个发生在队头两边各干各的互不干扰。理解队列关键是理解 front 和 rear 两个指针各管一边。3.2 顺序队列front 与 rear 的移动逻辑顺序队列用数组实现front 指向队头元素rear 指向队尾元素的下一个位置#include stdio.h #include stdbool.h #define MAX_TRAIN 10 typedef struct { int data[MAX_TRAIN]; int front; // 队头下标指向第一个元素 int rear; // 队尾下标指向最后一个元素的下一个位置 } Queue; void initQueue(Queue *q) { q-front 0; q-rear 0; } bool isQueueEmpty(Queue *q) { return q-front q-rear; } bool isQueueFull(Queue *q) { return q-rear MAX_TRAIN; } // 列车进站排队加到队尾 bool enqueue(Queue *q, int trainNo) { if (isQueueFull(q)) { printf(队列已满列车 %d 无法排队\n, trainNo); return false; } q-data[q-rear] trainNo; // 先写入rear 再后移 return true; } // 列车发车从队头走 int dequeue(Queue *q) { if (isQueueEmpty(q)) { printf(队列为空无列车可出站\n); return -1; } return q-data[q-front]; // 先取队头front 后移 }这里q-data[q-rear] trainNo是先写入再移动 rearreturn q-data[q-front]是先取数再移动 front。和栈类似移动顺序错了就会读到脏数据。空队列的判断front rear只在初始化后、未发生假溢出时成立这个后面第 5 章会专门讲坑。顺序队列的实现简单、缓存友好列车编号在内存里是连续存储的。但它有一个隐藏问题dequeue 之后 front 不断后移队头前面的空间永远空着rear 到顶之后整个队列就被判定为「满」哪怕前面明明空出一大片。这就是经典的假溢出第 5 章会展开。3.3 链式队列队头出、队尾入的关键细节链式队列用链表实现每个节点是一列列车。和链栈不同的是队列需要两个指针front 指向队头rear 指向队尾。入队挂在 rear 后面出队从 front 摘#include stdio.h #include stdlib.h typedef struct TrainNode { int trainNo; struct TrainNode *next; } TrainNode; typedef struct { TrainNode *front; // 队头指针 TrainNode *rear; // 队尾指针 } LinkedQueue; void initLinkedQueue(LinkedQueue *q) { q-front NULL; q-rear NULL; } // 入队新节点挂在队尾 void enqueueL(LinkedQueue *q, int trainNo) { TrainNode *node (TrainNode *)malloc(sizeof(TrainNode)); if (node NULL) return; node-trainNo trainNo; node-next NULL; if (q-rear NULL) { q-front q-rear node; // 第一个节点两个指针都指向它 } else { q-rear-next node; // 挂在原队尾后面 q-rear node; // rear 更新到新节点 } } // 出队从队头摘节点 int dequeueL(LinkedQueue *q) { if (q-front NULL) { printf(队列为空无列车可出站\n); return -1; } TrainNode *tmp q-front; int trainNo tmp-trainNo; q-front q-front-next; if (q-front NULL) { q-rear NULL; // 队列变空rear 必须同步置空 } free(tmp); return trainNo; }链式队列最容易踩的坑在出队最后那两行弹出最后一个节点后必须把 rear 也置空。如果只移动 front 而不处理 rear下一次入队时会走到q-rear-next node这行但 rear 还指向一个已经被 free 掉的节点这是典型的悬垂指针程序会随机崩溃。这类 bug 在单测里往往测不出来因为要恰好触发「队列从非空变空再到非空」的边界状态才会暴露。链式队列没有容量上限只要内存够就能一直入队代价是每个节点一次 malloc。如果列车编号本身是连续整数也可以用预分配节点池的方式来消除 malloc 抖动这个就属于工程优化了。4. 数组还是链表四类实现的选型边界与性能对比4.1 数组实现的栈容量固定扩容要迁移数组栈最省心的地方是内存连续、下标访问 O(1)、没有 malloc 开销。但容量订死了MAX_TRAIN 设 10第 11 列列车进站就只能被拒绝。被拒绝的列车在真实调度里意味着事故所以在业务侧一般有两种处理一是把 MAX_TRAIN 设成预估峰值的两倍二是实现动态扩容。常见的做法是复制到新数组。检测到满栈时申请一块更大的内存把原数组整体搬过去再释放旧数组。这个操作是 O(n)好在栈操作是摊还 O(1)——大部分时候不需要扩容偶尔一次的开销被之前的操作摊薄了。C 语言里可以用 realloc 完成搬迁但注意 realloc 失败会返回 NULL直接把原指针覆盖掉会造成内存泄漏正确姿势是先用临时指针接住 realloc 的返回值。用 realloc 扩容有一个取舍是每次翻倍还是一次加大固定值。翻倍扩容的摊还代价更低但会浪费内存固定步长扩容比较省内存但扩容次数多。我一般建议栈和队列这种不确定峰值的场景选翻倍扩容因为它们的操作模式就是突发性的进和出翻倍能显著减少迁移次数。4.2 链表实现的栈每次操作一次 malloc链表栈解决了容量问题引入了新麻烦每一次 push 和 pop 都伴随一次 malloc 和 free。malloc 本身不慢但在高频调度场景里频繁分配释放会产生内存碎片长时间跑下来堆空间会碎成一地鸡毛。这个问题在嵌入式环境里尤其明显。如果已经能确定峰值数组栈加合理容量就好真不确定峰值再用链表。还有一种中间方案是数组栈配扩容几乎能兼顾两者的优点。链栈真正的优势是删除和插入都是 O(1) 且不需要搬迁适合元素大小不一致的场景——不过列车编号是 int不存在这个需求。4.3 顺序队列的假溢出与链队列的无界顺序队列比顺序栈多了一个隐患假溢出。front 不断后移rear 到顶后队列被判定为满但 front 前面明明空着大量位置。解决手段是循环队列让 rear 到顶后绕回数组开头也就是取模运算这个第 6 章细讲。链式队列没有容量上限入队只受内存限制。但它和链栈有同样的代价每个节点都要 malloc。队列场景里如果入队出队频率极高malloc/free 的开销会被放大这时选循环队列更合适。真实系统里两种都用吞吐量敏感的场景倾向循环队列流量不可预知的场景倾向链表。4.4 四种实现选型对照表实现方式入队/入栈出队/出栈容量主要风险数组栈O(1)O(1)固定满栈拒绝需扩容链表栈O(1)mallocO(1)free仅受内存限制碎片、悬垂指针顺序队列O(1)O(1)固定假溢出链式队列O(1)mallocO(1)free仅受内存限制悬垂指针、碎片选型逻辑其实只有三条能预估峰值就选数组不能预估就选链表如果选数组队列务必加上循环取模。很多面试官爱问「栈和队列用数组还是链表实现」答案不是二选一而是先问场景再定方案。嵌入式里中断服务程序用的队列十有八九是定长数组循环队列因为 ISR 里不允许调用 malloc。这个约束直接决定了选型代码层面省不了。提示选型对照表的前提是单线程操作。多线程并发场景下数组结构加锁的粒度、伪共享问题都比链表更难处理届时优先考虑现成的并发队列实现。5. 列车调度代码中的四个常见问题从现象到排查5.1 现象栈顶初始值设成 0空栈判定全乱现象初始化时把 top 设为 0push 时用data[top] trainNo结果第一列列车存进 data[0]top 变成 1逻辑上没错但 isEmpty 的判断top 0一开始就返回 true——明明有元素却判成空栈。出站时永远少一列车最后还会越界读到 data[0] 的残留值。原因top 的语义自相矛盾。top -1 表示栈顶下标空栈时没有任何元素所以是 -1如果改成 top 0那 0 到底是「空栈」还是「有一个元素在 data[0]」两种约定撞在一起。这类 bug 排查起来像玄学本质上就是初始值、判空条件、压栈顺序用了三套不同的约定。解决统一采用top -1的约定初始化 -1判空top -1压栈data[top] trainNo出栈data[top--]。如果不习惯负数也可以用top 0表示下一个空位那判空就写成top 0压栈data[top] trainNo。两种都可以但要全篇保持一致。这是我写代码时踩过最蠢的坑之一每次复盘都想抽当时的自己。5.2 现象顺序队列 front 后移空间却永久减少现象顺序队列跑着跑着入队次数还不到 MAX_TRAIN 就报「队列已满」。仔细看 front 已经不是 0前面空着几个位置但 rear 顶到数组末尾isQueueFull 直接返回 true。原因顺序队列的isQueueFull用的是rear MAX_TRAIN它只看了 rear 的位置没看 front。front 前移后留出的空洞没有被复用rear 到顶即视为满这是假溢出。解决改成循环队列rear 到顶后通过(rear 1) % MAX_TRAIN绕回数组开头把 front 让出的空间用起来。另一个常用方案是用 length 字段记录当前元素个数空满判断都基于 length不依赖 front 和 rear 的绝对位置。机试里常见的「以数组 q[m] 存放循环队列中的元素同时以 rear 和 length 分别指示环形队列中的队尾和长度」就是这个思路空队length 0满队length MAX_TRAIN两个指针随便绕。5.3 现象出栈出队前不判空读回野数据现象pop 和 dequeue 不检查空状态直接操作。栈空时 top 是 -1data[-1]在 C 里是未定义行为运气好读到残留值运气差直接段错误。队列空时front rear取到的可能是上次遗留的列车编号调度系统会把这列根本不存在的车安排发车。原因把「正常情况下栈不会空」当成了「栈永远不会空」。调用方不能保证每次出站前都恰好有车尤其是多线程或中断嵌套场景时序一乱就踩空。解决pop/dequeue 的入口一律判空返回 bool 或让出队函数在空时返回哨兵值。C 语言里没有异常机制唯一的防线就是每个函数入口自己检查。我一般还会加一层断言调试版本里直接 crash 暴露问题发布版本里降级成错误日志。多写一个判空花不了两行代码少写一个判空等线上崩了就真没有后悔药。5.4 现象backtrace 栈回溯打印的调用顺序是反的现象程序崩溃后用 backtrace 查看调用栈打印出来第一行是当前正在执行的函数最后一行才是 main。有人按打印顺序从上往下读把调用关系读反排查方向整个错掉。在 ARM Cortex-M 上做中断栈回溯时栈的生长方向还和 x86 不同更容易看反。原因函数调用的活动记录本身就是栈结构。每调用一层函数就把返回地址压进栈backtrace 从栈顶往外弹先弹出来的自然是最内层。栈底在最下面打印顺序从栈顶开始所以看起来是「倒着的」。这里说的栈和 malloc 的堆是两个完全不同的存储区域函数调用链活在系统栈上malloc 出来的节点活在堆上面试里问的堆和栈的区别指的正是这两个和容器里的 Stack 对象不是一回事。解决读 backtrace 时永远从下往上追。最下面一行是根最上面一行是崩溃现场。调试器里选栈帧也要注意这个方向。这套回溯逻辑用的就是栈的「后进先出」——最晚进站的那列车最先出站和列车进站模型一模一样。6. 进阶循环队列、双端队列与真实系统的队列选择6.1 循环队列用 rear 和 length 判空满绕开假溢出循环队列解决假溢出的方式是让数组头尾相接rear 和 front 到边界后用取模绕回。难点在空满判断只用 front rear 判空满时 front 也可能等于 rear因为绕了一圈。加一个 length 字段最省心#define MAX_TRAIN 10 typedef struct { int data[MAX_TRAIN]; int front; int rear; int length; // 当前元素个数 } CircularQueue; void initCQueue(CircularQueue *q) { q-front 0; q-rear 0; q-length 0; } bool enqueueC(CircularQueue *q, int trainNo) { if (q-length MAX_TRAIN) return false; q-data[q-rear] trainNo; q-rear (q-rear 1) % MAX_TRAIN; q-length; return true; } int dequeueC(CircularQueue *q) { if (q-length 0) return -1; int trainNo q-data[q-front]; q-front (q-front 1) % MAX_TRAIN; q-length--; return trainNo; }入队先写数据再绕 rear出队先取数据再绕 front。length 记录真实数量front 和 rear 只是游标。这正好对应机试经典题「假设以数组 q[m] 存放循环队列中的元素同时以 rear 和 length 分别指示环形队列中的队尾位置和元素个数」我第一次写也绕了半天用 length 之后豁然开朗。6.2 双端队列列车两端都可以进出的调度双端队列deque是栈和队列的合体两头都能进、两头都能出。对应到列车调度就是一条两端都通股道的咽喉列车可以从任意一端进出。实现上比普通队列多 pushFront、pushBack、popFront、popBack 四个操作工程上一般用环形缓冲区加两个游标实现。双端队列最实用的场景是滑动窗口最大值配合单调队列维护一个从队头到队尾单调递减的队列窗口滑动时从队头淘汰过期元素新元素从队尾入队并淘汰所有更小的值。这个套路同样是面试高频题。6.3 落到真实系统线程池的阻塞队列怎么选栈和队列不只是课堂概念。线程池的任务队列、消息队列中间件、操作系统的就绪队列全是队列的实际应用。线程池里多个 worker 抢任务时队列必须支持并发访问这就是阻塞队列的由来。常见选型里SynchronousQueue 不存任务直接交接给线程LinkedBlockingQueue 无界任务不丢但可能堆积ArrayBlockingQueue 有界满了之后提交方阻塞或拒绝。选哪个先想清楚一个问题系统能不能接受积压。能就无界不能就有界加拒绝策略。更高并发的场景还有无锁队列基于 CAS 原子操作实现那是另一个值得单独展开的话题。这个逻辑和第 4 章的选型表完全一致——先想清楚容量边界再决定数组还是链表。从那以后我每写一个栈或队列都会强制走一遍检查清单top 初始值是不是 -1、出站前有没有判空、顺序队列有没有假溢出、链表节点释放后有没有留下悬垂指针。这套习惯治好了我给队列加 bug 的老毛病。列车进站的例子虽然简单但把它吃透这两个结构就算真正落地了希望帮到你。本文还有配套的精品资源点击获取