前几天做一个小工具里面需要缓存一批待处理的消息先发进来的先处理后发进来的排队等。手边没有合适的第三方库我索性自己写了一个队列。写的时候发现最顺手的实现方式还是数组——准确地说是动态数组。栈和队列一个是后进先出一个是先进先出这俩是数据结构里最基础的两个线性结构但真要用数组把它们实现成“容量可以自动伸缩”的版本里面还是有不少值得抠的细节。这篇文章我从头到尾讲一遍我的实现思路包含扩容缩容策略、边界处理、完整可运行的代码以及我在实际调试中踩过的几个坑。不管你是正在复习数据结构、准备面试还是工作中需要自己实现一个轻量级的栈或队列这篇文章应该都能帮到你。尤其是“动态”两个字很多人一开始用固定大小数组写一半发现容量不够才回头研究怎么扩容这其实就是本文的核心。我尽量把每一步的“为什么”也讲清楚不只是甩一段代码让你们自己看。1. 为什么我选择用数组实现动态栈和队列1.1 先用一张表看清三种方案的取舍在动手写代码之前先把方案选型这件事想明白。栈和队列常见的实现方式有三种固定容量数组、动态数组、链表。方案内存布局扩容成本缓存表现实现复杂度典型场景固定容量数组连续无扩容但满了就废极好低容量可预估且内存允许浪费动态数组连续偶发批量复制均摊O(1)极好中容量不可预估但想要高吞吐链表离散节点无复制但每次都要分配节点较差中高需要频繁拆分合并或无法预估容量固定容量数组是最容易写的但你得提前知道数据量上限而且一旦容量设大了内存就一直白白占着。链表实现的好处是不用考虑扩容每次插入动态分配一个节点就行代价是每个节点都要多存一两个指针而且节点散落在内存各处CPU缓存命中率低在高频入队出队的场景下性能差距很明显。动态数组正好站在两者中间内存连续存取速度快容量不够的时候一次性多分配一些空间容量浪费太多的时候再收缩回来。对于栈和队列这种只在一端或两端操作的结构数组实现非常自然。1.2 数组实现的真实使用场景我身边的实际场景大概有这么几类。第一类是撤销/历史记录栈。比如做一个简易编辑器每次操作把状态或命令压入栈里CtrlZ 就从栈顶弹出一个。这里如果用链表每记录一条命令就分配一次节点长时间运行内存碎片会很难看数组栈则可以预分配一块内存压栈出栈只是移动索引而已。第二类是任务调度队列。就像我开头说的那个小工具消息进来排队按顺序处理。数组队列配合动态扩容可以在消息量波动很大的情况下依然保持稳定的吞吐。对于一些嵌入式或低内存环境你还得精确控制容量动态数组反而比链表更好管理。第三类是广度优先搜索和深度优先搜索。BFS 要一个队列DFS 要一个栈算法题里经常需要手写理解了动态数组实现写起来就会很顺手。1.3 动态是核心不是装饰很多人觉得“数组实现栈和队列”很简单但加上了“动态”两个字性质就变了。固定数组只能在“满了报错”和“事先开大”之间二选一。你开到 1024结果业务高峰期来了 10 万条消息照样崩你开到 100 万条平时又只用了 10 条内存浪费了几百 KB。动态数组解决的正是这个问题平时小步快跑容量紧张时自动扩张闲置太多时自动收缩。代价是扩容和缩容都需要搬运数据所以必须设计好策略否则最坏情况下每次操作都要复制整个数组性能直接退化成 O(n)。好在只要扩容倍数选得对均摊成本可以压到常数级别这一点下一章详细讲。2. 动态容量的核心机制扩容、缩容与均摊复杂度2.1 扩容时机、扩容倍数为什么是2倍而不是固定增量扩容的触发条件很简单数组满了也就是元素个数等于容量。但容量一次扩多少这里面有讲究。假设当前容量是 m你选择每次固定增加 k 个槽位。那每次扩容都要把已有的 m 个元素复制到新数组里去。如果数据最终增长到 n扩容次数大约是 n/k 次每次复制的元素数量从 k 到 n 线性增长总的复制成本加起来是 O(n²/k)。n 一上来这个开销就非常可观。如果选择“翻倍扩容”情况就完全不同。容量从 1 翻倍到 2、4、8、16……到接近 n扩容次数只有 O(log n) 次。每次扩容复制的元素数量是当前容量所有扩容复制成本加起来约等于 2n是一个线性量级。也就是说n 次插入操作总共只额外做了大约 2n 次元素复制平均到每次插入就是常数代价。这就是大家常说的均摊 O(1)。举个例子更直观。容量从 8 起步要压入 100 万个数据只需要扩容 17 次复制总量大约 100 万个元素。如果每次固定增加 128 个槽位同样到 100 万扩容约 7820 次复制总量大约 3.9 亿次。差了三个数量级这就是“翻倍”和“固定增量”的本质区别。Java 的 ArrayList 扩容用的是 1.5 倍C 的 vector 常见是 2 倍都是为了在“扩容次数”和“内存浪费”之间找一个平衡。数学上只要倍数大于 1均摊复杂度都能维持在 O(1)但为了便于理解和教学实现我建议直接用 2 倍而且容量保持 2 的幂还有一个额外好处取模运算可以用位运算替代。2.2 缩容时机为什么阈值要低于扩容阈值一半扩容做得好缩容也得跟上否则数据量先涨后跌内存一直占着最大值不放等于白做动态。缩容的直觉方案是“元素个数少于容量一半就缩到一半”但实际这么写会出事。考虑这个序列容量 64压入 65 个元素触发扩容到 128然后弹出一个元素变成 63 个按“少于容量一半”的判断63 64触发缩容回到 64。然后再压入第 65 个又扩容到 128再弹出一个又缩容……在高位边界反复横跳每次都要整块搬运数据性能被白白浪费。正确做法是给缩容量设置一个更低的阈值让扩容和缩容之间留出缓冲区。我用的策略是元素个数小于容量的四分之一时才缩到一半。从 128 缩到 64需要元素数降到 32 以下之后要再触发扩容得又涨回 65。中间隔了 32 个元素的缓冲区间就不会反复抖动。这个机制很像空调温控的“回差”设定 26 度开制冷降到 25 度才停而不是一到 26 就反复切换。工程上这叫滞回控制在扩容缩容这种有成本的操作里非常实用。2.3 缩容和扩容都需要检查初始容量缩容还有一个容易忽视的边界不能缩到比初始容量还小。因为初始容量是你在创建结构时预估的最小可用空间如果缩容把容量缩到 1后面一个 push 又得从 1 开始疯狂扩容得不偿失。我习惯在结构体里保存一个 init_capacity 字段缩容时如果计算出的新容量小于 init_capacity就直接取 init_capacity。扩容那边也要注意整数溢出。如果你已经存了接近 INT_MAX 个元素再让 capacity * 2 就可能溢出变成负数。这种极端情况下标准做法是检查 new_capacity capacity 就知道溢出然后停止扩容或抛出异常。2.4 扩缩容是评估实现好不好的关键我面试别人的时候经常问动态数组的扩容策略。能说出“翻倍扩容、均摊 O(1)”的人不少但能同时说出“缩容阈值要低于扩容阈值防止抖动”的人就少很多了。缩容策略恰恰是工程实现和教科书代码最大的区别所在。所以后面的栈和队列实现里我都采用了这套组合满时翻倍扩容少到四分之一时减半缩容容量不低于初始值。这套规则在大多数业务场景下表现都很稳。3. 数组实现动态栈完整代码与边界处理3.1 栈的接口设计与字段定义栈是单口操作的结构只需要四个核心操作压栈、出栈、取栈顶、判空。我用 C 语言写一个最小实现因为这个结构足够底层能看到内存分配和释放的全过程换成 Java、Python、Go 也都能无缝迁移。#include stdio.h #include stdlib.h typedef struct { int *data; int top; // 指向栈顶元素的下一位置空栈时为 0 int capacity; // 当前容量 int init_capacity; } DynamicStack;这里 top 的语义我选择“指向栈顶元素的下一位置”也就是空栈时 top 为 0。另一种方案是让 top 指向栈顶元素本身空栈时 top 为 -1。两种都能用但前者在数组里更容易理解和计算因为元素实际存储在 data[0] 到 data[top - 1]。3.2 入栈出栈取栈顶的边界处理入栈之前先检查是否已满满了就执行扩容。出栈之前必须判空空栈出栈是一个未定义行为在所有语言里都应该被挡在门外。void stack_push(DynamicStack *s, int value) { if (s-top s-capacity) { if (stack_grow(s) ! 0) { // 扩容失败这里根据业务决定如何处理 return; } } s-data[s-top] value; s-top; } int stack_pop(DynamicStack *s) { // 调用方需要提前用 stack_is_empty 判空 s-top--; int value s-data[s-top]; stack_maybe_shrink(s); return value; } int stack_top(DynamicStack *s) { // 调用方需要提前用 stack_is_empty 判空 return s-data[s-top - 1]; }出栈后我调用了 stack_maybe_shrink这一步会检查是否需要缩容。这里有个陷阱如果缩容失败我的实现是忽略错误继续返回因为数据本身还是合法的只是容量没有收缩不会影响栈的正确性。3.3 完整可运行的动态栈代码下面是完整的动态栈实现包含扩容和缩容逻辑。这是我实际调试过的版本可以直接编译运行。#include stdio.h #include stdlib.h typedef struct { int *data; int top; int capacity; int init_capacity; } DynamicStack; void stack_init(DynamicStack *s, int init_capacity) { if (init_capacity 4) { init_capacity 4; } s-data (int *)malloc(sizeof(int) * init_capacity); if (!s-data) { fprintf(stderr, memory allocation failed\n); exit(1); } s-top 0; s-capacity init_capacity; s-init_capacity init_capacity; } void stack_destroy(DynamicStack *s) { free(s-data); s-data NULL; s-top 0; s-capacity 0; } int stack_is_empty(DynamicStack *s) { return s-top 0; } int stack_size(DynamicStack *s) { return s-top; } static int stack_grow(DynamicStack *s) { int new_capacity s-capacity * 2; if (new_capacity s-capacity) { // 整数溢出检查 return -1; } int *new_data (int *)realloc(s-data, sizeof(int) * new_capacity); if (!new_data) { return -1; } s-data new_data; s-capacity new_capacity; return 0; } static int stack_maybe_shrink(DynamicStack *s) { if (s-capacity s-init_capacity) { return 0; } if (s-top s-capacity / 4) { return 0; } int new_capacity s-capacity / 2; if (new_capacity s-init_capacity) { new_capacity s-init_capacity; } int *new_data (int *)realloc(s-data, sizeof(int) * new_capacity); if (!new_data) { return -1; } s-data new_data; s-capacity new_capacity; return 0; } void stack_push(DynamicStack *s, int value) { if (s-top s-capacity) { if (stack_grow(s) ! 0) { fprintf(stderr, stack grow failed\n); return; } } s-data[s-top] value; s-top; } int stack_pop(DynamicStack *s) { s-top--; int value s-data[s-top]; stack_maybe_shrink(s); return value; } int stack_top(DynamicStack *s) { return s-data[s-top - 1]; }注意这里的 realloc 用了一个临时变量接收返回值我没有直接写成s-data realloc(...)。理由是 realloc 失败时会返回 NULL如果直接赋值原指针就丢了旧内存既没释放也没法访问等于泄漏加数据丢失。这个问题在真实项目里一旦发生非常隐蔽。3.4 代码里的边界检查清单整理一下动态栈必须守住的边界条件空栈时不能 pop、不能 top。扩容时如果已经是满的要先扩容再写入。缩容时不能低于 init_capacity。容量翻倍时检查整数溢出。realloc 返回值要用临时变量承接。如果栈中存储的是引用类型比如 Java 的 Object、C 语言里的指针弹出后要把原位置置空否则数组还持有着引用GC 或内存管理器无法回收相关对象。Java 里类似这样处理public int pop() { int value data[--size]; data[size] 0; // 如果 data 是 Object[]这里应设为 null return value; }这个细节在 Java 里尤其重要。之前有人调试内存占用越来越高数据量看起来不大但垃圾收集器一直无法回收最后发现是数组弹出元素后没有清除引用导致一堆本该销毁的对象被数组的引用链牢牢拽着。4. 数组实现动态队列环形队列与可搬移线性队列4.1 线性数组队列的“假溢出”问题栈只有一端操作数组实现很直接。队列不一样它有两端出队从头部出入队从尾部进。如果还是按“头部从下标 0 开始尾部往后走”的朴素思路马上会遇到问题。假设容量是 8先入队 8 个元素再出队 5 个此时 head 指向下标 5tail 指向下标 8。数组前 5 个位置空着但 tail 已经顶到尾部新元素进不来了。这就是典型的“假溢出”明明前面有空间却因为指针只能往后走浪费掉了。解决假溢出的办法有两个方向一个是把数组首尾相接做成环形另一个是在入队时发现 tail 到底了就把剩余元素整体搬到数组头部。环形队列是主流方案搬移方案代码更直观我两个都讲。4.2 环形队列字段约定、判满判空、扩容复制环形队列的核心是“逻辑上把数组看成一个环”tail 到达数组末尾后通过取模操作绕回到开头。typedef struct { int *data; int head; // 指向队头元素 int tail; // 指向下一个入队位置 int size; // 当前元素个数 int capacity; int init_capacity; } DynamicQueue;我单独维护了一个 size 字段用来判空判满这样就不需要浪费一个存储位也不需要纠结“tail 1 head 才满”这种容易混淆的写法。判空size 0判满size capacity入队操作void queue_push(DynamicQueue *q, int value) { if (q-size q-capacity) { queue_resize(q, q-capacity * 2); } q-data[q-tail] value; q-tail (q-tail 1) % q-capacity; q-size; }出队操作int queue_pop(DynamicQueue *q) { int value q-data[q-head]; q-head (q-head 1) % q-capacity; q-size--; if (q-size q-capacity / 4) { queue_resize(q, q-capacity / 2); } return value; }4.3 环形队列完整代码环形队列最难的部分是扩容时的数据搬移。因为逻辑顺序和物理存储顺序不一致你不能直接 memcpy 整块内存必须按逻辑顺序从头到尾逐个复制。static int queue_resize(DynamicQueue *q, int new_capacity) { if (new_capacity q-init_capacity) { new_capacity q-init_capacity; } if (new_capacity q-size) { return -1; } int *new_data (int *)malloc(sizeof(int) * new_capacity); if (!new_data) { return -1; } for (int i 0; i q-size; i) { new_data[i] q-data[(q-head i) % q-capacity]; } free(q-data); q-data new_data; q-head 0; q-tail q-size; q-capacity new_capacity; return 0; }这个函数同时处理扩容和缩容不管是变大变小核心逻辑都是同一个先把数据按逻辑顺序复制到新数组的头部再把 head 和 tail 重置。这里是我之前踩坑最多的地方后面详细说。完整的队列初始化、入队、出队、销毁代码如下#include stdio.h #include stdlib.h typedef struct { int *data; int head; int tail; int size; int capacity; int init_capacity; } DynamicQueue; void queue_init(DynamicQueue *q, int init_capacity) { if (init_capacity 4) { init_capacity 4; } q-data (int *)malloc(sizeof(int) * init_capacity); if (!q-data) { fprintf(stderr, memory allocation failed\n); exit(1); } q-head 0; q-tail 0; q-size 0; q-capacity init_capacity; q-init_capacity init_capacity; } void queue_destroy(DynamicQueue *q) { free(q-data); q-data NULL; q-head 0; q-tail 0; q-size 0; q-capacity 0; } int queue_is_empty(DynamicQueue *q) { return q-size 0; } int queue_size(DynamicQueue *q) { return q-size; } void queue_push(DynamicQueue *q, int value) { if (q-size q-capacity) { if (queue_resize(q, q-capacity * 2) ! 0) { fprintf(stderr, queue grow failed\n); return; } } q-data[q-tail] value; q-tail (q-tail 1) % q-capacity; q-size; } int queue_pop(DynamicQueue *q) { int value q-data[q-head]; q-head (q-head 1) % q-capacity; q-size--; if (q-size q-capacity / 4) { queue_resize(q, q-capacity / 2); } return value; }4.4 可搬移线性队列另一种务实做法如果不搞环形也可以在做入队时检查“tail 是否已经到底”。如果 tail 到底了而 head 前面还有空间就把剩余元素整体搬到数组开头然后重置 head 和 tail。void queue_push_linear(DynamicQueue *q, int value) { if (q-size q-capacity) { queue_resize(q, q-capacity * 2); } if (q-tail q-capacity q-head 0) { for (int i 0; i q-size; i) { q-data[i] q-data[q-head i]; } q-head 0; q-tail q-size; } q-data[q-tail] value; q-tail; q-size; }这种方案的优点是非常直观物理位置就是逻辑顺序调试方便也不需要考虑取模。缺点是入队可能有偶发的 O(n) 搬移成本不过在均摊意义下仍然是 O(1)适合数据生命周期短、规模不大的场景。4.5 两种队列方案怎么选维度环形队列可搬移线性队列常态操作性能无额外搬移最优偶发搬移但次数可控实现难度较高涉及取模和逻辑复制较低思路直白调试复杂度较高扩容时容易错乱低状态直观适用场景高吞吐、长期运行、缓冲场景教学实现、短生命周期队列我的建议是环形队列值得花时间搞懂因为很多语言底层都在用类似的结构。Java 的 ArrayDeque 内部就是环形数组网络库里的环形缓冲区、日志系统的异步缓冲也都是这个思路。搞懂了环形队列很多“缓冲区”类问题都可以直接套用。5. 实战中的坑与性能体验5.1 排查实录缩容抖动我最早给队列写缩容时阈值取的是“元素个数小于容量一半就缩容”测试时发现一个问题在同一个数据量附近来回压入弹出容量会不停地在 64 和 128 之间反复横跳每次跳变都是一次完整的数组复制。操作次数多了整体耗时从不到 1 秒变成十几秒差距非常吓人。后来我把缩容阈值改成四分之一抖动立刻消失了。实测中注意观察“扩容次数”这个指标如果它在某一阶段异常增多多半就是阈值设计有问题。5.2 排查实录环形队列扩容时的顺序复制错误环形队列扩容时我最开始图省事直接用 memcpy 把旧数组的物理内存复制到新数组。结果队列出队的顺序完全乱了队头变成了一段乱七八糟的数据。原因很简单环形状态下逻辑顺序可能是“下标 3 到 7再回到 0 到 2”但物理内存顺序就是 0 到 7。直接复制物理内存相当于把环形展开成了另一种错误排列。后来改成按逻辑顺序逐元素复制问题才解决。这个坑很隐蔽因为很多情况下 head 恰好是 0物理顺序和逻辑顺序重合测试就过了。但只要做连续的出队再入队head 偏移后逻辑顺序错开就会暴露。测试时一定覆盖这种场景。5.3 排查实录内存泄漏与引用清理另一个印象深刻的坑是在 Java 版本里。栈的元素是 Object 数组pop 只是把 size 减一没有把 data[size] 置为 null。表现上看功能完全正常数据都能取到但跑了几个小时内存占用只升不降。最后定位到是数组的引用链把弹出的对象一直拽着GC 没办法回收。这个问题在 C 语言里更加直接如果栈里存的是指针pop 之后如果不把原槽位置空那块内存就无法被重新利用甚至可能导致重复释放。不管什么语言只要元素是引用类型pop 之后把原槽位清空是个好习惯。5.4 常见问题速查表现象可能原因解决办法容量反复横跳、性能骤降缩容阈值过高改为 size capacity / 4 时缩容环形队列出队顺序错乱扩容时直接复制物理内存按逻辑顺序逐元素复制内存占用持续上升引用类型元素未置空pop 后将原槽位置 nullrealloc 后数据丢失未用临时变量接收返回值先暂存 realloc 结果再赋值容量翻倍变成负数整数溢出检查 new_capacity capacity并发环境下结构污染多个线程同时 push/pop加锁或使用标准库并发容器5.5 一组直觉性的性能数据与扩容次数统计我用一个简单的方法评估扩容策略不依赖具体机器只需要数“复制元素的总次数”。容量从 8 起步连续压入 100 万个数据。翻倍扩容扩容 17 次复制总量约 100 万个元素。也就是说压入 100 万个元素的整个过程额外复制成本约等于又把整个数组复制了一遍均摊到每次插入约 1 次复制。固定增量扩容每次增加 128 个槽位扩容约 7820 次复制总量约 3.9 亿个元素。均摊到每次插入约 390 次复制。差距就是这么大。所以以后看到“动态数组插入是 O(1)”这种说法心里要有数它说的是均摊复杂度前提正是扩容翻倍。如果你的项目里用到的动态数组性能异常先检查扩容策略十有八九是这里出了问题。最后再分享一个小建议。代码这种东西看十遍不如上手调试一遍。建议你把缩容阈值改成二分之一跑一遍再把扩容倍数改成 1.5 或固定增量跑一遍在每次扩容前后打印容量和复制次数。数据会非常直观地告诉你为什么标准实践是翻倍扩容加滞回缩容。我自己就是通过这种“故意写错再观察现象”的方式才真正把这些边界条件和性能特性焊死在脑子里的。动态栈和动态队列写完之后你会发现自己对语言自带容器的很多行为一下子就想通了。以后再遇到“为什么列表扩容之后地址变了”“为什么队列在高频入队出队时不卡顿”这类问题你会有一种很踏实的掌控感。