1. 为什么还要手写动态栈与队列看似基础实则处处是分水岭先说个我之前带人时遇到的真实情况。有同事用vector写栈用deque写队列业务跑得飞快当时我也觉得STL 都封装好了谁还手写容器直到后来做某个内存受限的嵌入式模块不能用标准库只能自己管内存这时候才发现如果平时只停留在调用层面一旦脱离现成容器连动态扩容这种最基本的东西都可能写出一堆边界 Bug。所以我一直认为用数组实现动态栈与队列不是让你重复造轮子而是逼你搞清楚三件事数据怎么存、空间不够了怎么办、头尾指针到底怎么转。这三件事弄明白了你回头看 STL 里的stack、queue、vector、deque会突然觉得源码没那么神秘面试被问到底层怎么实现也不会只能背个动态数组的结论。而且数组实现栈和队列本身是两种完全不同的思维量级。栈是一头操作逻辑最简单但动态扩容时有个非常经典的隐患如果你用栈顶指针 当前元素个数这种设计扩容后元素拷贝是线性的容易可如果你用栈顶指针永远指向下一个空位或者栈顶指针指向最后一个元素扩容前后指针语义必须保持一致差一个单位压栈就错位。队列就复杂得多。因为队列是一头进、另一头出如果直接复用栈的低地址端固定思路出队后头部空间就浪费了。于是有了环形缓冲区这种设计头尾指针都能往后走走到数组末尾就绕回开头。听上去就是取模两个字但真写起来空队列和满队列怎么区分头尾指针初始值怎么定取模操作会不会拖慢性能这些全是坑。标题叫数组实现动态栈与队列说白了就是让你用最简单的一维数组把这两类数据结构从底层重新长出来。今天这篇文章我会直接用 C 语言讲因为 C 没有 STL 兜底所有内存、指针、边界都得自己面对最能暴露问题。如果你用 C/Java思路完全通用只是把malloc/free换成new/delete或ArrayList而已。我不会给你贴一个完美版本就算完事。我会按照设计结构体 → 写初始化 → 写扩容 → 写核心操作 → 跑测试 → 对比优化的顺序一步步把代码写出来并且把那些只看源码根本看不出来的坑逐个用大白话讲清楚。2. 先写动态栈从结构体设计到扩容链路2.1 结构体设计的两种栈顶指针流派数组实现栈第一步是定义结构体。很多初学者喜欢直接搞一个全局数组加一个全局变量top但这样既不支持多实例也没法在函数间安全传递。我建议用结构体封装typedef struct { int *data; // 指向堆上动态数组 int capacity; // 当前容量 int top; // 栈顶下标 } DynamicStack;这里最关键的是top的含义。我见过程序员写栈top至少有三种理解top表示栈顶元素的下标。空栈时top -1压栈时先top再赋值。top表示下一个空位的下标。空栈时top 0压栈时先赋值再top。干脆用size表示元素个数不叫top。这三种写法都能 work但一旦牵涉到扩容我们必须明确一个原则扩容函数绝不应该关心栈顶指针的语义之外的事情它只负责把数组变大然后把旧数据搬过去最后保证top的含义不变。听起来像废话实际特别容易出 Bug。我习惯用第 2 种top指向下一个空位空栈时top 0。为什么因为用size理解栈非常自然打印、判空、取栈顶都少一次1/-1的混淆。// 初始化 void initStack(DynamicStack *s, int initCapacity) { s-data (int *)malloc(sizeof(int) * initCapacity); s-capacity initCapacity; s-top 0; } // 判空 int isEmptyStack(DynamicStack *s) { return s-top 0; }2.2 扩容的核心别让 realloc 毁掉你的指针语义压栈前先判断容量。满的时候就需要扩容。常见做法是倍增扩容也就是新容量 旧容量 × 2。为什么是 2 而不是每次加 10因为如果每次固定增加 10 个元素假设从 10 扩到 1000需要扩容 99 次每次都要搬移旧数据总搬移量是 O(n²)而倍增扩容总搬移量是 O(n)均摊下来每次压栈是 O(1)。这是动态数组性能的关键。代码有两种写法写法 Arealloc 直接扩void pushStack(DynamicStack *s, int val) { if (s-top s-capacity) { int newCap s-capacity * 2; int *tmp (int *)realloc(s-data, sizeof(int) * newCap); if (tmp NULL) { // 处理失败原数组仍有效 return; } s-data tmp; s-capacity newCap; } s-data[s-top] val; }写法 B手动 malloc 拷贝 freevoid pushStack(DynamicStack *s, int val) { if (s-top s-capacity) { int newCap s-capacity * 2; int *newData (int *)malloc(sizeof(int) * newCap); if (newData NULL) return; for (int i 0; i s-top; i) { newData[i] s-data[i]; } free(s-data); s-data newData; s-capacity newCap; } s-data[s-top] val; }在实际项目中我更推荐写法 B尤其在嵌入式或内存碎片敏感的环境里。写 A 看起来省事但realloc有几个隐藏行为如果原地扩不了它会在别处分配新内存并把旧数据搬过去然后自动释放旧内存如果连新内存都分配失败它返回NULL但旧内存依然有效。所以上面代码里用tmp接收返回值而不是直接s-data realloc(...)否则失败后原指针就丢了。而 B 的逻辑完全可控每一步都清清楚楚代价只是多一次循环拷贝——但扩容本身是低频操作这点开销无所谓。还有一个扩容参数问题扩容因子到底取 2 还是 1.5如果取 2容量会迅速变大内存可能浪费如果取 1.5扩容更频繁但内存更紧凑。实际项目中两者都有应用场景如果你不确定用 2 最稳因为位运算里newCap oldCap 1比乘法更快虽然是毫秒级差别但至少看着专业。2.3 压栈、弹栈、取栈顶的正确姿势核心操作写出来其实很短但必须注意细节void pushStack(DynamicStack *s, int val) { if (s-top s-capacity) { int newCap s-capacity * 2; int *newData (int *)malloc(sizeof(int) * newCap); if (newData NULL) { printf(扩容失败压栈中止\n); return; } for (int i 0; i s-top; i) { newData[i] s-data[i]; } free(s-data); s-data newData; s-capacity newCap; } s-data[s-top] val; } int popStack(DynamicStack *s) { if (isEmptyStack(s)) { // 这里看需求要么报错要么返回一个约定值 printf(栈空无法弹出\n); return -1; // 假设元素都是非负 } return s-data[--s-top]; } int peekStack(DynamicStack *s) { if (isEmptyStack(s)) { printf(栈空无栈顶元素\n); return -1; } return s-data[s-top - 1]; }注意popStack里我用的是--s-top而不是s-top--。因为top指向的是下一个空位弹栈时应该先把top减 1再返回那个位置上的元素。如果你写反了第一次弹出的是空位上的脏数据整个栈就乱了。还有一个容易被忽略的点弹栈后旧值还残留在数组里。如果元素是int还好如果将来改成char*或指针类型你不把s-data[s-top] NULL清掉就会造成内存泄漏或悬挂指针。所以更严谨的写法是int popStack(DynamicStack *s) { if (isEmptyStack(s)) return -1; int val s-data[--s-top]; s-data[s-top] 0; // 清掉残留 return val; }这不是强迫症而是数据结构通用素养你管理的每块内存生命周期都要干净。2.4 销毁与重置不写析构等于白写栈动态数组栈用完了必须释放void destroyStack(DynamicStack *s) { free(s-data); s-data NULL; s-capacity 0; s-top 0; }为什么s-data要置NULL因为在多函数协作的项目里万一有人不小心再次destroyStackfree(NULL)是安全的但如果指针变成野指针第二次free会直接崩溃。这是防御性编程的基本习惯。到这里动态栈就完整写完了。从结构体、初始化、扩容、压栈、弹栈、取顶、销毁一共 7 个函数逻辑闭环。接下来是更刺激的部分动态队列。3. 动态队列环形数组才是真正的重头戏3.1 为什么普通数组做队列会假满如果直接用头指针固定、尾指针后移的普通数组做队列出队时头部元素被移走但front还是指向原来的位置导致大量空间浪费最终队列明明没满却因为 rear 到了数组末尾而无法入队。这就是假满。解决假满的方案有两个方案 1出队时把后面所有元素往前搬。每次出队 O(n)太慢直接淘汰。方案 2把数组想象成一个环形rear 到了末尾就绕回开头。这就是环形缓冲区circular buffer也是我在实际项目里最常用的队列实现。环形队列的每一块内存都被复用只要队列里元素个数没到容量上限就能一直入队。3.2 环形队列的结构体与头尾指针约定typedef struct { int *data; int capacity; int front; // 队头元素的下标 int rear; // 队尾下一个空位的下标 int size; // 当前元素个数 } DynamicQueue;这里的front指向队头元素rear指向队尾的下一个空位。空队列时front rear 0满队列时(rear 1) % capacity front。但为了区分空和满我建议额外维护一个size字段这样判空size 0判满size capacity不需要浪费一个存储位置也不需要用牺牲一格的老办法逻辑非常直白。3.3 入队出队取模运算背后的边界陷阱入队操作首先要判断是否满满则扩容。扩容的时候环形队列的搬移就不能像栈那样直接从头拷到尾了因为front不一定在数组下标 0 的位置。这是环形队列实现里最容易写错的一个点。我先给一个非扩容版本让你看清取模逻辑void enqueue(DynamicQueue *q, int val) { if (q-size q-capacity) { // 扩容稍后讲 } q-data[q-rear] val; q-rear (q-rear 1) % q-capacity; q-size; } int dequeue(DynamicQueue *q) { if (q-size 0) { printf(队列空无法出队\n); return -1; } int val q-data[q-front]; q-data[q-front] 0; q-front (q-front 1) % q-capacity; q-size--; return val; }这里有个非常隐蔽的问题q-rear (q-rear 1) % q-capacity中取模只在rear 1 capacity时才有意义其他时候% capacity等于没变化但 CPU 会执行一次除法指令。极高频入队场景下这也是一点性能损耗。优化写法是q-rear; if (q-rear q-capacity) { q-rear 0; }或者用位运算capacity保持 2 的幂q-rear (q-rear 1) (q-capacity - 1);我个人在实际项目中偏爱最后一种前提是把capacity始终控制为 2 的整数次幂。为什么因为运算比%快一个量级而且代码意图清晰。这个优化会在后面的性能对比里看到效果。3.4 环形队列扩容的正确搬移方式这是今天最值得细看的地方。假如当前capacity 5队列里有 3 个元素front 3rear 1。元素在数组中的分布是下标 3、4、0 各有一个元素。现在要扩容到 10你不能简单地把data[0..size-1]拷贝过去因为front不在 0。正确处理方法是按队列的逻辑顺序从front开始逐个取出元素放到新数组的前size个位置然后再让front 0rear size。void resizeQueue(DynamicQueue *q, int newCap) { int *newData (int *)malloc(sizeof(int) * newCap); if (newData NULL) return; for (int i 0; i q-size; i) { newData[i] q-data[(q-front i) % q-capacity]; } free(q-data); q-data newData; q-capacity newCap; q-front 0; q-rear q-size; }这个(q-front i) % q-capacity就是环形访问的核心。你每次从旧队列的逻辑头部开始跳过可能的环形空隙依次取出元素放置到新数组的线性头部于是新数组变成了一段从头开始、连续排列的队列。这个操作做完后front 0和rear size就保证了新的环形结构正确。同样的扩容因子我建议选择 2。新容量最好也处理成 2 的幂方便后续位运算替代取模。完整的入队扩容版本void enqueue(DynamicQueue *q, int val) { if (q-size q-capacity) { resizeQueue(q, q-capacity * 2); } q-data[q-rear] val; q-rear (q-rear 1) (q-capacity - 1); // 前提capacity 是 2 的幂 q-size; }是不是看起来很简洁但这里的 (q-capacity - 1)有一个前提capacity必须是 2 的幂。所以我通常在初始化时把用户传入的初始容量自动向上取整到最近的 2 的幂int roundToPowerOfTwo(int n) { int cap 1; while (cap n) cap 1; return cap; } void initQueue(DynamicQueue *q, int initCapacity) { int cap roundToPowerOfTwo(initCapacity); q-data (int *)malloc(sizeof(int) * cap); q-capacity cap; q-front 0; q-rear 0; q-size 0; }3.5 队列销毁与重置void destroyQueue(DynamicQueue *q) { free(q-data); q-data NULL; q-capacity 0; q-front 0; q-rear 0; q-size 0; }到这里动态栈和动态队列的核心实现都齐了。但光有代码还不够我们必须验证扩容前后栈的顺序对不对队列的先进先出有没有被破坏环形取模有没有越界所以接下来我会用测试用例和调试工具把这两个结构从看起来对变成实测对。4. 边界条件与测试用例把问题扼杀在扩容和取模处4.1 栈的测试策略压到扩容弹到空栈的测试我建议按这个路径来初始化空栈连续弹出 3 次确认不崩溃并提示栈空。压入 1 个元素弹出确认值相等。循环压入超过初始容量比如初始容量 4压 10 个再循环弹出确认顺序是后进先出。测试代码void testStack() { DynamicStack s; initStack(s, 4); // 空栈弹出 printf(弹空栈: %d\n, popStack(s)); // 压入超过容量 for (int i 1; i 10; i) { pushStack(s, i); } // 弹出并验证 int expected 10; while (!isEmptyStack(s)) { int val popStack(s); if (val ! expected) { printf(顺序错误: 期望 %d, 实际 %d\n, expected, val); } expected--; } printf(栈测试完成容量%d, top%d\n, s.capacity, s.top); destroyStack(s); }我发现很多人测栈只测容量范围内的压弹从不测扩容。结果扩容代码里realloc写错了也不知道。所以我强烈建议初始容量给一个小值比如 2 或 4然后压入量至少是容量 2 倍以上专打扩容路径。4.2 队列的测试策略绕一圈再绕一圈队列测试要更狠因为环形会绕圈。测试路径空队出队确认不崩溃。入队 3 个出队 2 个再入队 3 个。这一步会触发front和rear在环形数组里各种位置交错。持续入队直到触发扩容再持续出队验证顺序是先进先出。关键测试让队列接近满然后入队触发扩容确保扩容后队列数据顺序不变。void testQueue() { DynamicQueue q; initQueue(q, 4); // 空队出队 printf(空队出队: %d\n, dequeue(q)); // 先入3个 enqueue(q, 1); enqueue(q, 2); enqueue(q, 3); // 出2个 printf(出队: %d\n, dequeue(q)); // 1 printf(出队: %d\n, dequeue(q)); // 2 // 再入5个此时会经历扩容且 front 指向旧位置 for (int i 4; i 8; i) { enqueue(q, i); } // 连续出队验证 int expected 3; while (q.size 0) { int val dequeue(q); printf(出队: %d\n, val); if (val ! expected) { printf(顺序错误: 期望 %d, 实际 %d\n, expected, val); } expected; } destroyQueue(q); }这个测试最妙的地方在于入队 3 个后出队 2 个front变成 2再入队 5 个首次入队会先在rear处写然后rear绕回等插入到size capacity时触发扩容。这时front不在 0旧数据分布是环形的resizeQueue必须正确处理这段从 front 开始的逻辑顺序。如果搬移代码写错了比如直接memcpy(newData, oldData, ...)这里立刻会看到队列顺序变成乱的。我实际跑这个测试时遇到过一个典型错误扩容后front和rear忘了重置导致新队列里front还指向旧下标出队时直接越界访问。加一行q-front 0; q-rear q-size;才解决。这个 Bug 不看测试根本发现不了。4.3 断言宏与自动化验证手写printf测试只能肉眼观察效率低。实际项目里我建议用断言#include assert.h #define ASSERT_EQ(actual, expected) \ do { \ if ((actual) ! (expected)) { \ printf(断言失败: %s:%d, 期望 %d, 实际 %d\n, __FILE__, __LINE__, (expected), (actual)); \ exit(1); \ } \ } while(0)然后把上面的测试全部改成断言验证。这样以后改了实现跑一遍测试就知道有没有破坏行为。我在维护老代码时经常这么干先写测试用例固住正确行为再放心重构。4.4 内存检查与 Valgrind 使用心得C 语言动态内存最怕泄漏和越界。写完代码后我习惯跑valgrind --leak-checkfull ./demo。重点关注三件事definitely lost内存泄漏通常是destroy没调用或调用不全。Invalid read/write越界访问多半是取模没算对或扩容后front/rear没重置。Mismatched free/deleteC 里malloc配freeC 里new配delete混用会崩。跑一次 Valgrind 发现的问题往往比看十遍代码都有效。因为它能精确到行号告诉你哪块内存没释放、哪个下标越界了。这在数据结构练习和真实项目里都是一等一的工具。5. 性能优化思路从 O(n) 到均摊 O(1) 的进阶考量5.1 为什么均摊复杂度很重要动态数组最核心的复杂度分析是均摊。栈压栈时偶尔触发扩容扩容本身 O(n)但均摊到每一次压栈是 O(1)。这个结论是这么来的假设容量从 1 倍增到 n中间会扩容 log n 次每次扩容搬移的元素数量分别为 1、2、4、8...、n/2。总搬移量是 2n - 1所以均摊到 n 次插入每次就是 O(1)。我经常用这个结论跟同事解释倍增扩容不是浪费是均摊最优策略。如果改成固定增加 100 个总搬移量是 O(n²)那就不行了。这也是我在最开始强调 2 倍扩容而不是 10 的原因。5.2 取模优化的正确性与隐患我在环形队列里用 (capacity - 1)代替% capacity。正确性前提是capacity为正且为 2 的幂。为什么 (capacity - 1)等价于% capacity因为对于 2 的幂capacity 2^kcapacity - 1的二进制是 k 个 1任何数与它做只保留低 k 位结果范围是[0, capacity-1]正好是取模结果。举个例子capacity 88 - 1 7二进制0111。假设rear 7rear 1 88 7 0相当于8 % 8 0。假设rear 56 7 6相当于6 % 8 6。这个优化本身没问题但隐患是如果有人把capacity改成 6、10 这种非 2 的幂整个队列就崩了。所以我在initQueue里强制向上取整到 2 的幂并且建议在注释里写清楚所有修改capacity的地方都必须保证它始终是 2 的幂。否则别用位运算老老实实用%可读性更好。5.3 扩容缩容策略什么时候回收内存只扩不缩会导致一个长期运行的队列占用大量空闲内存。比如峰值 100 万元素之后长期只有 10 个元素但内存还是按 100 万容量占着。缩容策略一般有两种当size capacity / 4时容量减半。当size 0时直接释放大数组下次入队再重新分配。缩容的触发阈值不能太激进。我见过有人写元素数小于容量一半就缩容结果在容量边界附近反复缩扩性能抖动很严重。正确做法是留出安全余量比如size capacity / 4才缩让容量始终大于元素数的 2 倍以上。缩容实现其实和扩容一样只是目标容量变小搬移逻辑完全复用resizeQueue。唯一要注意的是newCap不能小于某个最小值比如 1 或初始容量防止缩成 0 导致除零。5.4 内存局部性与缓存友好度数组实现天然比链表缓存友好因为元素是连续存放的。遍历队列时CPU 预取能一口气加载一块内存链表则要跟着指针跳转缓存命中率低。这一点在性能敏感场景非常明显。我曾经在某个模拟器项目里用数组队列替代链表队列同样处理 100 万个事件耗时下降了约 30%。原因就是缓存局部性。所以面试或者系统设计时如果你能说出数组实现队列比链表实现更适合高吞吐场景原因包括内存局部性和无指针追逐会很加分。但数组队列也有代价扩容时需要一次性搬移链表则每次插入分配节点。所以如果你完全无法预估容量峰值且内存碎片不敏感链表在免扩容这个维度上有它的优势。两者没有绝对的谁好谁坏关键在于场景。我的习惯是能预估算量级用数组完全不可控且插入频繁链表兜底。6. 常见踩坑汇总从指针误用到负数下标6.1 栈top初始化为 0 但数组越界如果初始化时top设置为0但压栈直接写data[top] val; top第一次没毛病可如果你忘了判满等top等于capacity时再写data[top] val就数组越界了。更隐蔽的版本是扩容后capacity更新了但top还是旧值导致下次压栈时直接越界。这种问题靠编译器不一定查得出来所以必须每次扩容后打印s-top和s-capacity自查。6.2 栈pop返回后残留指针导致二次 free如果栈元素是char*弹栈时应该先取出指针再把栈内位置置空然后再使用。否则同一块内存会被两次释放或者变成悬挂指针。这是我当年写字符串栈时踩过的最痛的坑char *popStringStack(DynamicStack *s) { if (isEmptyStack(s)) return NULL; char *str s-data[--s-top]; s-data[s-top] NULL; // 关键 return str; }用int栈不觉得有问题换成指针栈立刻暴露。说到底数据结构本身是通用的但元素类型不同你就要考虑不同的生命周期管理。6.3 队列环形取模写成% q-capacity - 1我见过有人把(front i) % capacity写成(front i) % capacity - 1优先级搞错负数下标直接崩溃。C 语言里%的优先级和、-是同一级从左到右结合所以a % b - 1是(a % b) - 1。如果你希望的是a % (b - 1)必须加括号。这种问题在测试量大时一定会暴露但更好的方式是写一个辅助函数static int nextPos(int cur, int cap) { return (cur 1) (cap - 1); }所有取模操作都走这个函数统一维护。一旦改成 2 的幂约束这个函数内部也能统一换实现。6.4 队列front rear到底是空还是满如果不用size字段只用front和rear判断状态front rear可能是空也可能是满取决于具体约定。穷举状态数不够所以要么牺牲一个存储单元要么维护size。我强烈建议维护size代码可读性和正确性都更高而且size本身就是你随时可能要打印的调试信息。6.5 C 的 STL 容器也不能完全替代手写用 C 时std::vector扩容也是倍增策略std::deque是分段连续数组。但手写一遍的意义在于你会知道std::deque为什么能在两端 O(1) 插入删除——因为它把数组分成了很多块头尾都能增长。这个概念在系统设计里非常常见比如环形缓冲区在生产者消费者模型中的应用本质上就是队列。所以就算你平时用 STL我也建议你用 C 语言或裸指针把这两个结构实现一遍。这个过程训练的是内存视角你不再把vector当黑盒而是知道它内部有一个capacity在悄悄倍增。7. 从手写容器到业务落地环形队列在生产者消费者模型中的应用7.1 单生产者单消费者的无锁环形队列手写动态队列最有价值的落地场景之一就是生产者消费者模型。如果只有一个生产者线程和一个消费者线程并且队列容量固定不扩容可以用无锁环形队列生产者只写rear消费者只读front。读和写分别操作不同的变量通过内存屏障或原子操作保证可见性。不需要互斥锁因为不存在多个线程同时操作同一个变量。C 语言里可以用 C11 的stdatomic.h#include stdatomic.h typedef struct { int *data; int capacity; _Atomic int front; _Atomic int rear; } LockFreeQueue; int lfq_enqueue(LockFreeQueue *q, int val) { int r atomic_load(q-rear); int f atomic_load(q-front); if ((r 1) % q-capacity f) { return -1; // 满 } q-data[r] val; atomic_store(q-rear, (r 1) % q-capacity); return 0; } int lfq_dequeue(LockFreeQueue *q, int *out) { int f atomic_load(q-front); int r atomic_load(q-rear); if (f r) return -1; // 空 *out q-data[f]; atomic_store(q-front, (f 1) % q-capacity); return 0; }这段代码能跑但要注意它只适合单生产者单消费者。如果是多生产多消费rear会被多个线程同时改就需要 CAS 或其他手段。无锁编程细节很多这里不展开但你要明白动态扩容和锁往往互相冲突——扩容时会搬移数据导致消费者读到旧数据或半搬移状态复杂度瞬间上升。所以工业级的无锁队列通常都是固定容量满了要么丢、要么阻塞、要么覆盖最旧数据。7.2 动态队列在内存池、任务调度中的角色除了生产者消费者动态队列在任务调度、消息缓存、广度优先搜索里也到处都是。比如 BFS 需要队列如果用固定数组图特别大时可能溢出如果用手写动态数组队列只要内存够就能一直扩展。内存池里也经常用空闲块队列分配时从队头取一块释放时从队尾放回。这里队列的容量可能动态变化手写版本就能灵活控制。7.3 什么时候该用固定容量什么时候该用动态扩容我的经验法则是如果队列容量可预测且有上限优先固定容量。省去扩容开销还能避免扩容瞬间的延迟抖动。如果流量峰值难预测且对内存利用率要求高用动态扩容。如果单次任务对实时性要求极高尽量避免动态扩容——扩容瞬间的 memcpy 可能造成毫秒级卡顿。这时候可以预先估计峰值直接用大容量固定队列。这个选择无关对错只关乎场景。8. 最后的实操体会把手写变成肌肉记忆写到这里整个用数组实现动态栈与队列的过程已经完整走了一遍。最后聊聊我自己的感受。第一先写栈再写队列循序渐进。栈只有一头操作动态扩容只需要线性搬移适合用来建立结构体 初始容量 倍增扩容的思维套路。队列多了一个front又引入了环形和取模如果你直接上手队列很容易在扩容搬移时一头雾水。先把栈写通队列只需要理解从 front 开始按逻辑顺序搬移这一件事。第二边写边用断言和 Valgrind 验证。我第一次写队列时在resizeQueue里忘了重置rear导致扩容后入队覆盖了本不该覆盖的元素。当时靠肉眼盯代码盯了一个小时没看出来最后跑了断言测试立刻定位。从那以后我写任何数据结构第一件事就是先写测试用例把空结构操作扩容后顺序不变反复绕圈后数据正确三个场景全部锁死。第三不要止步于能用。动态栈和队列写完之后可以继续做几件事给栈加上缩容逻辑模仿 STL 的内存管理。把队列改成泛型使用void*或者 C 语言的宏模板。直接把固定容量的环形队列改成无锁版本用于多线程场景。对比数组实现和链表实现的性能差异自己亲手测一遍基准。这些事情做完你对数据结构就不再是背概念的程度而是真的能在项目里随时徒手造轮子。面试时如果被问到为什么 STL 的 queue 底层常常是 deque 而不是 list你也能从内存局部性、扩容策略、两端操作效率这几个角度给出有深度的回答。这篇文章的代码都是可以直接复制到本地跑的。我建议你把初始容量调成 2把压栈和入队数量调成 100然后加上 Valgrind 或者 ASan 编译选项-fsanitizeaddress再跑一遍测试。你会发现手写一遍、测一遍、坏一遍、修一遍比看十篇教程都管用。数组实现动态栈和队列从来不是过时的基本功而是理解所有连续内存容器的最佳入口。