说句实话算法竞赛里最容易被高估的一个能力不是会多少奇技淫巧而是能不能把一个基础数据结构用得又快又稳。栈、队列、树这三类结构几乎每场比赛都会出现但真正把它们写成静态数组版本的人远没有想象中多。很多选手用惯了 STL 里的 stack、queue、deque遇到数据规模到百万级、多组测试叠加、或者评测机比较老的时候才知道动态分配带来的性能账有多贵。这篇是“数据结构补充”系列的第 2 篇我把栈、队列的静态实现以及树的数组实现从头到尾讲一遍全部是竞赛中直接能抄走用的写法。1. 为什么算法竞赛里的数据结构总爱用静态写法先别急着背代码得先搞明白“静态实现”这四个字到底在解决什么问题。动态内存的核心问题有两个分配开销不可控和内存碎片不可控。你在 C 里写一句new Node底层要去找空闲内存块这个寻找过程的时间和内存布局强相关如果你在循环里反复new/delete分配器还可能越搞越慢。STL 容器也一样的std::stack默认底层是std::deque它内部按块分配内存push 多了还会触发扩容和数据搬移。竞赛题的评测往往卡得很死同样 O(n) 复杂度的操作常数差几倍就能决定你是 AC 还是 TLE。静态写法的意思就是提前规划好最大规模一次性开一个大数组然后用下标来模拟“指针”。比如栈的顶部用一个整型变量表示树的左右儿子用两个整型数组表示。这样代码中没有new、没有析构、没有迭代器所有数据都躺在连续内存里CPU 缓存命中率也高。这个思路还顺带解决了一个更现实的问题调试。用std::stack的时候你想看栈中间某个元素非常别扭但用数组栈stk[1]到stk[top]直接输出栈里存的是坐标还是值、当前容量多大一目了然。遇到越界、漏判打印几个变量就能定位。当然静态实现也不是万能。像线段树、平衡树这类结构理论上也可以用数组写但代码会变得很长。所以我把范围限定在栈、队列、树这三个最常用且最容易静态化的结构上。这三个写熟了你会发现竞赛代码的“脆感”会少很多——不用再担心容器分配内存失败不用在评测机的栈空间上赌运气。我在后面的内容里会给出具体模板和边界提醒。强烈建议你至少把数组栈、数组队列、前向星这三种写法练成肌肉记忆因为你不知道下一次比赛哪道题会突然要求你手写它们。2. 静态栈数组栈与它最常见的两个战场栈是线性结构里逻辑最简单、但竞赛应用最广的一个。表达式求值、括号匹配、单调栈、DFS 显式化、回溯搜索全都要用到它。2.1 数组栈的基本骨架和容量约定最朴素的数组栈长这样const int MAXN 1000005; int stk[MAXN]; int top 0; // top 表示栈顶元素的位置0 表示空栈 void push(int x) { stk[top] x; } void pop() { if (top 0) --top; } int getTop() { return stk[top]; } bool empty() { return top 0; }注意这里的下标是从 1 开始的。有人习惯从 0 开始top -1表示空栈也行但我强烈推荐从 1 开始因为很多竞赛题里的节点、数组、坐标都是从 1 编号的栈顶初始化为 0 之后“0 就是无效位置”这个约定能和树的空节点、图的 0 号边统一起来减少思维切换成本。容量方面别写成const int MAXN n 5这种运行时确定的写法。竞赛里必须用编译期常量直接写成1000005之类的全局数组。如果题目没给最大数据范围就多看几眼内存限制然后开一个足够大的常量并预留余量。另一个容易忽略的点是push之前我们要不要检查栈是否满答案是通常不用。因为很多题的入栈总次数不会超过最大元素个数如果你知道自己 push 的总量一定小于数组容量就不需要检查。但这不代表可以随便 push——如果你的代码存在逻辑 bug比如压栈次数是 n 的两倍那数组栈照样越界。这种越界不会像new那样直接抛异常而是悄悄踩到相邻数组比赛里表现为“莫名 WA”或者“本地正常提交就错”非常坑。所以竞赛代码里可以把push直接写成stk[top] x;但你心里要清楚这个写法成立的前提是 top 永远不会超过 MAXN-1。2.2 括号匹配把边界问题亮出来括号匹配是栈最经典的入门题但静态实现里有个很典型的细节取栈顶之前必须先判空。#include cstdio #include cstring const int MAXN 1000005; char s[MAXN]; char stk[MAXN]; int top 0; bool match(char a, char b) { return (a ( b )) || (a [ b ]) || (a { b }); } int main() { scanf(%s, s); for (int i 0; s[i]; i) { char c s[i]; if (c ( || c [ || c {) { stk[top] c; } else { if (top 0) { printf(NO\n); return 0; } if (!match(stk[top], c)) { printf(NO\n); return 0; } --top; } } printf(top 0 ? YES\n : NO\n); return 0; }这个代码里最容易犯错的地方就是漏掉if (top 0)这个分支。如果你写了char c stk[top--];当栈为空时实际访问的是stk[0]。如果栈底留着一个初始值结果可能侥幸通过如果数组是全局的stk[0]是 0恰好不匹配也能寄希望于输出 NO。可是万一题目里某种输入让空栈时碰到左括号那就直接访问垃圾数据了。我建议把match函数写成判断两两配对不要写成 ASCII 码差值之类的技巧。) - (是 1] - [是 2} - {是 2其实也可以但读代码的人一眼看过去不知道你在干什么。竞赛里“可读性”也是一种性能你自己 debug 时能少掉不少头发。2.3 单调栈数组栈真正发光的场景单调栈是栈最常考的方向比如“下一个更大元素”“柱状图中最大的矩形”“每日温度”等。它本质上就是维护一个从栈底到栈顶单调递增或递减的序列数据入栈时把不合法的元素弹出。下面是一个经典例子给一个数组 a[1..n]求每个位置右边第一个比它大的位置不存在就输出 0const int MAXN 1000005; int a[MAXN]; int stk[MAXN]; int ans[MAXN]; int top 0; for (int i n; i 1; --i) { while (top 0 a[stk[top]] a[i]) { --top; } ans[i] top 0 ? stk[top] : 0; stk[top] i; }这里我选择从右往左扫栈里存的是下标而不是值因为题目要输出位置。弹出条件用的是说明我们要找的是“严格大于”当前元素如果题目要求的是“大于等于”就改成。这种细节差一个字符答案就可能完全不同。你可能会问用std::stackint不也一样能写吗确实能但单调栈经常和输入输出、扫描、二分等操作混在一起如果栈底层动态扩容局部性差性能会差不少。数组栈在单调栈里的优势不光是快还有一个不可替代的点你可以直接基于下标随机访问栈中任意一层像单调栈配合二分时stk[mid]就能直接存取换成std::stack就得把栈先拷到临时数组里非常痛苦。单调栈的时间复杂度是 O(n)每个元素最多入栈一次、出栈一次。如果你写出来的循环看起来像 O(n^2)那一定是 while 里没有做到每个元素只被弹出一次。这是检验单调栈写法是否正确的一个重要指标。3. 静态队列环形下标、手写 deque 和 BFS队列在竞赛里比栈更依赖数组实现尤其是 BFS 和滑动窗口问题。std::queue虽然能用但在很多图形规模很大的题目里反复 push/pop 的动态分配会拖慢速度std::deque还要考虑内存块的索引机制常数更大。3.1 队列的数组约定线性还是环形最简单的是“线性队列”const int MAXN 1000005; int q[MAXN]; int head 0, tail 0; // 左闭右开head 指向队头tail 指向下一个空位 void push(int x) { q[tail] x; } void pop() { if (head tail) head; } bool empty() { return head tail; }这种写法和栈类似只要总入队次数没超过数组容量head 和 tail 就会一直向右移动不需要取模。当数据规模固定例如 BFS 一张 n×m 的网格图入队次数最多是 nm那么把数组开到 nm5它就是一个完美的队列。但有些题需要“循环队列”典型场景是队列容量有限头尾指针循环使用数组空间比如模拟 CPU 任务调度、约瑟夫环。写法很简单int q[MAXN]; int head 0, tail 0; void push(int x) { q[tail] x; tail (tail 1) % MAXN; } void pop() { head (head 1) % MAXN; } bool empty() { return head tail; }注意循环队列这种写法有一个潜在坑它无法区分队列空和队列满因为head tail既可能表示空也可能表示满。解决方案是少用一个空间或者单独用一个变量记录大小。竞赛题里如果你清楚最大元素个数我更推荐直接用线性队列少一点心智负担。3.2 滑动窗口最大值手写单调双端队列滑动窗口最大值/最小值是单调队列的经典应用也是手写 deque 最有价值的场景。给定数组 a[1..n] 和窗口长度 k求每个窗口的最大值。做法是维护一个双端队列队列里存下标且对应值从队头到队尾单调递减这样队头永远是当前窗口最大值。#include cstdio const int MAXN 1000005; int a[MAXN]; int dq[MAXN]; // 手写双端队列 int l 1, r 0; // 左闭右闭空队列时 l r int main() { int n, k; scanf(%d%d, n, k); for (int i 1; i n; i) scanf(%d, a[i]); for (int i 1; i n; i) { // 维护单调性从队尾弹出所有 a[i] 的元素 while (l r a[dq[r]] a[i]) --r; dq[r] i; // 清理不在窗口内的过期下标 while (l r dq[l] i - k) l; if (i k) printf(%d , a[dq[l]]); } return 0; }这里的清理语句是dq[l] i - k不是dq[l] i - k。因为窗口左边界是i - k 1如果队头下标小于等于i - k说明它已经滑出窗口。这个等号关系很多人会写错导致答案差一个位置。手写 deque 的核心是数组空间可以整体开成2 * MAXN初始把l放在MAXN 1r放在MAXN然后 l 向左扩展、r 向右扩展这样就不用担心 push_front 时数组下标变负数。当然如果你确定只会往尾部 push只是偶尔从头部 pop那l 1, r 0的写法就足够。我这里用的l 1, r 0是“左闭右闭”写法出队时l入队时--r和r都不会越界前提是总元素个数在数组容量之内。很多选手遇到滑动窗口问题就套std::deque能过倒是能过但一方面常数略大另一方面你没法直接在 deque 里按下标访问中间元素。如果需要配合二分手写 deque 的优势会非常明显。3.3 网格 BFS 的 tail/head 写法BFS 是队列在竞赛里最高频的出场方式。一个网格图 n×m从起点出发求到终点的最短步数队列最大长度不会超过 n*m。这种场景用线性数组队列最舒服。#include cstdio const int MAXN 1005; int n, m; char grid[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; struct Point { int x, y, step; }; Point q[MAXN * MAXN]; int head 0, tail 0; int bfs(int sx, int sy, int tx, int ty) { q[tail] {sx, sy, 0}; vis[sx][sy] true; while (head tail) { Point cur q[head]; if (cur.x tx cur.y ty) return cur.step; for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (nx 1 || nx n || ny 1 || ny m) continue; if (vis[nx][ny] || grid[nx][ny] #) continue; vis[nx][ny] true; q[tail] {nx, ny, cur.step 1}; } } return -1; }这个写法里tail和head都只是向右移动不需要取模因为入队次数有上限。它的优势是q[head]天然模拟“弹出队头”q[tail]天然模拟“压入队尾”你可以通过tail - head直接得到当前队列长度这在分层 BFS、双向 BFS 里非常有用。我特别强调一点vis 标记要在入队时立刻置 true而不是出队时再置 true。否则同一个节点可能被重复入队队列长度会膨胀甚至超时。这是 BFS 最容易翻车的地方。4. 树的静态表示左孩子右孩子、邻接表与堆树在竞赛题里要么作为显式的二叉树出现要么作为任意根的多叉树/森林出现。静态实现的关键是用数组代替指针让“递归遍历”变得非常直接。4.1 二叉树lc/rc 两个数组完成所有结构二叉树用数组实现核心就是两个整型数组lc[u]存 u 的左孩子编号rc[u]存 u 的右孩子编号0 表示空节点。const int MAXN 100005; int lc[MAXN], rc[MAXN]; int val[MAXN]; int tot 0; // 以 val 为关键字向二叉搜索树插入一个节点root 用 int 引用传递 void insert(int root, int x) { if (root 0) { root tot; val[root] x; lc[root] rc[root] 0; return; } if (x val[root]) insert(lc[root], x); else insert(rc[root], x); } int root 0; // 调用insert(root, x); void inorder(int u) { if (u 0) return; inorder(lc[u]); printf(%d , val[u]); inorder(rc[u]); }这里有个很实用的惯例把 0 号节点当作“空节点守卫”。这样lc[root]和rc[root]天然就是 0不需要额外初始化。插入时用int root引用传递函数里给root赋值就能直接修改父节点的孩子指针。如果你不太习惯引用也可以写成int insert(int root, int x)返回新的子树根但引用写法在竞赛里非常常见。不同于指针树数组二叉树有几个隐藏优点一是可以轻松实现“节点编号”和“值”分离比如一个节点既有编号又有值二是可以用lc[u]、rc[u]直接访问兄弟节点配合栈stk可以快速做迭代遍历三是整个树的大小tot就是当前用了多少个节点不需要手动 delete。4.2 多叉树和树形图前向星比 vector 更硬核任意根的多叉树或者森林一般不会开int son[MAXN][MAXCNT]这种二维数组因为孩子数量不确定空间浪费严重。竞赛里最常见的做法是前向星链式前向星它本质是用数组模拟邻接链表。const int MAXN 100005; const int MAXM 200005; // 边数上限无向树要开 2 * (n-1) int head[MAXN]; int to[MAXM]; int nxt[MAXM]; int cnt 0; void addEdge(int u, int v) { to[cnt] v; nxt[cnt] head[u]; head[u] cnt; } void dfs(int u, int fa) { for (int e head[u]; e ! 0; e nxt[e]) { int v to[e]; if (v fa) continue; dfs(v, u); } }这里最容易被坑的是MAXM。如果题目给的是无向树有 n-1 条边但你 addEdge 一次要存两个方向所以MAXM至少要2 * (n - 1) 5。很多人只开n5样例能过一提交就 RE就是因为边数组越界。如果你在写图论题我建议一律开2 * MAXN或4 * MAXN宁可多开一点别省这点内存。有人说vectorint g[MAXN]不也能过吗能过但vector每次 push_back 都可能扩容导致内存重新分配前向星只需要两个数组不涉及多次分配而且可以用cnt记录边的编号这在处理反向边、最短路、网络流问题时非常关键。前向星还支持很方便的“按边编号去重”操作比如记录边 ID 来跳过反向边。如果你只在一棵树上做 DFS用vectorint g[MAXN]其实也还好。但如果你在做树上启发式合并、树链剖分、点分治这类进阶题前向星的边编号概念会让你省很多事。我的建议是把前向星当成树的默认存储vector 留给某些动态添加边的场景。4.3 完全二叉树和堆数组就是堆本体堆是特殊的完全二叉树。因为完全二叉树的父子关系可以用下标直接计算所以堆不需要lc、rc数组用heap数组就足以表达整棵树的结构。假设堆从下标 1 开始i的父亲是i/2左孩子是2*i右孩子是2*i1。const int MAXN 100005; int heap[MAXN]; int sz 0; // 向上调整 void push(int x) { heap[sz] x; int p sz; while (p 1 heap[p] heap[p / 2]) { int tmp heap[p]; heap[p] heap[p / 2]; heap[p / 2] tmp; p / 2; } } // 向下调整 void pop() { heap[1] heap[sz--]; int p 1; while (true) { int l p * 2, r p * 2 1; int smallest p; if (l sz heap[l] heap[smallest]) smallest l; if (r sz heap[r] heap[smallest]) smallest r; if (smallest p) break; int tmp heap[p]; heap[p] heap[smallest]; heap[smallest] tmp; p smallest; } } int getMin() { return heap[1]; }这段代码是小根堆。如果你想用大根堆把所有比较符号反过来或者在值前面加负号。很多人堆排序时容易把p * 2、p * 2 1写成p 1和p 1 | 1也行但位运算可读性稍差我觉得比赛里不差这点速度写清楚更好。这里有个关键点从 0 开始索引会毁掉堆的父子关系公式。如果用 0 作为根那i的父亲是(i-1)/2左孩子是2*i1右孩子是2*i2虽然也能算但代码要比从 1 开始麻烦。竞赛里大部分和堆相关的题你直接让下标从 1 开始省心很多。堆的使用场景太广泛了优先队列优化 Dijkstra、哈夫曼树、TopK 问题、动态中位数维护。用std::priority_queue当然更快写出来但在某些要求输出堆内全部元素、或者需要自定比较函数的题里手写堆会轻松很多。更重要的是理解了数组形式的堆你就能看懂 Dijkstra 堆优化的底层原理。4.4 树的 DFS 和递归深度什么时候必须改成显式栈树的静态表示已经让你不用管节点内存了但 DFS 还存在另一个隐藏问题递归深度。如果树退化成一条链比如 n 个节点每个节点只有一个孩子那么递归 DFS 的调用栈深度是 n。而默认的递归栈空间通常在 1MB 级别深度达到 1e5 就可能爆栈评测环境直接“段错误”。这个问题在 ACM 老赛制、某些 OJ 上尤其常见。解决办法是手动模拟递归把状态压进显式栈。前序遍历最简单int stk[MAXN], top 0; stk[top] root; while (top 0) { int u stk[top--]; // 访问 u for (int e head[u]; e ! 0; e nxt[e]) { int v to[e]; if (v ! fa[u]) stk[top] v; } }这个写法只是把“先访问根再压孩子”的顺序变成了显式栈但要注意压栈顺序会影响遍历顺序。如果既要 preorder又要 postorder只用一个栈就不太够。此时可以给每个节点打一个“阶段标记”0 表示还没进入1 表示左子树处理完2 表示右子树处理完第三种状态表示可以访问并出栈。不过这会让代码变长很多。竞赛里我一般更推荐先判断题目到底需不需要后序如果只是要统计子树大小、深度、路径和很多可以改成自底向上的递推只有确实需要后序信息的场景才去写带阶段的显式栈。如果你用的是数组树而不是指针树还有一个更取巧的办法先用一次递归预处理出欧拉序或 dfs 序然后很多“树上的区间问题”就变成了数组上的区间问题不再需要深层递归。5. 深树递归爆栈的一次亲历与解决聊到树的递归我想插一个真实经历。有一回我在做一棵树的子树和统计n 是 5e5树是一个随机生成的比较平衡的形态本地测试一点问题没有。提交之后却收到 RE一开始以为是数组越界查了半天发现没有。最后在本机把一个特化的链式数据跑了一遍直接段错误才意识到是递归深度的问题。很多初学者会觉得“我的代码逻辑对啊为什么评测机说我内存越界”其实根本不是数组越界而是函数调用栈爆了。这时候最好用的工具不是 debugger而是把递归改成显式栈或者使用所谓的“栈回溯”——就是用手动维护的栈把递归一层一层完整复现出来。backtrace这个热词在算法竞赛里不太多见但在排查这种问题时你确实就是在做栈回溯。我后来养成了一个习惯看到数据规模超过 2e5 的树题先问自己一句“递归会到多深”。如果最坏深度可能达到节点数级我会直接写成显式栈 DFS省得赛后挨骂。显式栈的另一个好处是它把“访问节点”和“回溯到父节点”变成了两个显式动作方便你记录进入时间和离开时间这些时间戳在树上做差分、做离线查询时非常有用。如果你实在不想写显式栈也可以试试在 Linux 环境用ulimit -s或者编译选项调大栈空间但竞赛 OJ 的环境未必由你控制所以还是老老实实手写栈更稳妥。6. 我会直接默写的静态结构模板与边界习惯最后分享几个我用了很久的惯例。它们不是教科书上写的但能让比赛里的 bug 少很多。6.1 数组开大一点并且全部放全局竞赛类的 C 代码里大数组一定要放在函数外面因为局部数组会占用系统栈容易导致“莫名其妙 RE”。全局数组还有一个好处默认初始化为 0。这样树节点、图边的head、lc、rc自动就是 0不用挨个 memset。开数组的尺寸也很有讲究。我一般这么写栈、队列MAXN 题目最大范围 5至少留 5 个余量。二叉树lc[MAXN]、rc[MAXN]、val[MAXN]同样 5。前向星无向树MAXM 2 * MAXN再加一点点。BFS 队列如果是Point q[MAXN * MAXN]要确保MAXN * MAXN不超内存限制。这些余量不是强迫症而是很多越界其实是“只越了一点点”。比如栈顶 push 到top MAXN时你写stk[top] x依然合法0 到 MAXN-1 之外的越界但下一个 push 就会爆。缓冲区多留一点能让你把真正的问题留给逻辑而不是数组大小。6.2 多组测试的清理比我写成memset更好用的是“时间戳”很多多组数据的题目都要求每组输入重新初始化数据结构。直接memset当然可以但当数组很大1e6而测试组数极多时memset的时间会成为一个隐藏常数。一种省时间的技巧是时间戳用一个visStamp[u]数组记录“最后一次访问u是在第几组测试”每次判断时比较一下当前组号。int vis[MAXN]; int curCase 0; void solve() { curCase; // 使用时 if (vis[u] ! curCase) { vis[u] curCase; // 第一次遇到 } }这样不仅省去memset(vis,0,sizeof(vis))还能顺便表示“本组尚未访问”。类似地top、sz、cnt这些计数器在每组开始时直接重置成 0 或 1 就行不需要清空整个数组因为新写入的数据会覆盖旧数据。但要注意这种技巧只适用于“数据只依赖当期状态”的题。如果你的算法需要读历史状态那就老老实实全部初始化。6.3 静态实现的 debug 三板斧用静态数组之后debug 手段也要变。我最常做三件事打印栈/队内容for (int i 1; i top; i) printf(%d , stk[i]);看是不是符合预期序列。打印cnt或top计数器如果无限循环里cnt疯涨大概率是某个节点被重复入队/入栈。打印相邻数组边界比如head[u]和to[cnt]检查是不是有 0 号边被不小心覆盖。静态结构还有一个天然优势所有数据都在内存里连续排列你可以用一个for循环把整个数组 dump 出来这对单调栈、单调队列的调试尤其友好。STL 容器反而做不到这么直观。7. 最后再唠叨一句关于“要不要背模板”在竞赛里静态栈、静态队列、前向星、数组二叉树这四个模板我建议你还是背下来但背的是原理和边界不是代码本身。如果你面试或做题时经常被卡在“queue 为什么内存超限”“为什么递归树爆栈”“为什么 STL 版本慢”这种问题上很大程度是因为你没有亲手用数组实现过这些结构。一旦你写过stk[top] x和dq[l] ...你就能理解这些容器底层到底在干什么也更容易在赛场上根据题目规模做出选型。我个人一直以来最推荐的练习方式是每周找一两道不依赖 STL 容器的题强制自己只用手写数组栈、数组队列、前向星来写。坚持一个月你会明显感觉到自己在“控制内存”这件事上比原来稳得多。数据结构这块不怕你写得慢就怕你只会调用接口、不懂原理。把栈、队列、树这三件小事吃透后面线段树、并查集、平衡树这些进阶结构才有真正的底气。
算法竞赛必备：栈、队列、树的静态数组实现与性能优化技巧
说句实话算法竞赛里最容易被高估的一个能力不是会多少奇技淫巧而是能不能把一个基础数据结构用得又快又稳。栈、队列、树这三类结构几乎每场比赛都会出现但真正把它们写成静态数组版本的人远没有想象中多。很多选手用惯了 STL 里的 stack、queue、deque遇到数据规模到百万级、多组测试叠加、或者评测机比较老的时候才知道动态分配带来的性能账有多贵。这篇是“数据结构补充”系列的第 2 篇我把栈、队列的静态实现以及树的数组实现从头到尾讲一遍全部是竞赛中直接能抄走用的写法。1. 为什么算法竞赛里的数据结构总爱用静态写法先别急着背代码得先搞明白“静态实现”这四个字到底在解决什么问题。动态内存的核心问题有两个分配开销不可控和内存碎片不可控。你在 C 里写一句new Node底层要去找空闲内存块这个寻找过程的时间和内存布局强相关如果你在循环里反复new/delete分配器还可能越搞越慢。STL 容器也一样的std::stack默认底层是std::deque它内部按块分配内存push 多了还会触发扩容和数据搬移。竞赛题的评测往往卡得很死同样 O(n) 复杂度的操作常数差几倍就能决定你是 AC 还是 TLE。静态写法的意思就是提前规划好最大规模一次性开一个大数组然后用下标来模拟“指针”。比如栈的顶部用一个整型变量表示树的左右儿子用两个整型数组表示。这样代码中没有new、没有析构、没有迭代器所有数据都躺在连续内存里CPU 缓存命中率也高。这个思路还顺带解决了一个更现实的问题调试。用std::stack的时候你想看栈中间某个元素非常别扭但用数组栈stk[1]到stk[top]直接输出栈里存的是坐标还是值、当前容量多大一目了然。遇到越界、漏判打印几个变量就能定位。当然静态实现也不是万能。像线段树、平衡树这类结构理论上也可以用数组写但代码会变得很长。所以我把范围限定在栈、队列、树这三个最常用且最容易静态化的结构上。这三个写熟了你会发现竞赛代码的“脆感”会少很多——不用再担心容器分配内存失败不用在评测机的栈空间上赌运气。我在后面的内容里会给出具体模板和边界提醒。强烈建议你至少把数组栈、数组队列、前向星这三种写法练成肌肉记忆因为你不知道下一次比赛哪道题会突然要求你手写它们。2. 静态栈数组栈与它最常见的两个战场栈是线性结构里逻辑最简单、但竞赛应用最广的一个。表达式求值、括号匹配、单调栈、DFS 显式化、回溯搜索全都要用到它。2.1 数组栈的基本骨架和容量约定最朴素的数组栈长这样const int MAXN 1000005; int stk[MAXN]; int top 0; // top 表示栈顶元素的位置0 表示空栈 void push(int x) { stk[top] x; } void pop() { if (top 0) --top; } int getTop() { return stk[top]; } bool empty() { return top 0; }注意这里的下标是从 1 开始的。有人习惯从 0 开始top -1表示空栈也行但我强烈推荐从 1 开始因为很多竞赛题里的节点、数组、坐标都是从 1 编号的栈顶初始化为 0 之后“0 就是无效位置”这个约定能和树的空节点、图的 0 号边统一起来减少思维切换成本。容量方面别写成const int MAXN n 5这种运行时确定的写法。竞赛里必须用编译期常量直接写成1000005之类的全局数组。如果题目没给最大数据范围就多看几眼内存限制然后开一个足够大的常量并预留余量。另一个容易忽略的点是push之前我们要不要检查栈是否满答案是通常不用。因为很多题的入栈总次数不会超过最大元素个数如果你知道自己 push 的总量一定小于数组容量就不需要检查。但这不代表可以随便 push——如果你的代码存在逻辑 bug比如压栈次数是 n 的两倍那数组栈照样越界。这种越界不会像new那样直接抛异常而是悄悄踩到相邻数组比赛里表现为“莫名 WA”或者“本地正常提交就错”非常坑。所以竞赛代码里可以把push直接写成stk[top] x;但你心里要清楚这个写法成立的前提是 top 永远不会超过 MAXN-1。2.2 括号匹配把边界问题亮出来括号匹配是栈最经典的入门题但静态实现里有个很典型的细节取栈顶之前必须先判空。#include cstdio #include cstring const int MAXN 1000005; char s[MAXN]; char stk[MAXN]; int top 0; bool match(char a, char b) { return (a ( b )) || (a [ b ]) || (a { b }); } int main() { scanf(%s, s); for (int i 0; s[i]; i) { char c s[i]; if (c ( || c [ || c {) { stk[top] c; } else { if (top 0) { printf(NO\n); return 0; } if (!match(stk[top], c)) { printf(NO\n); return 0; } --top; } } printf(top 0 ? YES\n : NO\n); return 0; }这个代码里最容易犯错的地方就是漏掉if (top 0)这个分支。如果你写了char c stk[top--];当栈为空时实际访问的是stk[0]。如果栈底留着一个初始值结果可能侥幸通过如果数组是全局的stk[0]是 0恰好不匹配也能寄希望于输出 NO。可是万一题目里某种输入让空栈时碰到左括号那就直接访问垃圾数据了。我建议把match函数写成判断两两配对不要写成 ASCII 码差值之类的技巧。) - (是 1] - [是 2} - {是 2其实也可以但读代码的人一眼看过去不知道你在干什么。竞赛里“可读性”也是一种性能你自己 debug 时能少掉不少头发。2.3 单调栈数组栈真正发光的场景单调栈是栈最常考的方向比如“下一个更大元素”“柱状图中最大的矩形”“每日温度”等。它本质上就是维护一个从栈底到栈顶单调递增或递减的序列数据入栈时把不合法的元素弹出。下面是一个经典例子给一个数组 a[1..n]求每个位置右边第一个比它大的位置不存在就输出 0const int MAXN 1000005; int a[MAXN]; int stk[MAXN]; int ans[MAXN]; int top 0; for (int i n; i 1; --i) { while (top 0 a[stk[top]] a[i]) { --top; } ans[i] top 0 ? stk[top] : 0; stk[top] i; }这里我选择从右往左扫栈里存的是下标而不是值因为题目要输出位置。弹出条件用的是说明我们要找的是“严格大于”当前元素如果题目要求的是“大于等于”就改成。这种细节差一个字符答案就可能完全不同。你可能会问用std::stackint不也一样能写吗确实能但单调栈经常和输入输出、扫描、二分等操作混在一起如果栈底层动态扩容局部性差性能会差不少。数组栈在单调栈里的优势不光是快还有一个不可替代的点你可以直接基于下标随机访问栈中任意一层像单调栈配合二分时stk[mid]就能直接存取换成std::stack就得把栈先拷到临时数组里非常痛苦。单调栈的时间复杂度是 O(n)每个元素最多入栈一次、出栈一次。如果你写出来的循环看起来像 O(n^2)那一定是 while 里没有做到每个元素只被弹出一次。这是检验单调栈写法是否正确的一个重要指标。3. 静态队列环形下标、手写 deque 和 BFS队列在竞赛里比栈更依赖数组实现尤其是 BFS 和滑动窗口问题。std::queue虽然能用但在很多图形规模很大的题目里反复 push/pop 的动态分配会拖慢速度std::deque还要考虑内存块的索引机制常数更大。3.1 队列的数组约定线性还是环形最简单的是“线性队列”const int MAXN 1000005; int q[MAXN]; int head 0, tail 0; // 左闭右开head 指向队头tail 指向下一个空位 void push(int x) { q[tail] x; } void pop() { if (head tail) head; } bool empty() { return head tail; }这种写法和栈类似只要总入队次数没超过数组容量head 和 tail 就会一直向右移动不需要取模。当数据规模固定例如 BFS 一张 n×m 的网格图入队次数最多是 nm那么把数组开到 nm5它就是一个完美的队列。但有些题需要“循环队列”典型场景是队列容量有限头尾指针循环使用数组空间比如模拟 CPU 任务调度、约瑟夫环。写法很简单int q[MAXN]; int head 0, tail 0; void push(int x) { q[tail] x; tail (tail 1) % MAXN; } void pop() { head (head 1) % MAXN; } bool empty() { return head tail; }注意循环队列这种写法有一个潜在坑它无法区分队列空和队列满因为head tail既可能表示空也可能表示满。解决方案是少用一个空间或者单独用一个变量记录大小。竞赛题里如果你清楚最大元素个数我更推荐直接用线性队列少一点心智负担。3.2 滑动窗口最大值手写单调双端队列滑动窗口最大值/最小值是单调队列的经典应用也是手写 deque 最有价值的场景。给定数组 a[1..n] 和窗口长度 k求每个窗口的最大值。做法是维护一个双端队列队列里存下标且对应值从队头到队尾单调递减这样队头永远是当前窗口最大值。#include cstdio const int MAXN 1000005; int a[MAXN]; int dq[MAXN]; // 手写双端队列 int l 1, r 0; // 左闭右闭空队列时 l r int main() { int n, k; scanf(%d%d, n, k); for (int i 1; i n; i) scanf(%d, a[i]); for (int i 1; i n; i) { // 维护单调性从队尾弹出所有 a[i] 的元素 while (l r a[dq[r]] a[i]) --r; dq[r] i; // 清理不在窗口内的过期下标 while (l r dq[l] i - k) l; if (i k) printf(%d , a[dq[l]]); } return 0; }这里的清理语句是dq[l] i - k不是dq[l] i - k。因为窗口左边界是i - k 1如果队头下标小于等于i - k说明它已经滑出窗口。这个等号关系很多人会写错导致答案差一个位置。手写 deque 的核心是数组空间可以整体开成2 * MAXN初始把l放在MAXN 1r放在MAXN然后 l 向左扩展、r 向右扩展这样就不用担心 push_front 时数组下标变负数。当然如果你确定只会往尾部 push只是偶尔从头部 pop那l 1, r 0的写法就足够。我这里用的l 1, r 0是“左闭右闭”写法出队时l入队时--r和r都不会越界前提是总元素个数在数组容量之内。很多选手遇到滑动窗口问题就套std::deque能过倒是能过但一方面常数略大另一方面你没法直接在 deque 里按下标访问中间元素。如果需要配合二分手写 deque 的优势会非常明显。3.3 网格 BFS 的 tail/head 写法BFS 是队列在竞赛里最高频的出场方式。一个网格图 n×m从起点出发求到终点的最短步数队列最大长度不会超过 n*m。这种场景用线性数组队列最舒服。#include cstdio const int MAXN 1005; int n, m; char grid[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; struct Point { int x, y, step; }; Point q[MAXN * MAXN]; int head 0, tail 0; int bfs(int sx, int sy, int tx, int ty) { q[tail] {sx, sy, 0}; vis[sx][sy] true; while (head tail) { Point cur q[head]; if (cur.x tx cur.y ty) return cur.step; for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (nx 1 || nx n || ny 1 || ny m) continue; if (vis[nx][ny] || grid[nx][ny] #) continue; vis[nx][ny] true; q[tail] {nx, ny, cur.step 1}; } } return -1; }这个写法里tail和head都只是向右移动不需要取模因为入队次数有上限。它的优势是q[head]天然模拟“弹出队头”q[tail]天然模拟“压入队尾”你可以通过tail - head直接得到当前队列长度这在分层 BFS、双向 BFS 里非常有用。我特别强调一点vis 标记要在入队时立刻置 true而不是出队时再置 true。否则同一个节点可能被重复入队队列长度会膨胀甚至超时。这是 BFS 最容易翻车的地方。4. 树的静态表示左孩子右孩子、邻接表与堆树在竞赛题里要么作为显式的二叉树出现要么作为任意根的多叉树/森林出现。静态实现的关键是用数组代替指针让“递归遍历”变得非常直接。4.1 二叉树lc/rc 两个数组完成所有结构二叉树用数组实现核心就是两个整型数组lc[u]存 u 的左孩子编号rc[u]存 u 的右孩子编号0 表示空节点。const int MAXN 100005; int lc[MAXN], rc[MAXN]; int val[MAXN]; int tot 0; // 以 val 为关键字向二叉搜索树插入一个节点root 用 int 引用传递 void insert(int root, int x) { if (root 0) { root tot; val[root] x; lc[root] rc[root] 0; return; } if (x val[root]) insert(lc[root], x); else insert(rc[root], x); } int root 0; // 调用insert(root, x); void inorder(int u) { if (u 0) return; inorder(lc[u]); printf(%d , val[u]); inorder(rc[u]); }这里有个很实用的惯例把 0 号节点当作“空节点守卫”。这样lc[root]和rc[root]天然就是 0不需要额外初始化。插入时用int root引用传递函数里给root赋值就能直接修改父节点的孩子指针。如果你不太习惯引用也可以写成int insert(int root, int x)返回新的子树根但引用写法在竞赛里非常常见。不同于指针树数组二叉树有几个隐藏优点一是可以轻松实现“节点编号”和“值”分离比如一个节点既有编号又有值二是可以用lc[u]、rc[u]直接访问兄弟节点配合栈stk可以快速做迭代遍历三是整个树的大小tot就是当前用了多少个节点不需要手动 delete。4.2 多叉树和树形图前向星比 vector 更硬核任意根的多叉树或者森林一般不会开int son[MAXN][MAXCNT]这种二维数组因为孩子数量不确定空间浪费严重。竞赛里最常见的做法是前向星链式前向星它本质是用数组模拟邻接链表。const int MAXN 100005; const int MAXM 200005; // 边数上限无向树要开 2 * (n-1) int head[MAXN]; int to[MAXM]; int nxt[MAXM]; int cnt 0; void addEdge(int u, int v) { to[cnt] v; nxt[cnt] head[u]; head[u] cnt; } void dfs(int u, int fa) { for (int e head[u]; e ! 0; e nxt[e]) { int v to[e]; if (v fa) continue; dfs(v, u); } }这里最容易被坑的是MAXM。如果题目给的是无向树有 n-1 条边但你 addEdge 一次要存两个方向所以MAXM至少要2 * (n - 1) 5。很多人只开n5样例能过一提交就 RE就是因为边数组越界。如果你在写图论题我建议一律开2 * MAXN或4 * MAXN宁可多开一点别省这点内存。有人说vectorint g[MAXN]不也能过吗能过但vector每次 push_back 都可能扩容导致内存重新分配前向星只需要两个数组不涉及多次分配而且可以用cnt记录边的编号这在处理反向边、最短路、网络流问题时非常关键。前向星还支持很方便的“按边编号去重”操作比如记录边 ID 来跳过反向边。如果你只在一棵树上做 DFS用vectorint g[MAXN]其实也还好。但如果你在做树上启发式合并、树链剖分、点分治这类进阶题前向星的边编号概念会让你省很多事。我的建议是把前向星当成树的默认存储vector 留给某些动态添加边的场景。4.3 完全二叉树和堆数组就是堆本体堆是特殊的完全二叉树。因为完全二叉树的父子关系可以用下标直接计算所以堆不需要lc、rc数组用heap数组就足以表达整棵树的结构。假设堆从下标 1 开始i的父亲是i/2左孩子是2*i右孩子是2*i1。const int MAXN 100005; int heap[MAXN]; int sz 0; // 向上调整 void push(int x) { heap[sz] x; int p sz; while (p 1 heap[p] heap[p / 2]) { int tmp heap[p]; heap[p] heap[p / 2]; heap[p / 2] tmp; p / 2; } } // 向下调整 void pop() { heap[1] heap[sz--]; int p 1; while (true) { int l p * 2, r p * 2 1; int smallest p; if (l sz heap[l] heap[smallest]) smallest l; if (r sz heap[r] heap[smallest]) smallest r; if (smallest p) break; int tmp heap[p]; heap[p] heap[smallest]; heap[smallest] tmp; p smallest; } } int getMin() { return heap[1]; }这段代码是小根堆。如果你想用大根堆把所有比较符号反过来或者在值前面加负号。很多人堆排序时容易把p * 2、p * 2 1写成p 1和p 1 | 1也行但位运算可读性稍差我觉得比赛里不差这点速度写清楚更好。这里有个关键点从 0 开始索引会毁掉堆的父子关系公式。如果用 0 作为根那i的父亲是(i-1)/2左孩子是2*i1右孩子是2*i2虽然也能算但代码要比从 1 开始麻烦。竞赛里大部分和堆相关的题你直接让下标从 1 开始省心很多。堆的使用场景太广泛了优先队列优化 Dijkstra、哈夫曼树、TopK 问题、动态中位数维护。用std::priority_queue当然更快写出来但在某些要求输出堆内全部元素、或者需要自定比较函数的题里手写堆会轻松很多。更重要的是理解了数组形式的堆你就能看懂 Dijkstra 堆优化的底层原理。4.4 树的 DFS 和递归深度什么时候必须改成显式栈树的静态表示已经让你不用管节点内存了但 DFS 还存在另一个隐藏问题递归深度。如果树退化成一条链比如 n 个节点每个节点只有一个孩子那么递归 DFS 的调用栈深度是 n。而默认的递归栈空间通常在 1MB 级别深度达到 1e5 就可能爆栈评测环境直接“段错误”。这个问题在 ACM 老赛制、某些 OJ 上尤其常见。解决办法是手动模拟递归把状态压进显式栈。前序遍历最简单int stk[MAXN], top 0; stk[top] root; while (top 0) { int u stk[top--]; // 访问 u for (int e head[u]; e ! 0; e nxt[e]) { int v to[e]; if (v ! fa[u]) stk[top] v; } }这个写法只是把“先访问根再压孩子”的顺序变成了显式栈但要注意压栈顺序会影响遍历顺序。如果既要 preorder又要 postorder只用一个栈就不太够。此时可以给每个节点打一个“阶段标记”0 表示还没进入1 表示左子树处理完2 表示右子树处理完第三种状态表示可以访问并出栈。不过这会让代码变长很多。竞赛里我一般更推荐先判断题目到底需不需要后序如果只是要统计子树大小、深度、路径和很多可以改成自底向上的递推只有确实需要后序信息的场景才去写带阶段的显式栈。如果你用的是数组树而不是指针树还有一个更取巧的办法先用一次递归预处理出欧拉序或 dfs 序然后很多“树上的区间问题”就变成了数组上的区间问题不再需要深层递归。5. 深树递归爆栈的一次亲历与解决聊到树的递归我想插一个真实经历。有一回我在做一棵树的子树和统计n 是 5e5树是一个随机生成的比较平衡的形态本地测试一点问题没有。提交之后却收到 RE一开始以为是数组越界查了半天发现没有。最后在本机把一个特化的链式数据跑了一遍直接段错误才意识到是递归深度的问题。很多初学者会觉得“我的代码逻辑对啊为什么评测机说我内存越界”其实根本不是数组越界而是函数调用栈爆了。这时候最好用的工具不是 debugger而是把递归改成显式栈或者使用所谓的“栈回溯”——就是用手动维护的栈把递归一层一层完整复现出来。backtrace这个热词在算法竞赛里不太多见但在排查这种问题时你确实就是在做栈回溯。我后来养成了一个习惯看到数据规模超过 2e5 的树题先问自己一句“递归会到多深”。如果最坏深度可能达到节点数级我会直接写成显式栈 DFS省得赛后挨骂。显式栈的另一个好处是它把“访问节点”和“回溯到父节点”变成了两个显式动作方便你记录进入时间和离开时间这些时间戳在树上做差分、做离线查询时非常有用。如果你实在不想写显式栈也可以试试在 Linux 环境用ulimit -s或者编译选项调大栈空间但竞赛 OJ 的环境未必由你控制所以还是老老实实手写栈更稳妥。6. 我会直接默写的静态结构模板与边界习惯最后分享几个我用了很久的惯例。它们不是教科书上写的但能让比赛里的 bug 少很多。6.1 数组开大一点并且全部放全局竞赛类的 C 代码里大数组一定要放在函数外面因为局部数组会占用系统栈容易导致“莫名其妙 RE”。全局数组还有一个好处默认初始化为 0。这样树节点、图边的head、lc、rc自动就是 0不用挨个 memset。开数组的尺寸也很有讲究。我一般这么写栈、队列MAXN 题目最大范围 5至少留 5 个余量。二叉树lc[MAXN]、rc[MAXN]、val[MAXN]同样 5。前向星无向树MAXM 2 * MAXN再加一点点。BFS 队列如果是Point q[MAXN * MAXN]要确保MAXN * MAXN不超内存限制。这些余量不是强迫症而是很多越界其实是“只越了一点点”。比如栈顶 push 到top MAXN时你写stk[top] x依然合法0 到 MAXN-1 之外的越界但下一个 push 就会爆。缓冲区多留一点能让你把真正的问题留给逻辑而不是数组大小。6.2 多组测试的清理比我写成memset更好用的是“时间戳”很多多组数据的题目都要求每组输入重新初始化数据结构。直接memset当然可以但当数组很大1e6而测试组数极多时memset的时间会成为一个隐藏常数。一种省时间的技巧是时间戳用一个visStamp[u]数组记录“最后一次访问u是在第几组测试”每次判断时比较一下当前组号。int vis[MAXN]; int curCase 0; void solve() { curCase; // 使用时 if (vis[u] ! curCase) { vis[u] curCase; // 第一次遇到 } }这样不仅省去memset(vis,0,sizeof(vis))还能顺便表示“本组尚未访问”。类似地top、sz、cnt这些计数器在每组开始时直接重置成 0 或 1 就行不需要清空整个数组因为新写入的数据会覆盖旧数据。但要注意这种技巧只适用于“数据只依赖当期状态”的题。如果你的算法需要读历史状态那就老老实实全部初始化。6.3 静态实现的 debug 三板斧用静态数组之后debug 手段也要变。我最常做三件事打印栈/队内容for (int i 1; i top; i) printf(%d , stk[i]);看是不是符合预期序列。打印cnt或top计数器如果无限循环里cnt疯涨大概率是某个节点被重复入队/入栈。打印相邻数组边界比如head[u]和to[cnt]检查是不是有 0 号边被不小心覆盖。静态结构还有一个天然优势所有数据都在内存里连续排列你可以用一个for循环把整个数组 dump 出来这对单调栈、单调队列的调试尤其友好。STL 容器反而做不到这么直观。7. 最后再唠叨一句关于“要不要背模板”在竞赛里静态栈、静态队列、前向星、数组二叉树这四个模板我建议你还是背下来但背的是原理和边界不是代码本身。如果你面试或做题时经常被卡在“queue 为什么内存超限”“为什么递归树爆栈”“为什么 STL 版本慢”这种问题上很大程度是因为你没有亲手用数组实现过这些结构。一旦你写过stk[top] x和dq[l] ...你就能理解这些容器底层到底在干什么也更容易在赛场上根据题目规模做出选型。我个人一直以来最推荐的练习方式是每周找一两道不依赖 STL 容器的题强制自己只用手写数组栈、数组队列、前向星来写。坚持一个月你会明显感觉到自己在“控制内存”这件事上比原来稳得多。数据结构这块不怕你写得慢就怕你只会调用接口、不懂原理。把栈、队列、树这三件小事吃透后面线段树、并查集、平衡树这些进阶结构才有真正的底气。
