简介这份资源围绕经典的“列车进站”调度问题展开面向正在学习数据结构与算法、需要理解栈与队列实际应用的学生和编程练习者。题目给定一个“丁”字型铁路调度系统主铁轨与辅助铁轨相互垂直车厢只能单向流动要求编程求出将任意入站序列调整为1至n顺序出站的完整调度过程是栈与队列综合运用的典型实验案例。资源包共9个文件压缩后约128KB包含cpp源码、h头文件、o目标文件、exe可执行程序以及dev工程文件等覆盖从源码到可运行工程的完整内容便于直接编译调试与对照学习。目前已有1935人学习下载。读者可借助其中的栈、队列实现与调度逻辑理解辅助铁轨的入栈出栈规则掌握序列合法性判断与模拟求解思路并参考工程结构自行扩展测试用例。1. 列车进站栈与队列的调度逻辑到底怎么落地高铁站台只有一条轨道先到的列车先停靠、后到的排队等位这就是队列而列车检修时最后一节车厢先被拖走、最先拖走的反而最后归位这就是栈。很多同学在刷算法题时能把「栈、队列」的 push/pop、enqueue/dequeue 背得滚瓜烂熟一到真实项目里就翻车——比如用数组模拟队列时忘了处理假溢出或者用栈做括号匹配时把空栈判断漏掉直接数组越界。这份资源把「列车进站」这个场景拆成栈和队列两条主线用可运行的代码把顺序存储、链式存储、循环队列、合法出栈序列判定这些高频考点串起来。适合正在准备数据结构实验、面试手撕代码或者想给团队做内部培训的工程师。下面我按自己复现时的顺序把关键参数和踩过的坑一条条摊开。2. 顺序栈与顺序队列从数组模拟到边界判定2.1 为什么先用数组模拟而不是直接上 STL很多教程一上来就#include stack、#include queue跑得通但考不出真功夫。列车进站这个场景里站台容量固定、列车编号连续用数组模拟反而更贴近物理模型。顺序栈的核心是top指针顺序队列的核心是front和rear两个指针。我一般会先写一个固定容量的版本把overflow和underflow两种异常显式暴露出来再考虑动态扩容。先看顺序栈的入栈和出栈#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针指向当前栈顶元素下标 } SeqStack; // 初始化top -1 表示空栈 void InitStack(SeqStack *s) { s-top -1; } // 入栈先判满再移动指针 int Push(SeqStack *s, int e) { if (s-top MAXSIZE - 1) { return 0; // 栈满入栈失败 } s-data[(s-top)] e; // 先加再存 return 1; } // 出栈先判空再取元素 int Pop(SeqStack *s, int *e) { if (s-top -1) { return 0; // 栈空出栈失败 } *e s-data[(s-top)--]; // 先取再减 return 1; }逻辑说明top初始化为 -1 是顺序栈最常见的约定入栈时top再赋值出栈时先取值再top--。参数MAXSIZE决定站台容量改成 10 就能模拟小型站台。注意Push和Pop都返回 int 表示成功与否调用方必须检查返回值否则栈满时继续写就是内存越界。顺序队列的坑更多。如果直接用front和rear同向移动出队后前面的空间永远用不上这就是假溢出。常见做法是改成循环队列用取模运算把rear绕回来typedef struct { int data[MAXSIZE]; int front; // 队头指针指向当前队头元素 int rear; // 队尾指针指向下一个入队位置 } CircularQueue; void InitQueue(CircularQueue *q) { q-front 0; q-rear 0; } // 入队先判满再存元素rear 后移取模 int EnQueue(CircularQueue *q, int e) { if ((q-rear 1) % MAXSIZE q-front) { return 0; // 队满牺牲一个存储单元 } q-data[q-rear] e; q-rear (q-rear 1) % MAXSIZE; return 1; } // 出队先判空再取元素front 后移取模 int DeQueue(CircularQueue *q, int *e) { if (q-front q-rear) { return 0; // 队空 } *e q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }参数说明循环队列判满用(rear 1) % MAXSIZE front代价是永远空一个格子。如果不想浪费这个格子可以额外加一个count变量记录元素个数判满条件改成count MAXSIZE。我一般会在注释里写清楚用的是哪种约定避免队友看代码时把判满条件抄错。2.2 链式队列指针操作与内存释放数组模拟适合容量固定的场景但列车进站如果遇到节假日加开临客固定容量就不够用了。链式队列用节点动态申请内存入队就是尾插出队就是头删。这里最容易翻车的是出队时忘记free节点跑一晚上内存直接爆掉。typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front; // 队头指针 QNode *rear; // 队尾指针 } LinkQueue; void InitLinkQueue(LinkQueue *q) { QNode *head (QNode *)malloc(sizeof(QNode)); head-next NULL; q-front head; q-rear head; } int EnLinkQueue(LinkQueue *q, int e) { QNode *node (QNode *)malloc(sizeof(QNode)); if (node NULL) return 0; node-data e; node-next NULL; q-rear-next node; // 挂到队尾 q-rear node; // 更新队尾指针 return 1; } int DeLinkQueue(LinkQueue *q, int *e) { if (q-front q-rear) return 0; // 空队列 QNode *p q-front-next; // 第一个数据节点 *e p-data; q-front-next p-next; if (q-rear p) { // 只有一个节点时rear 要回退 q-rear q-front; } free(p); // 关键释放节点 return 1; }逻辑说明链式队列带头节点front指向头节点rear指向最后一个数据节点。出队时如果队列只剩一个节点rear必须回退到头节点否则rear会变成野指针。参数上malloc失败要返回 0调用方决定是重试还是报错。常见做法是封装一个DestroyQueue函数循环出队直到空把每个节点都释放掉。3. 栈与队列的相互模拟两个栈实现队列、两个队列实现栈3.1 两个栈实现队列入队 O(1)出队均摊 O(1)面试里高频出现的一道题用两个栈模拟队列。思路是stackIn负责入队stackOut负责出队。入队直接压stackIn出队时如果stackOut为空就把stackIn全部弹出并压入stackOut再从stackOut弹出。这样每个元素最多被搬运两次均摊时间复杂度 O(1)。class MyQueue: def __init__(self): self.stack_in [] self.stack_out [] def push(self, x: int) - None: self.stack_in.append(x) def pop(self) - int: if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) - int: if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1] def empty(self) - bool: return not self.stack_in and not self.stack_out参数说明stack_in和stack_out都是普通列表append和pop分别对应入栈和出栈。peek和pop都要先检查stack_out是否为空为空才搬运。注意empty必须同时判断两个栈只判断一个会漏掉元素还在stack_in里的情况。3.2 两个队列实现栈入栈 O(n)出栈 O(1)反过来用两个队列模拟栈常见做法是入栈时把元素放到空队列然后把另一个队列的元素全部搬过来保证新元素永远在队头。这样出栈就是普通出队时间复杂度 O(1)但入栈变成 O(n)。from collections import deque class MyStack: def __init__(self): self.q1 deque() self.q2 deque() def push(self, x: int) - None: self.q2.append(x) while self.q1: self.q2.append(self.q1.popleft()) self.q1, self.q2 self.q2, self.q1 def pop(self) - int: return self.q1.popleft() def top(self) - int: return self.q1[0] def empty(self) - bool: return not self.q1逻辑说明push先把新元素放进q2再把q1里所有元素依次搬到q2最后交换q1和q2。这样q1的队头永远是最新入栈的元素。参数上deque的popleft是 O(1)如果用普通列表的pop(0)会退化成 O(n)。常见误用是忘记交换队列导致下次push时元素顺序错乱。3.3 合法出栈序列判定模拟栈的压入弹出给定一个入栈序列判断某个出栈序列是否合法这是栈的经典应用题。做法是用一个辅助栈模拟按入栈序列依次压栈每压一个就检查栈顶是否等于出栈序列当前元素相等就弹出并移动出栈指针。最后栈为空则合法。def validate_stack_sequences(pushed, popped): stack [] j 0 for x in pushed: stack.append(x) while stack and stack[-1] popped[j]: stack.pop() j 1 return not stack参数说明pushed是入栈序列popped是待判定的出栈序列两者长度必须相等。j指向popped当前待匹配元素。循环结束后如果stack为空说明所有元素都按popped的顺序弹出序列合法。注意while条件里要先判断stack非空否则stack[-1]会越界。4. 避坑与排查栈队列实现里最容易翻车的五个点4.1 循环队列判满条件写错导致队满时还能入队现象队列明明已经满了EnQueue还返回成功继续写就覆盖了队头元素。原因判满条件写成rear front这和判空条件冲突。解决用(rear 1) % MAXSIZE front判满或者额外维护count变量。我一般会在初始化时把front和rear都置 0并在注释里写明「牺牲一个存储单元」。4.2 链式队列出队后忘记 free内存持续增长现象程序跑一段时间后内存占用越来越高最终被系统杀掉。原因DeLinkQueue里只移动了指针没有free(p)。解决每次出队都要释放被删节点并提供一个DestroyQueue在程序退出前清空剩余节点。用 Valgrind 跑一遍就能看到泄漏点。4.3 两个栈实现队列时出队前忘记检查 stack_out 是否为空现象出队返回了错误元素或者直接抛异常。原因pop和peek直接从stack_out取但stack_out可能为空而stack_in还有元素。解决取之前先判断stack_out为空就把stack_in全部搬过来。搬运时用while stack_in而不是if确保搬干净。4.4 合法出栈序列判定时while 循环条件顺序写反现象程序报数组越界或索引错误。原因写成while stack[-1] popped[j] and stack先访问了stack[-1]才判断非空。解决把非空判断放前面while stack and stack[-1] popped[j]。短路求值会先算左边左边为假就不会访问右边。4.5 用普通列表模拟队列pop(0) 导致性能退化现象数据量到十万级时出队操作明显变慢。原因Python 列表pop(0)需要把后面所有元素前移时间复杂度 O(n)。解决用collections.deque的popleft或者自己用数组加front指针模拟循环队列。C 里同理std::queue底层默认用deque不要用vector做队列。5. 进阶技巧用单调队列把滑动窗口最大值压到 O(n)5.1 单调队列的核心维护一个递减的双端队列滑动窗口最大值是队列的进阶用法。暴力解法每个窗口扫一遍O(nk)单调队列把时间复杂度降到 O(n)。思路是维护一个双端队列队列里存下标对应的值从队头到队尾递减。每次窗口右移先把队尾比当前值小的全部弹出再把当前下标入队如果队头下标已经滑出窗口就弹出队头。这样队头永远是当前窗口最大值。from collections import deque def max_sliding_window(nums, k): dq deque() # 存下标对应值递减 result [] for i, num in enumerate(nums): # 队尾比当前值小的全部弹出 while dq and nums[dq[-1]] num: dq.pop() dq.append(i) # 队头滑出窗口则弹出 if dq[0] i - k: dq.popleft() # 窗口形成后记录最大值 if i k - 1: result.append(nums[dq[0]]) return result参数说明nums是输入数组k是窗口大小。dq存的是下标而不是值这样方便判断队头是否滑出窗口。while里用而不是保证队列里没有重复的较小值。i k - 1表示第一个完整窗口已经形成从这时开始记录结果。5.2 验证方法与性能对比我一般会写一个暴力版本做对拍随机生成数组和窗口大小跑一千组对比结果。下面是对拍脚本的核心部分import random def brute_force(nums, k): return [max(nums[i:ik]) for i in range(len(nums) - k 1)] for _ in range(1000): n random.randint(1, 50) k random.randint(1, n) nums [random.randint(-100, 100) for _ in range(n)] assert max_sliding_window(nums, k) brute_force(nums, k) print(all passed)逻辑说明随机生成长度 1 到 50 的数组窗口大小 1 到 n对比单调队列和暴力解法的输出。一千组全部通过后再把数据量加到十万级用time.perf_counter()测一下耗时。我实测下来十万数据、窗口一千单调队列在 0.05 秒左右暴力解法要 8 秒以上差距非常明显。5.3 一个容易忽略的边界k 大于数组长度如果k大于len(nums)滑动窗口根本形不成应该返回空列表。单调队列版本里i k - 1永远不成立result保持为空逻辑上是对的。但有些实现会在循环外直接取nums[dq[0]]这时候dq可能为空直接翻车。我一般会在函数开头加一句if k 0 or k len(nums): return []把边界挡在外面。从那以后我每次写栈和队列相关的代码都强制先画一遍指针移动图再把判空判满条件单独拎出来检查一遍。列车进站这个场景看着简单真要把顺序栈、循环队列、链式队列、两个栈模拟队列、单调队列全部跑通还是得动手敲一遍才行。希望帮到你。本文还有配套的精品资源点击获取