动态数组实现栈与队列：扩容缩容策略与工程实践

前几天做一个小工具，里面需要缓存一批待处理的消息，先发进来的先处理，后发进来的排队等。手边没有合适的第三方库，我索性自己写了一个队列。写的时候发现，最顺手的实现方式还是数组——准确地说，是动态数组。

栈和队列，一个是后进先出，一个是先进先出，这俩是数据结构里最基础的两个线性结构，但真要用数组把它们实现成“容量可以自动伸缩”的版本，里面还是有不少值得抠的细节。这篇文章我从头到尾讲一遍我的实现思路，包含扩容缩容策略、边界处理、完整可运行的代码，以及我在实际调试中踩过的几个坑。

不管你是正在复习数据结构、准备面试，还是工作中需要自己实现一个轻量级的栈或队列，这篇文章应该都能帮到你。尤其是“动态”两个字，很多人一开始用固定大小数组，写一半发现容量不够，才回头研究怎么扩容，这其实就是本文的核心。

我尽量把每一步的“为什么”也讲清楚，不只是甩一段代码让你们自己看。

1. 为什么我选择用数组实现动态栈和队列

1.1 先用一张表看清三种方案的取舍

在动手写代码之前，先把方案选型这件事想明白。栈和队列常见的实现方式有三种：固定容量数组、动态数组、链表。

固定容量数组是最容易写的，但你得提前知道数据量上限，而且一旦容量设大了，内存就一直白白占着。链表实现的好处是不用考虑扩容，每次插入动态分配一个节点就行，代价是每个节点都要多存一两个指针，而且节点散落在内存各处，CPU缓存命中率低，在高频入队出队的场景下性能差距很明显。

动态数组正好站在两者中间：内存连续，存取速度快，容量不够的时候一次性多分配一些空间；容量浪费太多的时候再收缩回来。对于栈和队列这种只在一端或两端操作的结构，数组实现非常自然。

1.2 数组实现的真实使用场景

我身边的实际场景大概有这么几类。

第一类是撤销/历史记录栈。比如做一个简易编辑器，每次操作把状态或命令压入栈里，Ctrl+Z 就从栈顶弹出一个。这里如果用链表，每记录一条命令就分配一次节点，长时间运行内存碎片会很难看；数组栈则可以预分配一块内存，压栈出栈只是移动索引而已。

第二类是任务调度队列。就像我开头说的那个小工具，消息进来排队，按顺序处理。数组队列配合动态扩容，可以在消息量波动很大的情况下依然保持稳定的吞吐。对于一些嵌入式或低内存环境，你还得精确控制容量，动态数组反而比链表更好管理。

第三类是广度优先搜索和深度优先搜索。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 指向下标 5，tail 指向下标 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 常见问题速查表

5.5 一组直觉性的性能数据与扩容次数统计

我用一个简单的方法评估扩容策略，不依赖具体机器，只需要数“复制元素的总次数”。

容量从 8 起步，连续压入 100 万个数据。

• 翻倍扩容：扩容 17 次，复制总量约 100 万个元素。也就是说，压入 100 万个元素的整个过程，额外复制成本约等于又把整个数组复制了一遍，均摊到每次插入约 1 次复制。
• 固定增量扩容：每次增加 128 个槽位，扩容约 7820 次，复制总量约 3.9 亿个元素。均摊到每次插入，约 390 次复制。

差距就是这么大。所以以后看到“动态数组插入是 O(1)”这种说法，心里要有数：它说的是均摊复杂度，前提正是扩容翻倍。如果你的项目里用到的动态数组性能异常，先检查扩容策略，十有八九是这里出了问题。

最后再分享一个小建议。代码这种东西，看十遍不如上手调试一遍。建议你把缩容阈值改成二分之一跑一遍，再把扩容倍数改成 1.5 或固定增量跑一遍，在每次扩容前后打印容量和复制次数。数据会非常直观地告诉你，为什么标准实践是翻倍扩容加滞回缩容。我自己就是通过这种“故意写错再观察现象”的方式，才真正把这些边界条件和性能特性焊死在脑子里的。

动态栈和动态队列写完之后，你会发现自己对语言自带容器的很多行为一下子就想通了。以后再遇到“为什么列表扩容之后地址变了”“为什么队列在高频入队出队时不卡顿”这类问题，你会有一种很踏实的掌控感。