栈这个数据结构课本上讲完定义和基本操作紧接着端出来的第一个像样的大例子十有八九就是迷宫问题。它不像括号匹配那么一眼看穿也不像表达式求值那样绕但它把栈的后进先出LIFO和回溯这两件事捏在了一起第一次让人真切体会到数据结构不是摆设而是能决定算法能不能跑起来的关键。这篇文章我不打算复述教材而是把我在教学、写代码、帮人看题解过程中攒下来的东西掏出来迷宫问题到底在考什么栈在里面扮演什么角色顺序栈和链栈怎么选代码怎么从零写到能跑跑不通的时候大概率栽在哪几个坑里以及把它吃透之后你还能顺手拿下接雨水、括号匹配、表达式求值这一串同类题。如果你正在学数据结构与算法或者被递归版迷宫程序直接搞到栈溢出这篇应该能帮你把这条线彻底理顺。1. 先想明白迷宫问题到底在考什么很多人拿到迷宫题就急着敲代码结果写了两百行还在纠结坐标怎么加。我建议先把问题抽象这一层想透后面写起来会很轻。1.1 从走迷宫到图搜索的抽象把迷宫摊开看它本质就是一个二维的网格图。每个可通行的格子是一个顶点上下左右相邻的可通行格子之间有一条边。于是从入口走到出口这句话翻译成算法语言就是在这个图里找一条从起点到终点的路径。这个视角转换非常关键一旦转过来你会发现迷宫、八数码、N皇后、图的连通性判定其实是同一类问题的不同外壳。具体的存储约定最经典的做法是用一个二维数组maze[n2][m2]四周包一圈边界。为什么要把数组开大一圈并且在外围填满墙因为这样你在判断某个方向能不能走时就不需要额外写x1 xn这样的边界条件了直接看maze[nx][ny]是不是通路即可。少一个 if就少一个出 bug 的地方这是我特别推荐的工程化小习惯。约定上通常设 0 表示通路、1 表示墙或者反过来但这个约定必须在整个程序里保持统一——我见过太多人前面用 0 表示墙后面判断时忘了结果程序一直在原地打转。另外还有一个容易被忽略的点起点和终点本身也必须是通路。有些测试用例会把终点设成墙或者起点就是墙程序跑出来直接无解。写代码前先在心里过一遍输入边界比事后 debug 省事得多。1.2 为什么偏偏是栈LIFO 与回溯的天作之合这是整篇文章最核心的问题为什么用栈而不是队列也不是普通数组走迷宫的真实动作是站在一个格子上试着往某个方向走一步如果能走就过去把当前位置记住如果四个方向都走不通说明进了死胡同那就退回到上一个位置换一个方向再试。这个退回到上一个位置的动作正是回溯。而记住来时的路并在需要时回到最近的一个位置恰好就是栈的行为特征。你每往前探索一步就把它压入栈每遇到死路就弹出栈顶回到上一个决策点。栈顶永远是你当前所在的位置栈里的内容就是从起点到当前点的整条路径。这个性质漂亮在什么地方你不需要额外维护一个父亲指针数组也不需要递归调用栈帮你偷偷保存现场路径信息本身就存在栈里随时可以打印出来。反过来如果你用队列那就是广度优先搜索BFS它一次探索一圈先进先出找出来的是最短路径在边权都为 1 的情况下但它没法像栈那样自然地把当前这条路径摊在你面前需要额外记录前驱节点才能还原路线。所以栈和队列在这里不是谁替代谁而是深度优先和广度优先两种策略的代表。想找一条路栈足够想找最短的那条得上队列。1.3 数据结构的整体设计动手之前把要用到的东西列清楚这个习惯能省掉大量返工。我通常需要这么几样一个二维数组表示迷宫地图外围加一圈墙一个二维标记数组mark记录某个格子是否已经走过防止兜圈子一个方向数组dir[4][2]把上下左右的坐标增量预先存好循环里直接查表避免写四段几乎一样的代码一个栈元素类型是坐标结构体用来存当前路径起点终点坐标以及一个表示是否找到的标志。这里重点说方向数组。很多初学者会写// 不推荐的写法四段重复逻辑 if (maze[x1][y] 0 !mark[x1][y]) { ... } if (maze[x][y1] 0 !mark[x][y1]) { ... } if (maze[x-1][y] 0 !mark[x-1][y]) { ... } if (maze[x][y-1] 0 !mark[x][y-1]) { ... }这段代码能跑但一旦你想改成八个方向加上对角线或者想动态调整探索顺序就得复制粘贴到怀疑人生。而用方向数组int dir[4][2] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 在循环里 for (int d 0; d 4; d) { int nx x dir[d][0]; int ny y dir[d][1]; // 统一处理 }代码短了一半扩展性还强。这个技巧不只用在迷宫后面讲剪枝、讲 BFS 都会反复出现值得刻进肌肉记忆。2. 栈的选型顺序栈、链栈还是语言自带的容器知道了要用栈下一个问题是用哪种栈。这不是一个可以随便糊弄的问题不同选择在边界处理、内存、代码量上差别不小。2.1 顺序栈的实现与边界处理顺序栈就是数组加一个栈顶指针最简单也最常用。核心操作只有三个入栈、出栈、判空。但魔鬼藏在细节里尤其是栈顶指针的初始值和判断条件。我习惯的写法是top -1表示空栈入栈时先top再赋值出栈时取data[top]再--top判空就是top -1。这套约定内部自洽不容易错。但你要注意另一种常见约定是top 0表示空栈此时判空变成top 0入栈是data[top] x。两套写法本身都没问题最怕的是混着用——比如初始化用了 -1判空却写top 0那空栈会被误判成有一个元素程序直接读到垃圾数据。我在帮人看代码时这类错误出现的频率高得离谱。关于栈的大小怎么定给一个保守的估算方法。迷宫是 n×m 个格子栈的最大深度不会超过可通行格子的总数也就是n*m。所以顺序栈的容量开到n*m 10就绝对安全。如果题目规模是 100×100那就是一万个元素每个元素是一个坐标两个 int8 字节总共 80KB 左右对于现代机器的内存完全不值一提。但如果你开的是data[100]而迷宫有 2500 个格子那走到一半就溢出了症状是路径莫名其妙断掉或者程序崩溃。先算容量再开数组这一步不能省。2.2 链栈的取舍链栈用节点动态申请内存理论上没有容量上限入栈出栈都是 O(1)。听上去很美但在迷宫这种场景里我并不推荐。原因很实际。第一链栈每次入栈都要malloc一个节点出栈要free一次完整的探索可能产生成千上万次内存申请与释放开销远大于数组的指针加减。第二也是更烦的一点动态内存管理会引入新的错误来源忘记释放导致内存泄漏释放后再次访问导致野指针这些 bug 在调试器里比栈溢出错难找多了。第三在很多编程竞赛或面试的评分环境里malloc的调用是被严格计时的。那链栈什么时候值得用当栈的最大深度事先完全无法估计而且可能非常大同时又不能一次性开一个大数组比如嵌入式环境内存极度受限的时候。迷宫问题显然不满足这些条件所以老老实实用顺序栈就好。这个判断逻辑可以推广到很多场景当上界可估且不算大数组永远比链表省心。2.3 用语言内置容器模拟栈的坑如果你用 Python多半会用list直接当栈append入栈、pop出栈非常顺手。Java 里有现成的Stack类C 有std::stack。这些都没问题但有两个坑要提前知道。第一个是Python 的列表当栈时pop()默认弹最后一个这正好符合 LIFO这点没问题。但很多人习惯性地写pop(0)那是从头部弹出复杂度是 O(n)而且语义变成了队列整个算法的行为就悄悄变了从深度优先变成了广度优先你还纳闷为什么结果不对。第二个是Java 的Stack类继承自Vector方法是同步的。同步意味着每次操作都要加锁解锁在单线程场景下纯属白白付出的性能开销。所以 Java 里更推荐的写法是用ArrayDeque来模拟栈push/pop/peek方法都在效率高得多。这个小知识点在面试里经常被拿来问属于知道的人觉得理所当然不知道的人一脸懵的类型。2.4 别把栈内存和栈这个数据结构搞混这是个特别典型的困惑我几乎每个学期都会被问到函数调用用的那个栈和我们迷宫题里用的这个栈是同一个东西吗严格说不是。函数调用栈是操作系统和编译器在内存里划出的一块区域用来保存返回地址、局部变量、寄存器现场它的增长和收缩由函数调用与返回自动驱动你写代码时基本感知不到。而迷宫题里的栈是你自己在代码里定义的一个数据结构它住在堆内存或者静态数据区如果定义成全局数组由你的push/pop显式控制。它们相同的地方在于遵循同一套 LIFO 原则这也是为什么递归版本的迷宫程序可以完全不写一个显式的栈——因为编译器用函数调用栈帮你把回溯现场这件事做了。理解这层对应关系你就明白递归和迭代为什么能互相转换了。顺带一提Python 默认的递归深度限制在一千层左右用递归写迷宫搜索稍微大一点的图就会抛RecursionError本质上就是调用栈溢出了。这也是为什么大图上我更倾向显式栈的迭代写法。3. 核心算法实现一步一步把路径找出来理论聊够了来看代码。我先把算法主循环拆开讲再给完整实现。3.1 方向数组与坐标约定先把探索顺序定下来。方向数组{{1,0},{0,1},{-1,0},{0,-1}}对应的顺序是下、右、上、左。这个顺序会直接影响程序在有多条路径时找到的是哪一条但不会影响是否有解这个结论。如果你想让它优先往右走就把{0,1}挪到第一个。这个细节对调试很有用当你不确定结果对不对时固定一个方向的搜索顺序然后手动推演一遍能快速验证逻辑。坐标上我用(x, y)表示第 x 行第 y 列往下 x 增大往右 y 增大。这个约定和大多数教材一致也和二维数组的下标顺序一致。千万别一会儿把 x 当列一会儿当行那是最典型的低级错误我见过有人为此 debug 一整晚。3.2 算法主循环拆解整个搜索过程的骨架其实就四句话我用大白话描述一遍把起点压入栈标记起点已访问只要栈不空就看一眼栈顶注意是先看一眼不是立刻弹出来如果栈顶就是终点成功退出否则依次尝试四个方向找到第一个能走的邻格标记它、把它压栈然后回到第 2 步如果四个方向都走不通说明栈顶这个位置是死路弹出它回到栈里上一个位置重新尝试循环结束时如果栈空了还没到终点说明无解。这里有个关键细节特别容易写错主循环里是先 peek 栈顶再决定要不要弹。很多人的代码写成每轮循环开头就 pop 一个出来结果弹出的元素还没尝试过方向就被当成废弃点扔了路径自然接不上。正确的节奏是栈顶代表我当前站的地方它要一直留在栈里直到确认是死路才被弹出。想清楚这一点代码逻辑就顺了。3.3 完整代码实现C 与 Python先给 C 语言的顺序栈版本这是我教学时最常用的模板#include stdio.h #include string.h #define MAXN 105 #define MAXS 10005 typedef struct { int x, y; } Pos; typedef struct { Pos data[MAXS]; int top; // 空栈为 -1 } Stack; void push(Stack *s, Pos p) { s-data[(s-top)] p; } Pos pop (Stack *s) { return s-data[(s-top)--]; } Pos peek(Stack *s) { return s-data[s-top]; } int empty(Stack *s) { return s-top 0; } int maze[MAXN][MAXN]; int mark[MAXN][MAXN]; int dir[4][2] {{1,0},{0,1},{-1,0},{0,-1}}; int main() { int n, m; scanf(%d %d, n, m); memset(maze, 1, sizeof(maze)); // 全部先当作墙 for (int i 1; i n; i) for (int j 1; j m; j) scanf(%d, maze[i][j]); Stack s; s.top -1; Pos start {1, 1}, target {n, m}; if (maze[start.x][start.y] 1) { printf(no path\n); return 0; } push(s, start); mark[start.x][start.y] 1; int found 0; while (!empty(s)) { Pos cur peek(s); if (cur.x target.x cur.y target.y) { found 1; break; } int moved 0; for (int d 0; d 4; d) { int nx cur.x dir[d][0]; int ny cur.y dir[d][1]; if (maze[nx][ny] 0 mark[nx][ny] 0) { Pos np {nx, ny}; mark[nx][ny] 1; push(s, np); moved 1; break; // 关键一次只走一步 } } if (!moved) pop(s); // 死路回退 } if (!found) { printf(no path\n); } else { printf(path length %d\n, s.top 1); for (int i 0; i s.top; i) printf((%d,%d)%s, s.data[i].x, s.data[i].y, i s.top ? \n : - ); } return 0; }再看 Python 版本短很多适合快速验证思路def solve(maze): n, m len(maze), len(maze[0]) dirs [(1, 0), (0, 1), (-1, 0), (0, -1)] stack [(0, 0)] visited [[False] * m for _ in range(n)] visited[0][0] True while stack: x, y stack[-1] if (x, y) (n - 1, m - 1): return list(stack) # 栈里就是完整路径 moved False for dx, dy in dirs: nx, ny x dx, y dy if 0 nx n and 0 ny m \ and maze[nx][ny] 0 and not visited[nx][ny]: visited[nx][ny] True stack.append((nx, ny)) moved True break if not moved: stack.pop() return NonePython 版没加外围墙边界判断写在条件里这是两种风格选你顺手的就行。3.4 关键参数与复杂度计算先说时间复杂度。最坏情况下每个格子可能被访问一次每次访问要对四个方向做判断所以是O(n·m)。这个结论有个前提每个格子只入栈一次。而这正是mark数组的作用——它保证一个格子不会被重复压栈。但这里有个微妙的地方需要点破。上面这份代码用的是全局访问标记好处是不会绕圈、不会重复缺点是它只能找到一条路径而且找到的不一定是最短的。为什么不能找所有路径因为一旦某个格子弹栈回退mark仍然是 1它就不会再被别的分支走第二次了。如果你想要枚举所有从起点到终点的路径就得在回退的时候把mark清掉。这个改动只有一行但带来的复杂度变化是巨大的——从 O(n·m) 暴涨到指数级因为路径数量本身就可能是指数级的。所以要不要清标记不是风格问题而是你在求解什么问题的分水岭动笔之前必须想清楚。空间复杂度上栈最深是 O(n·m)mark和maze各是 O(n·m)整体 O(n·m)。很干净。4. 实操过程记录从手写到跑通代码贴出来只是结果真正的经验藏在调试过程里。这一节记录几个我反复用到的实操手法。4.1 用例设计与调试手法我强烈建议先用一个 3×3 或者 4×4 的迷你迷宫手推比如0 1 0 0 0 1 1 0 0起点左上角终点右下角。手动走一遍你会得到一条路径。然后把这份期望结果记住再跑程序对比。用大迷宫调 bug 是最笨的做法因为你根本不知道错在哪一步。第二个手法是打印每次入栈和出栈。在push和pop里各加一行输出跑小迷宫把轨迹和你的手推过程逐行对齐。我第一次写这个程序时就是因为主循环开头多写了一个pop导致路径总是少一格打印出栈轨迹后一眼就看出问题所在。这种让程序自己说话的调试方式比盯着代码干想高效十倍。第三个手法是构造特殊用例起点就是终点、起点被墙包围、终点不可达、迷宫只有一行或一列。这几个边界能覆盖绝大部分下标越界和判空错误。特别是只有一行的情况如果边界处理写得糙很容易访问到数组外。4.2 打印路径与可视化路径打印有个小技巧。栈里的元素是从栈底到栈顶的顺序也就是从起点到终点所以直接按下标从 0 遍历到top就是正序输出。但如果你在别的题目里用栈存结果弹出来自然就是逆序的需要再借助一个辅助栈或者数组倒一下。这个区分要记住。如果迷宫稍大用坐标打印看着累可以把路径画回地图里for (int i 0; i s.top; i) maze[s.data[i].x][s.data[i].y] 2; // 2 代表路径 for (int i 1; i n; i) { for (int j 1; j m; j) putchar(maze[i][j] 2 ? * : (maze[i][j] ? # : )); putchar(\n); }用*描路径、#画墙、空格表示通路一眼就能看出路径对不对。这个可视化习惯在调试稍微复杂的搜索题时价值极高因为你扫一眼就能发现路径穿墙了这种肉眼可见的逻辑错误。4.3 一次真实的踩坑记录说个我印象最深的。有一次帮朋友看他的迷宫程序症状是小迷宫全对稍大一点就报无解但那个迷宫明明有路。我查了半小时没头绪最后发现问题出在他把方向数组写成了int dir[4][2] {{1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 第三个是 {1,0}第一个和第三个方向重复了向上这个方向根本不存在。小迷宫里恰好不需要往上走所以没问题大迷宫里必须往上绕于是直接判定无解。这个 bug 的教训是方向数组这四个坐标必须是四个互不相同的单位向量写完顺手核对一遍或者干脆用注释把每个方向标出来比如// 下、右、上、左。花十秒钟注释能省半小时排查。第二个坑是标记时机。有人习惯弹出的时候标记有人习惯入栈的时候标记。正确的是入栈时就标记。如果等弹出才标记同一个格子可能被两个不同的邻格先后压入栈栈里出现重复路径长度统计就会出错严重时还会绕圈。这个顺序问题看起来只是先后之差实际影响很大。5. 常见问题与排查速查表把高频问题集中整理一下方便对着症状找原因。5.1 死循环与重复入栈症状程序卡住不结束或者栈的长度一直涨。原因几乎总是mark没起作用。可能是忘了标记可能是标记数组开小了导致越界写坏内存也可能是标记的判断条件和赋值条件不一致判断时查mark[nx][ny]赋值时写成了mark[cur.x][cur.y]自己覆盖自己。解法在入栈之前先标记再入栈两个操作紧挨着写中间不要插别的逻辑。写完通读一遍确认判断的格子和标记的格子是同一个。5.2 路径丢失与回退不干净症状程序能找到终点但打印出来的路径是断的或者长度明显不对。原因主循环里多写了pop或者moved标志的判断逻辑写反了。还有一种隐蔽情况出栈之后没有正确更新当前方向导致回到上一个点又走了同一个死路来回震荡。解法让栈顶始终代表当前位置只有四个方向都失败才弹。用一个布尔变量moved明确记录本轮有没有走成逻辑会清晰很多。5.3 递归版栈溢出症状用递归写的时候图一大就抛异常或直接崩溃。Python 报RecursionErrorC 里可能是段错误。原因每一层递归调用都占用调用栈的一帧深度等于搜索路径长度大图上轻松上千层。解法改成显式栈的迭代写法或者如果确实想用递归Python 里可以调大递归深度限制但这不是根本办法遇到几十万格的图照样崩。迭代写法是正解这也是我反复推荐它的原因之一。5.4 常见问题速查表症状最可能的原因排查动作程序不结束标记数组未生效检查入栈前是否标记判断与赋值是否同一格路径断成几截主循环多写了 pop确认是 peek 栈顶再判断只有死路才 pop明明有解却报无解方向数组重复或缺方向核对四个方向是否为四个不同单位向量小图对、大图错栈容量不足容量应开到 n×m 余量结果路径不是最短用了 DFS 而非 BFS换队列做广度优先并记录前驱非法访问/段错误边界未处理用外围加一圈墙的方式规避越界函数返回后数据错乱局部数组过大压垮调用栈把大数组移到全局或静态区6. 从迷宫往外延伸栈还能这么用迷宫只是入口把这套思维迁移出去能覆盖一大片题目。6.1 最短路径为什么栈不够用前面反复提过栈式 DFS 找到的是一条路径不保证最短。道理很直观DFS 是一条道走到黑撞到终点就返回它可能绕了一大圈而 BFS 是一圈一圈往外扩第一次碰到终点时的层数就是最短距离。想用 BFS 求最短路径做法是用队列代替栈每个节点记录从哪个节点来的前驱到达终点后从终点顺着前驱一路回溯到起点再反转就得到最短路径。这里其实又用到了栈的思想——回溯前驱的过程就是一个天然的逆序可以借助栈或者递归来完成。所以队列负责广度扩散回溯负责还原路径两者配合。这个套路在网格类题里极其常见值得单独练熟。6.2 单调栈接雨水与柱状图最大矩形栈的应用里除了回溯这一支还有一支特别能打的是单调栈。它的核心思想是维护一个栈让栈内元素保持单调递增或递减当新元素破坏了单调性时就不断弹出栈顶并结算答案。每个元素最多进栈一次、出栈一次所以整体复杂度是 O(n)比暴力枚举的 O(n²) 好得多。最典型的例子是接雨水和柱状图中最大的矩形。这两题表面上和迷宫毫无关系但底层的思维方式是相通的栈里保存的是还没被结算的状态一旦条件满足就回溯式地清算。你可以把单调栈理解成只用最近相关元素的一种回溯简化版。理解了迷宫里的压栈弹栈再学单调栈会顺很多因为你会本能地去想栈里存的到底是什么含义。6.3 括号匹配与表达式求值如果说迷宫是栈的综合应用那括号匹配就是栈的最小演示。遇到左括号压栈遇到右括号检查栈顶是否匹配、匹配就弹出最后栈空则合法。整个逻辑只有几行但它把 LIFO 的必要性展示得淋漓尽致为什么不能用队列因为括号的匹配关系是最近的未匹配左括号优先这正是栈顶的定义。表达式求值更进一步。中缀转后缀要用栈存运算符并比较优先级后缀求值要用栈存操作数。这套东西和迷宫的搜索过程看起来八竿子打不着但它们共享同一个核心动作在遇到需要回头处理的情况时用栈保存现场。这个抽象层次上的一致性才是学数据结构真正要抓住的东西。6.4 剪枝与启发式搜索的一点想法最后聊点进阶的。当迷宫图很大、还想枚举所有路径时纯 DFS 会指数级爆炸。这时就要用剪枝给搜索加一些约束提前砍掉明显不可能通向终点的分支。最简单的剪枝是维护一个从当前点到终点的曼哈顿距离如果这个距离加上已经走的步数已经超过当前已知最优解就直接放弃这条分支。这一招在求最短路径时非常有效。再进一步就是启发式搜索每次优先扩展看起来最接近终点的节点让它更快逼近目标。这套思路和迷宫同根同源只是把盲目试错换成了有方向地试错。我个人的经验是把基础的栈式 DFS 彻底吃透之后再去看这些优化会非常自然因为你清楚地知道每一步在做什么、哪一步是浪费的。反过来如果基础没打牢就上高级技巧很容易变成背模板题目稍微一变形就束手无策。最后分享一个我在实践里总结的小习惯每次写完一个栈相关的程序我都会问自己一句——栈里存的到底代表什么在迷宫题里它代表从起点到当前的整条路径在括号匹配里它代表还没被配对的左括号在单调栈里它代表还没被结算的候选边界。把这句话想清楚代码基本不会写歪因为它会约束你去一致地维护栈的语义而不是东压一个西弹一个最后自己都说不清栈里是什么。这个自问自答的习惯比记住任何一段模板代码都管用。