企业官网建设流程全解析

栈这个数据结构，课本上讲完定义和基本操作，紧接着端出来的第一个像样的大例子，十有八九就是迷宫问题。它不像括号匹配那么"一眼看穿"，也不像表达式求值那样绕，但它把栈的后进先出（LIFO）和回溯这两件事捏在了一起，第一次让人真切体会到"数据结构不是摆设，而是能决定算法能不能跑起来的关键"。这篇文章我不打算复述教材，而是把我在教学、写代码、帮人看题解过程中攒下来的东西掏出来：迷宫问题到底在考什么，栈在里面扮演什么角色，顺序栈和链栈怎么选，代码怎么从零写到能跑，跑不通的时候大概率栽在哪几个坑里，以及把它吃透之后，你还能顺手拿下接雨水、括号匹配、表达式求值这一串同类题。如果你正在学数据结构与算法，或者被递归版迷宫程序直接搞到栈溢出，这篇应该能帮你把这条线彻底理顺。

1. 先想明白：迷宫问题到底在考什么

很多人拿到迷宫题就急着敲代码，结果写了两百行还在纠结坐标怎么加。我建议先把问题抽象这一层想透，后面写起来会很轻。

1.1 从"走迷宫"到"图搜索"的抽象

把迷宫摊开看，它本质就是一个二维的网格图。每个可通行的格子是一个顶点，上下左右相邻的可通行格子之间有一条边。于是"从入口走到出口"这句话，翻译成算法语言就是：在这个图里找一条从起点到终点的路径。这个视角转换非常关键，一旦转过来，你会发现迷宫、八数码、N皇后、图的连通性判定，其实是同一类问题的不同外壳。

具体的存储约定，最经典的做法是用一个二维数组maze[n+2][m+2]，四周包一圈边界。为什么要把数组开大一圈并且在外围填满"墙"？因为这样你在判断某个方向能不能走时，就不需要额外写x>=1 && x<=n这样的边界条件了，直接看maze[nx][ny]是不是通路即可。少一个 if，就少一个出 bug 的地方，这是我特别推荐的工程化小习惯。约定上，通常设 0 表示通路、1 表示墙，或者反过来，但这个约定必须在整个程序里保持统一——我见过太多人前面用 0 表示墙，后面判断时忘了，结果程序一直在原地打转。

另外还有一个容易被忽略的点：起点和终点本身也必须是通路。有些测试用例会把终点设成墙，或者起点就是墙，程序跑出来直接无解。写代码前先在心里过一遍输入边界，比事后 debug 省事得多。

1.2 为什么偏偏是栈：LIFO 与回溯的天作之合

这是整篇文章最核心的问题：为什么用栈，而不是队列，也不是普通数组？

走迷宫的真实动作是：站在一个格子上，试着往某个方向走一步；如果能走，就过去，把当前位置"记住"；如果四个方向都走不通，说明进了死胡同，那就退回到上一个位置，换一个方向再试。这个"退回到上一个位置"的动作，正是回溯。

而"记住来时的路，并在需要时回到最近的一个位置"，恰好就是栈的行为特征。你每往前探索一步，就把它压入栈；每遇到死路，就弹出栈顶，回到上一个决策点。栈顶永远是你当前所在的位置，栈里的内容就是从起点到当前点的整条路径。这个性质漂亮在什么地方？你不需要额外维护一个"父亲指针"数组，也不需要递归调用栈帮你偷偷保存现场，路径信息本身就存在栈里，随时可以打印出来。

反过来，如果你用队列，那就是广度优先搜索（BFS），它一次探索一圈，先进先出，找出来的是最短路径（在边权都为 1 的情况下），但它没法像栈那样自然地把"当前这条路径"摊在你面前，需要额外记录前驱节点才能还原路线。所以栈和队列在这里不是谁替代谁，而是深度优先和广度优先两种策略的代表。想找一条路，栈足够；想找最短的那条，得上队列。

1.3 数据结构的整体设计

动手之前，把要用到的东西列清楚，这个习惯能省掉大量返工。我通常需要这么几样：

• 一个二维数组表示迷宫地图，外围加一圈墙；
• 一个二维标记数组mark，记录某个格子是否已经走过，防止兜圈子；
• 一个方向数组dir[4][2]，把上下左右的坐标增量预先存好，循环里直接查表，避免写四段几乎一样的代码；
• 一个栈，元素类型是坐标结构体，用来存当前路径；
• 起点终点坐标，以及一个表示"是否找到"的标志。

这里重点说方向数组。很多初学者会写：

// 不推荐的写法：四段重复逻辑 if (maze[x+1][y] == 0 && !mark[x+1][y]) { ... } if (maze[x][y+1] == 0 && !mark[x][y+1]) { ... } 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，那就是一万个元素，每个元素是一个坐标（两个 int，8 字节），总共 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 算法主循环拆解

整个搜索过程的骨架其实就四句话，我用大白话描述一遍：

1. 把起点压入栈，标记起点已访问；
2. 只要栈不空，就看一眼栈顶（注意，是先看一眼，不是立刻弹出来）：
   • 如果栈顶就是终点，成功，退出；
   • 否则依次尝试四个方向，找到第一个能走的邻格，标记它、把它压栈，然后回到第 2 步；
   • 如果四个方向都走不通，说明栈顶这个位置是死路，弹出它，回到栈里上一个位置重新尝试；
3. 循环结束时如果栈空了还没到终点，说明无解。

这里有个关键细节特别容易写错：主循环里是先 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 None

Python 版没加外围墙，边界判断写在条件里，这是两种风格，选你顺手的就行。

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 报RecursionError，C 里可能是段错误。

原因：每一层递归调用都占用调用栈的一帧，深度等于搜索路径长度，大图上轻松上千层。

解法：改成显式栈的迭代写法；或者如果确实想用递归，Python 里可以调大递归深度限制，但这不是根本办法，遇到几十万格的图照样崩。迭代写法是正解，这也是我反复推荐它的原因之一。

5.4 常见问题速查表

6. 从迷宫往外延伸：栈还能这么用

迷宫只是入口，把这套思维迁移出去，能覆盖一大片题目。

6.1 最短路径为什么栈不够用

前面反复提过，栈式 DFS 找到的是"一条"路径，不保证最短。道理很直观：DFS 是一条道走到黑，撞到终点就返回，它可能绕了一大圈；而 BFS 是一圈一圈往外扩，第一次碰到终点时的层数就是最短距离。

想用 BFS 求最短路径，做法是：用队列代替栈，每个节点记录"从哪个节点来的"（前驱），到达终点后从终点顺着前驱一路回溯到起点，再反转，就得到最短路径。这里其实又用到了栈的思想——回溯前驱的过程就是一个天然的逆序，可以借助栈或者递归来完成。所以队列负责"广度扩散"，回溯负责"还原路径"，两者配合。这个套路在网格类题里极其常见，值得单独练熟。

6.2 单调栈：接雨水与柱状图最大矩形

栈的应用里，除了回溯这一支，还有一支特别能打的是单调栈。它的核心思想是：维护一个栈，让栈内元素保持单调递增或递减，当新元素破坏了单调性时，就不断弹出栈顶并结算答案。每个元素最多进栈一次、出栈一次，所以整体复杂度是 O(n)，比暴力枚举的 O(n²) 好得多。

最典型的例子是"接雨水"和"柱状图中最大的矩形"。这两题表面上和迷宫毫无关系，但底层的思维方式是相通的：栈里保存的是"还没被结算的状态"，一旦条件满足就回溯式地清算。你可以把单调栈理解成"只用最近相关元素"的一种回溯简化版。理解了迷宫里的压栈弹栈，再学单调栈会顺很多，因为你会本能地去想"栈里存的到底是什么含义"。

6.3 括号匹配与表达式求值

如果说迷宫是栈的"综合应用"，那括号匹配就是栈的"最小演示"。遇到左括号压栈，遇到右括号检查栈顶是否匹配、匹配就弹出，最后栈空则合法。整个逻辑只有几行，但它把 LIFO 的必要性展示得淋漓尽致：为什么不能用队列？因为括号的匹配关系是"最近的未匹配左括号"优先，这正是栈顶的定义。

表达式求值更进一步。中缀转后缀要用栈存运算符并比较优先级，后缀求值要用栈存操作数。这套东西和迷宫的搜索过程看起来八竿子打不着，但它们共享同一个核心动作：在遇到"需要回头处理"的情况时，用栈保存现场。这个抽象层次上的一致性，才是学数据结构真正要抓住的东西。

6.4 剪枝与启发式搜索的一点想法

最后聊点进阶的。当迷宫图很大、还想枚举所有路径时，纯 DFS 会指数级爆炸。这时就要用剪枝：给搜索加一些约束，提前砍掉明显不可能通向终点的分支。最简单的剪枝是维护一个"从当前点到终点的曼哈顿距离"，如果这个距离加上已经走的步数已经超过当前已知最优解，就直接放弃这条分支。这一招在求最短路径时非常有效。

再进一步就是启发式搜索，每次优先扩展"看起来最接近终点"的节点，让它更快逼近目标。这套思路和迷宫同根同源，只是把"盲目试错"换成了"有方向地试错"。我个人的经验是，把基础的栈式 DFS 彻底吃透之后，再去看这些优化会非常自然，因为你清楚地知道每一步在做什么、哪一步是浪费的。反过来，如果基础没打牢就上高级技巧，很容易变成背模板，题目稍微一变形就束手无策。

最后分享一个我在实践里总结的小习惯：每次写完一个栈相关的程序，我都会问自己一句——栈里存的到底代表什么？在迷宫题里，它代表"从起点到当前的整条路径"；在括号匹配里，它代表"还没被配对的左括号"；在单调栈里，它代表"还没被结算的候选边界"。把这句话想清楚，代码基本不会写歪，因为它会约束你去一致地维护栈的语义，而不是东压一个西弹一个，最后自己都说不清栈里是什么。这个自问自答的习惯，比记住任何一段模板代码都管用。