链表的指针操作、栈的先进后出、队列的先进先出这三个基础数据结构在 C 语言里的实现几乎是每一位想搞懂底层原理的开发者都绕不开的关卡。我当年第一次写链表时头指针、尾指针、临时指针搅在一起一调试就是大半个晚上直到把插入和删除的次序彻底背下来才发现 C 语言的指针、内存分配、模块化设计这些概念全都串在了一块。这篇文章就把链表、栈、队列的 C 语言实现从头到尾过一遍既有设计思路也有可以抄走的代码还有我踩过的一些坑。想找参考实现、想弄懂为什么这么写的同学可以直接跟着段落往下看。1. 结构设计与选型思路很多同学拿到“用 C 实现链表、栈、队列”这个题目第一反应是赶紧敲代码。这个冲劲没错但我建议先花十分钟把选型想清楚否则写到一半很容易发现当前结构根本不支撑业务场景。链表、栈、队列都算线性结构可核心诉求差别很大链表管的是“一段随时增删的数据”栈管的是“后进先出”队列管的是“先进先出”。1.1 数组和链表到底谁更合适数组和链表的差异如果用一句话概括数组是连续的内存块链表是一串散落的节点。连续意味着可以用下标直接算地址随机访问就是 O(1)散落意味着必须顺着 next 指针一个一个找访问第 n 个元素是 O(n)。同样的差异也体现在插入和删除上数组在中间插一个数要把后面所有元素往后挪链表只要改两个指针。我把常用的判断点整理成一张表维度数组链表随机访问O(1)O(n)已知位置插入/删除O(n)需要搬移O(1)改指针空间预分配一次性连续分配每次节点独立分配缓存友好性好局部性明显差节点分布离散额外内存开销几乎没有每个节点多存一个指针实际选择要看“读写比”而不是死记结论。读多写少、又频繁按下标访问数组明显更稳数据量不确定、中间插删是常态链表更灵活。我举一个常见的例子哈希表的拉链法桶下面挂的是链表链表过长时再转成树或有序结构这说明真实工程里并没有“唯一正确解”而是随着数据特征动态切换。1.2 栈和队列该选数组还是链表栈的特点是只在栈顶操作队列的特点是队尾进、队头出。这两个结构本身不关心“中间元素”所以实现选择的关键就落在空间和扩展性上。栈我建议优先用数组原因很实在入栈出栈只需要修改 top 下标缓存命中也好。数组栈的扩容偶尔会触发一次搬移但均摊下来代价很小扩容一倍让每次 push 的操作成本摊薄到 O(1) 附近。链表栈的好处是没有扩容一说节点用完就 free但每次 push 都要 malloc 一次节点频繁使用时分配器开销反而会高于数组栈的搬移。队列则要分情况。循环数组队列的空间紧凑、性能好但要处理“判空判满”和“取模回绕”。链表队列逻辑上更简单入队出队都是改指针代价是节点分散、缓存不友好。如果队列长度经常变化、且峰值不可预估链表队列入门友好如果追求吞吐量且能预留足够容量循环数组队列是更专业的选择。1.3 接口统一替换底层才不难这一条算是我的习惯不管底层用数组还是链表对外暴露的函数名和参数尽量保持一致。比如push(stack, value)、pop(stack)、enqueue(queue, value)、dequeue(queue)让上层代码只跟这组接口打交道。这样做的收益很明显。你从数组栈换成链表栈调用方一行都不用改笔试手写代码时考官也容易看懂你的结构设计。更重要的是接口统一后你可以在同一套 main 函数里测试多种实现哪个有 bug 马上就能对比出来。我后面给的测试模板就是建立在这个习惯上的。先想清楚结构选型再动手写节点这是我认为最重要的一步。接下来就从链表这个“地基”开始拆。2. 链表实现核心细节链表本身不只是三个结构里的一个它还是“链表栈”和“链表队列”的底层骨架。所以我把链表的过程写细一点后面实现栈和队列时你会发现其实就是在“复用同一套指针操作”。2.1 先有一个趁手的节点定义在 C 语言里最常见的节点定义长这样typedef struct Node { int data; struct Node *next; } Node;注意struct Node *next这行next是指向自身类型的指针。有人一开始会写Node *next但在这里还不行因为 typedef 的名字在这个结构体内部还没生效编译器还没看到完整的struct Node。所以在结构体内部一定要写struct Node *等结构体定义完了后面创建变量或参数时再用Node就方便了。节点还有两个容易忽略的细节。一是data类型这里用 int 是为了演示你可以改成任意业务类型甚至是一个 void* 指针这样链表就能存任意结构了。二是createNode函数最好单独写并且检查 malloc 的返回值我见过不少代码在 malloc 后不判空程序在内存不足时直接崩溃调试起来非常痛苦。节点创建函数如下Node* createNode(int val) { Node *n (Node *)malloc(sizeof(Node)); if (n NULL) { return NULL; } n-data val; n-next NULL; return n; }2.2 一个哨兵头节点省掉一半特殊情况链表写起来常见的痛点是“第一个节点”和“最后一个节点”总是需要特殊判断。比如在头部插入一个节点要改 head 指针本身删除最后一个节点要把前一个节点的 next 置空。这些判断代码不难但容易漏。我的做法是引入一个“哨兵头节点”也就是 dummy 节点。它不存业务数据只占一个位置让真正的头节点永远不是第一个节点。这样插入和删除的逻辑就被统一了不管操作位置是 0 还是中间都是同一种写法。下面这两段代码是带哨兵的插入和删除可以先感受一下这种写法Node* insertAt(Node *head, int pos, int val) { Node dummy; dummy.next head; Node *p dummy; int idx 0; while (p-next ! NULL idx pos) { p p-next; idx; } Node *newNode createNode(val); if (newNode NULL) { return dummy.next; } newNode-next p-next; p-next newNode; return dummy.next; } Node* deleteAt(Node *head, int pos) { Node dummy; dummy.next head; Node *p dummy; int idx 0; while (p-next ! NULL idx pos) { p p-next; idx; } if (p-next ! NULL) { Node *del p-next; p-next del-next; free(del); } return dummy.next; }这里dummy是栈上的局部变量不是 malloc 出来的所以用完不用 free 它我们把dummy.next作为新的头指针返回。while循环结束后p指向插入位置的前一个节点p-next就是要插入位置的当前节点。整个过程不需要判断head NULL因为即使链表为空dummy.next也是 NULLp-next操作仍然安全。你可能会有疑问返回值为什么还是dummy.next原因是插入到位置 0 时头节点会变化而 dummy 是局部变量无法在函数结束后继续被上层访问所以必须把新的头指针传出去。如果你把链表封装成带 head 的结构体那就不需要每次返回直接修改结构体里的 head 即可。两种封装方式我都在项目里用过简单练习时用返回指针更直白工程代码里则建议用结构体封装。2.3 插入、删除、反转把指针次序理清楚链表最容易写错的地方是插入和删除的指针次序。插入的时候必须先让新节点的 next 指向后一个节点再让前一个节点的 next 指向新节点。调换次序的后果是前一个节点先指向了新节点旧链表从此断开后半个链表找不回来内存就泄漏了。删除的时候正好相反要先让前一个节点的 next 跳过被删节点指向被删节点的后面然后才能 free 被删节点。很多时候段错误并不是因为 free 本身而是 free 之前没有把前后指针调整好或者 free 完之后还去访问被删节点的 next。反转链表是另一个高频考点也是检验指针次序的好题目。用三个指针 prev、cur、next 一趟扫完即可Node* reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; cur-next prev; prev cur; cur next; } return prev; }关键步骤是先保存cur-next再改cur-next prev。如果先改后保存原来的后继就丢了。三个指针里prev始终指向前一个节点循环结束时 prev 就是新的头节点。这段代码我每次笔试都写同一个版本原因就是固定顺序先存 next再改指针最后移动三个指针。链表这部分把插入、删除、反转写熟后面的栈就是“在头部插删”的特殊链表队列就是“一个在头、一个在尾”的特殊链表。下面进入栈的正题。3. 栈的数组实现与链表实现栈的语义很简单只能在栈顶进、栈顶出所以数组栈和链表栈的核心操作几乎一样短。差别主要在一个地方数组要管容量链表要管 malloc。3.1 数组栈扩容策略决定上限数组栈的经典结构是三个成员data 数组指针、capacity 容量、top 下标。top 从 -1 开始表示空栈push 时先判断容量不够就扩容pop 时先判空返回栈顶再减下标。我常用的结构体如下typedef struct { int *data; int capacity; int top; // 栈顶下标-1 表示空栈 } ArrayStack;push 和 pop 的实现void stackPush(ArrayStack *s, int val) { if (s-top 1 s-capacity) { int newCap s-capacity * 2; int *tmp (int *)realloc(s-data, newCap * sizeof(int)); if (tmp NULL) { return; } s-data tmp; s-capacity newCap; } s-top; s-data[s-top] val; } int stackPop(ArrayStack *s) { if (s-top 0) { return -1; } int val s-data[s-top]; s-top--; return val; }扩容为什么翻倍“翻倍增长”能让扩容的均摊代价变成 O(1)。假设容量从 1 开始每次翻倍扩容时复制数据的总次数加起来是 1248...最后一次不超过当前容量总复制量大约是当前容量的两倍。如果容量只加 1每次 push 都可能扩容复制量累计成 O(n^2)。当然翻倍也有代价容量很大但栈很空时会浪费内存我习惯在容量明显超过使用量时才考虑缩容比如capacity 1024 top capacity / 4时缩到一半避免频繁扩容缩容互相打架。还有一点要说明stackPop返回 -1 作为错误值是因为演示代码只处理非负整数。实际工程里栈可能存任意 int-1 也可能是合法值。更稳的做法是用输出参数比如int pop(Stack *s, int *out)返回 0 表示成功、-1 表示失败。接口一改后面所有调用点都要跟着改所以建议一开始就把接口想清楚。3.2 链表栈入栈出栈都在头部链表栈的思路非常直接把链表的头部当作栈顶。入栈就是创建一个新节点让它指向原来的 top再把 top 更新为新节点。出栈就是保存 top取出数据top 后移再 free 旧节点。结构体只需要一个 top 指针typedef struct NodeStack { Node *top; } NodeStack; void linkedStackPush(NodeStack *s, int val) { Node *newNode createNode(val); if (newNode NULL) { return; } newNode-next s-top; s-top newNode; } int linkedStackPop(NodeStack *s) { if (s-top NULL) { return -1; } Node *del s-top; int val del-data; s-top del-next; free(del); return val; }这个实现易错在两个地方。第一个是入栈顺序不能换newNode-next s-top必须在s-top newNode之前否则新节点自己指向了自己。第二个是出栈时先保存要 free 的节点再移动 top。不少新手写s-top s-top-next; free(s-top);结果把新栈顶给 free 了这是经典错误。链表栈和数组栈的性能差异我在第 1 部分已经说过链表栈省去了扩容搬移但每次 push 都多一次 malloc。实测下来数据规模小的时候差异不明显一旦频繁 push 几十万次malloc 的耗时会明显高于数组栈的扩容均摊。所以笔试题里我优先写数组栈只有题目明确要求“用链表实现栈”时才走链表。3.3 实战括号匹配和逆波兰式栈的两个经典应用很适合用来检验任意一种栈实现是否靠谱。第一个是括号匹配int isBalanced(const char *s) { ArrayStack stack; stackInit(stack, 32); while (*s) { if (*s ( || *s [ || *s {) { stackPush(stack, *s); } else if (*s ) || *s ] || *s }) { int left stackPop(stack); if (left -1) { return 0; } if (*s ) left ! () return 0; if (*s ] left ! [) return 0; if (*s } left ! {) return 0; } s; } return stack.top 0; }匹配的原理很朴素遇到左括号就入栈遇到右括号就出栈并检查是否配对。只要中间出现“栈空却遇到右括号”或“配对失败”就说明括号不合法。最后栈空表示所有左括号都找到了对应的右括号。这个例子能测出你的栈是否支持连续压入、弹出以及空栈保护是否做得到位。第二个是逆波兰式求值这里的数字和运算符都从输入里取遇到数字就入栈遇到运算符就弹出两个操作数计算后再压回去int evalRPN(const char **tokens, int n) { ArrayStack stack; stackInit(stack, 16); for (int i 0; i n; i) { const char *t tokens[i]; if (t[0] 0 t[0] 9) { stackPush(stack, atoi(t)); } else { int b stackPop(stack); int a stackPop(stack); switch (t[0]) { case : stackPush(stack, a b); break; case -: stackPush(stack, a - b); break; case *: stackPush(stack, a * b); break; case /: stackPush(stack, a / b); break; } } } return stackPop(stack); }这个示例偷了一点懒只处理了单个字符的非负整数。真实场景里数字可能是多位数也可能是负数那就要把 token 切成更细致的格式再解析。这里不展开重点是体会栈在“临时保存中间结果”这件事上的作用。把这两个应用跑通你的数组栈和链表栈基本就算过关了。4. 队列循环数组与链表方案队列的结构关键在“两头”入队从队尾出队从队头。这两端可能会在同一个数组里来回移动所以需要处理“环形”逻辑。链表队列没这个环的问题但要在 front 和 rear 两个指针之间做好配合。4.1 循环数组队列判空判满要讲套路直接开一个数组当队列出队时 front 后移入队时 rear 后移很快会遇到一个问题队头空出来了rear 却已经到数组末尾无法再入队。解决办法是把数组看成环形用取模运算把下标回绕到数组开头。我的结构体里特意加了 count这样判空和判满都不用靠 front 和 rear 的巧合来猜typedef struct { int *data; int capacity; int front; // 队首下标出队时移动 int rear; // 下一个入队位置 int count; // 当前元素个数 } CirQueue;入队、出队和扩容的代码如下void enqueue(CirQueue *q, int val) { if (q-count q-capacity) { int newCap q-capacity * 2; int *tmp (int *)malloc(newCap * sizeof(int)); for (int i 0; i q-count; i) { tmp[i] q-data[(q-front i) % q-capacity]; } free(q-data); q-data tmp; q-front 0; q-rear q-count; q-capacity newCap; } q-data[q-rear] val; q-rear (q-rear 1) % q-capacity; q-count; } int dequeue(CirQueue *q) { if (q-count 0) { return -1; } int val q-data[q-front]; q-front (q-front 1) % q-capacity; q-count--; return val; }扩容这一段其实是“重新排队”先把旧数组按从头到尾的顺序搬到新数组再把 front 重置为 0rear 放在 count 的位置。搬完后队列在物理上也变成了连续的一整段取模逻辑可以继续正常工作。判断队列是否为空看清 count比看 front 和 rear 是否相等更直观也避免了“空队列”和“满队列”状态下一不留神就混在一起的问题。我见过不少人用“浪费一个格子”的办法区分空和满front rear 表示空(rear 1) % capacity front表示满。这样做省一个 count 成员但容量实际少了 1而且代码一复杂就容易把判断写反。两者没有绝对优劣建议第一次写循环队列时老老实实加 count让代码意图更直白。4.2 链表队列小心尾部指针的边界链表队列的实现就是用两个指针分别指向链表的头和尾。入队在 rear 后面挂新节点出队从 front 拿掉节点。特殊之处在于队列从空到非空、从非空到空这两个临界点typedef struct { Node *front; Node *rear; } LinkedQueue; void linkedEnqueue(LinkedQueue *q, int val) { Node *newNode createNode(val); if (newNode NULL) { return; } if (q-rear NULL) { q-front newNode; } else { q-rear-next newNode; } q-rear newNode; } int linkedDequeue(LinkedQueue *q) { if (q-front NULL) { return -1; } Node *del q-front; int val del-data; q-front del-next; if (q-front NULL) { q-rear NULL; } free(del); return val; }这里最容易被忽略的是linkedDequeue里的最后一个 if。当队列只有一个节点时q-front被后移成 NULL但q-rear仍然指向这个已经被 free 的节点。如果不把 rear 也置空下一次入队时q-rear-next newNode就会对悬空指针做写入直接段错误。我初期写队列踩过好几次这种坑后来养成一个习惯只要动到 front 或 rear就在操作后问自己“另一个指针需不需要同步更新”。链表队列和循环数组队列还有一个细微差别链表队列的 rear 永远指向最后一个节点不存在“队列满”的状态但每次入队都要 malloc 一次节点出队又要 free。如果你的业务对延迟要求很高malloc/free 的波动可能比数组扩容更明显。选型时最好先用数据压一遍不要只看理论复杂度。4.3 队列的应用场景从 BFS 到任务调度队列最典型的应用是广度优先搜索。在图上从起点出发按层扩展每一层节点都要先放进队列再依次处理。我写了一个最简 BFS 骨架用的是刚才的循环数组队列void bfs(int start, int n, int (*graph)[n]) { CirQueue q; queueInit(q, n); int *visited (int *)calloc(n, sizeof(int)); visited[start] 1; enqueue(q, start); while (q.count 0) { int cur dequeue(q); printf(%d , cur); for (int i 0; i n; i) { if (graph[cur][i] !visited[i]) { visited[i] 1; enqueue(q, i); } } } printf(\n); free(visited); }这段代码用q.count 0作为循环条件本质就是在测队列是否为空。为什么 BFS 要用队列而不是栈因为队列先进先出能保证先发现的节点先被扩展从而按距离递增的顺序访问如果用栈就退化成了 DFS路径顺序就乱了。任务调度也是同样的逻辑先来的请求先处理来的顺序不能乱掉。这两种场景都能直接把队列的实现拿过去用。5. 常见问题与调试实录结构和代码都写完了我想专门聊一聊我在大量练习里遇见的错误。很多人代码写得快但在调试上花了很多时间其实大多数都是几个老问题。5.1 段错误的几类来源和现场特征链表、栈、队列相关的段错误归纳起来通常只有三类空指针解引用、野指针访问、越界写。空指针很好认调试器会告诉你访问地址是 0x0野指针大多是 free 之后没把指针置空或者修改 next 时绕过了某个节点越界写经常发生在数组栈扩容时容量算错数据写到了data[capacity]之后。我举一个常见的“活例子”删除链表中某个节点后代码再用一个遍历函数打印所有节点数据。如果删除时只改了前驱的 next没有释放内存整个链表还能正常工作如果 free 之后又错误地继续访问了 del 节点那表现出来的就是“有时候能跑有时候崩溃”因为那块内存已经被分配器回收内容随时可能被改写。这类问题最坑表面看不出来规律实际原因就是访问了已经不属于自己的内存。5.2 内存泄漏与重复释放Valgrind 是最好的助手C 语言里没人替你回收内存漏了就是漏了。最简单的验证方法是 Valgrind零侵入直接编译后把可执行文件丢给它就行gcc -g -Wall -fsanitizeaddress -o demo demo.c valgrind --leak-checkfull ./demo代码编译时我习惯加-g这样报错里有行号。-Wall开启常见警告很多未用到的函数、类型不匹配都能提前暴露。-fsanitizeaddress是另一个利器数组越界、释放后访问这类问题跑起来就会直接报错并告诉你具体位置比纯 Valgrind 更快。等程序稳定了再去掉 sanitizer因为它的内存占用比较大。Valgrind 报告里最需要关注的字段是definitely lost和Invalid read/write。前者说明你漏了 free典型原因包括删除节点时没有把前驱的 next 跳过或者反转链表时把某个节点的指针弄丢了。后者说明你访问了已释放或越界的内存。我第一次用 Valgrind 的时候发现一个大程序里有 20 多处definitely lost全是早期写链表时留下来的“指针孤儿”改掉之后整晚都安心得多。5.3 用断言和防御式检查兜住低级错误一套负责的代码应该在“发现问题”和“掩盖问题”之间选择前者。C 语言里最廉价的防御是assertassert(p ! NULL)、assert(top -1)都是很好的观察点。断言只会在调试构建里生效正式编译加-DNDEBUG就自动关闭不影响性能。另一个建议是给所有“可能失败的接口”设计明确的错误返回约定。比如我上面写的return -1虽然简单但只能处理非负数据。更通用的做法是int tryPop(ArrayStack *s, int *out) { if (s-top 0) { return -1; } *out s-data[s-top]; s-top--; return 0; }调用方先看返回值再拿*out这样就不会出现“把 -1 当合法数据”的误判。这种设计学习曲线不高但对代码维护的帮助非常大尤其是在后面涉及到图算法、缓冲区管理等复杂场景时。6. 实操总结与往后的扩展建议到这里链表、栈、队列的 C 语言实现主体已经讲完。最后我想把测试方法和一个大的扩展方向留给你。6.1 一份简单但有效的测试模板数据结构代码光靠眼睛看不出来对错我习惯用宏搭一个极简测试框架static int test_count 0; #define CHECK(expr) do { \ test_count; \ if (!(expr)) { \ printf(FAIL: %s (line %d)\n, #expr, __LINE__); \ } \ } while (0)然后在 main 里依次验证正常、边界和异常三类用例。正常用例连续 push 5 个元素连续 pop 检查顺序。边界用例空链表插入、删除最后一个节点、队列只剩一个元素。异常用例空栈 pop、空队列 dequeue、删除不存在的位置。每一次测试跑完如果FAIL打印为 0我才敢说这一版基本稳了。边界用例的重要性远高于正常用例。我记得写循环数组队列时正常入队出队怎么跑都对唯独在“队列刚好满”和“队列只有一个元素”这两个状态下出了问题后来正是靠边界用例把 bug 抓出来。如果你自己实现这三种结构一定把边界情况列成清单别偷懒。6.2 从这堂基础课往外扩展的方向链表、栈、队列是线性结构的入门三件套但掌握之后可以直线往里走。最先值得做的是双向链表节点里加一个 prev 指针删除操作不需要从头遍历前驱代价是每个节点多 8 字节64 位系统下。接着是循环链表适合做约瑟夫环、进程轮转这类场景。再往上可以看跳表它给有序链表加了几层索引让查找从 O(n) 降到接近 O(log n)很多高性能缓存都会用到。栈和队列的进阶方向则是单调栈、单调队列、优先队列它们在算法题里出场率极高。我个人的体会是这三个结构的 C 语言实现本质上是在训练“手动管理内存 精确控制指针”的能力。能用好它们往后看树、图、哈希表思路都会顺很多。每实现一个结构都顺手写一遍测试宏和 Valgrind 检查这个习惯带到任何 C 项目里都不过时。如果你正在学数据结构的路上我建议你别只抄代码把示例跑通后再故意制造几个 bug比如交换插入的指针顺序、忘记更新 rear然后观察程序怎么崩溃。这种“主动失败”的训练方式比十遍默写代码更能加深理解。数据结构不难难的是自己动手踩一遍坑然后在下一次遇到同样的指针问题时能笑着说这个坑我熟。 C语言实现链表、栈与队列：从指针操作到内存管理实战
链表的指针操作、栈的先进后出、队列的先进先出这三个基础数据结构在 C 语言里的实现几乎是每一位想搞懂底层原理的开发者都绕不开的关卡。我当年第一次写链表时头指针、尾指针、临时指针搅在一起一调试就是大半个晚上直到把插入和删除的次序彻底背下来才发现 C 语言的指针、内存分配、模块化设计这些概念全都串在了一块。这篇文章就把链表、栈、队列的 C 语言实现从头到尾过一遍既有设计思路也有可以抄走的代码还有我踩过的一些坑。想找参考实现、想弄懂为什么这么写的同学可以直接跟着段落往下看。1. 结构设计与选型思路很多同学拿到“用 C 实现链表、栈、队列”这个题目第一反应是赶紧敲代码。这个冲劲没错但我建议先花十分钟把选型想清楚否则写到一半很容易发现当前结构根本不支撑业务场景。链表、栈、队列都算线性结构可核心诉求差别很大链表管的是“一段随时增删的数据”栈管的是“后进先出”队列管的是“先进先出”。1.1 数组和链表到底谁更合适数组和链表的差异如果用一句话概括数组是连续的内存块链表是一串散落的节点。连续意味着可以用下标直接算地址随机访问就是 O(1)散落意味着必须顺着 next 指针一个一个找访问第 n 个元素是 O(n)。同样的差异也体现在插入和删除上数组在中间插一个数要把后面所有元素往后挪链表只要改两个指针。我把常用的判断点整理成一张表维度数组链表随机访问O(1)O(n)已知位置插入/删除O(n)需要搬移O(1)改指针空间预分配一次性连续分配每次节点独立分配缓存友好性好局部性明显差节点分布离散额外内存开销几乎没有每个节点多存一个指针实际选择要看“读写比”而不是死记结论。读多写少、又频繁按下标访问数组明显更稳数据量不确定、中间插删是常态链表更灵活。我举一个常见的例子哈希表的拉链法桶下面挂的是链表链表过长时再转成树或有序结构这说明真实工程里并没有“唯一正确解”而是随着数据特征动态切换。1.2 栈和队列该选数组还是链表栈的特点是只在栈顶操作队列的特点是队尾进、队头出。这两个结构本身不关心“中间元素”所以实现选择的关键就落在空间和扩展性上。栈我建议优先用数组原因很实在入栈出栈只需要修改 top 下标缓存命中也好。数组栈的扩容偶尔会触发一次搬移但均摊下来代价很小扩容一倍让每次 push 的操作成本摊薄到 O(1) 附近。链表栈的好处是没有扩容一说节点用完就 free但每次 push 都要 malloc 一次节点频繁使用时分配器开销反而会高于数组栈的搬移。队列则要分情况。循环数组队列的空间紧凑、性能好但要处理“判空判满”和“取模回绕”。链表队列逻辑上更简单入队出队都是改指针代价是节点分散、缓存不友好。如果队列长度经常变化、且峰值不可预估链表队列入门友好如果追求吞吐量且能预留足够容量循环数组队列是更专业的选择。1.3 接口统一替换底层才不难这一条算是我的习惯不管底层用数组还是链表对外暴露的函数名和参数尽量保持一致。比如push(stack, value)、pop(stack)、enqueue(queue, value)、dequeue(queue)让上层代码只跟这组接口打交道。这样做的收益很明显。你从数组栈换成链表栈调用方一行都不用改笔试手写代码时考官也容易看懂你的结构设计。更重要的是接口统一后你可以在同一套 main 函数里测试多种实现哪个有 bug 马上就能对比出来。我后面给的测试模板就是建立在这个习惯上的。先想清楚结构选型再动手写节点这是我认为最重要的一步。接下来就从链表这个“地基”开始拆。2. 链表实现核心细节链表本身不只是三个结构里的一个它还是“链表栈”和“链表队列”的底层骨架。所以我把链表的过程写细一点后面实现栈和队列时你会发现其实就是在“复用同一套指针操作”。2.1 先有一个趁手的节点定义在 C 语言里最常见的节点定义长这样typedef struct Node { int data; struct Node *next; } Node;注意struct Node *next这行next是指向自身类型的指针。有人一开始会写Node *next但在这里还不行因为 typedef 的名字在这个结构体内部还没生效编译器还没看到完整的struct Node。所以在结构体内部一定要写struct Node *等结构体定义完了后面创建变量或参数时再用Node就方便了。节点还有两个容易忽略的细节。一是data类型这里用 int 是为了演示你可以改成任意业务类型甚至是一个 void* 指针这样链表就能存任意结构了。二是createNode函数最好单独写并且检查 malloc 的返回值我见过不少代码在 malloc 后不判空程序在内存不足时直接崩溃调试起来非常痛苦。节点创建函数如下Node* createNode(int val) { Node *n (Node *)malloc(sizeof(Node)); if (n NULL) { return NULL; } n-data val; n-next NULL; return n; }2.2 一个哨兵头节点省掉一半特殊情况链表写起来常见的痛点是“第一个节点”和“最后一个节点”总是需要特殊判断。比如在头部插入一个节点要改 head 指针本身删除最后一个节点要把前一个节点的 next 置空。这些判断代码不难但容易漏。我的做法是引入一个“哨兵头节点”也就是 dummy 节点。它不存业务数据只占一个位置让真正的头节点永远不是第一个节点。这样插入和删除的逻辑就被统一了不管操作位置是 0 还是中间都是同一种写法。下面这两段代码是带哨兵的插入和删除可以先感受一下这种写法Node* insertAt(Node *head, int pos, int val) { Node dummy; dummy.next head; Node *p dummy; int idx 0; while (p-next ! NULL idx pos) { p p-next; idx; } Node *newNode createNode(val); if (newNode NULL) { return dummy.next; } newNode-next p-next; p-next newNode; return dummy.next; } Node* deleteAt(Node *head, int pos) { Node dummy; dummy.next head; Node *p dummy; int idx 0; while (p-next ! NULL idx pos) { p p-next; idx; } if (p-next ! NULL) { Node *del p-next; p-next del-next; free(del); } return dummy.next; }这里dummy是栈上的局部变量不是 malloc 出来的所以用完不用 free 它我们把dummy.next作为新的头指针返回。while循环结束后p指向插入位置的前一个节点p-next就是要插入位置的当前节点。整个过程不需要判断head NULL因为即使链表为空dummy.next也是 NULLp-next操作仍然安全。你可能会有疑问返回值为什么还是dummy.next原因是插入到位置 0 时头节点会变化而 dummy 是局部变量无法在函数结束后继续被上层访问所以必须把新的头指针传出去。如果你把链表封装成带 head 的结构体那就不需要每次返回直接修改结构体里的 head 即可。两种封装方式我都在项目里用过简单练习时用返回指针更直白工程代码里则建议用结构体封装。2.3 插入、删除、反转把指针次序理清楚链表最容易写错的地方是插入和删除的指针次序。插入的时候必须先让新节点的 next 指向后一个节点再让前一个节点的 next 指向新节点。调换次序的后果是前一个节点先指向了新节点旧链表从此断开后半个链表找不回来内存就泄漏了。删除的时候正好相反要先让前一个节点的 next 跳过被删节点指向被删节点的后面然后才能 free 被删节点。很多时候段错误并不是因为 free 本身而是 free 之前没有把前后指针调整好或者 free 完之后还去访问被删节点的 next。反转链表是另一个高频考点也是检验指针次序的好题目。用三个指针 prev、cur、next 一趟扫完即可Node* reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; cur-next prev; prev cur; cur next; } return prev; }关键步骤是先保存cur-next再改cur-next prev。如果先改后保存原来的后继就丢了。三个指针里prev始终指向前一个节点循环结束时 prev 就是新的头节点。这段代码我每次笔试都写同一个版本原因就是固定顺序先存 next再改指针最后移动三个指针。链表这部分把插入、删除、反转写熟后面的栈就是“在头部插删”的特殊链表队列就是“一个在头、一个在尾”的特殊链表。下面进入栈的正题。3. 栈的数组实现与链表实现栈的语义很简单只能在栈顶进、栈顶出所以数组栈和链表栈的核心操作几乎一样短。差别主要在一个地方数组要管容量链表要管 malloc。3.1 数组栈扩容策略决定上限数组栈的经典结构是三个成员data 数组指针、capacity 容量、top 下标。top 从 -1 开始表示空栈push 时先判断容量不够就扩容pop 时先判空返回栈顶再减下标。我常用的结构体如下typedef struct { int *data; int capacity; int top; // 栈顶下标-1 表示空栈 } ArrayStack;push 和 pop 的实现void stackPush(ArrayStack *s, int val) { if (s-top 1 s-capacity) { int newCap s-capacity * 2; int *tmp (int *)realloc(s-data, newCap * sizeof(int)); if (tmp NULL) { return; } s-data tmp; s-capacity newCap; } s-top; s-data[s-top] val; } int stackPop(ArrayStack *s) { if (s-top 0) { return -1; } int val s-data[s-top]; s-top--; return val; }扩容为什么翻倍“翻倍增长”能让扩容的均摊代价变成 O(1)。假设容量从 1 开始每次翻倍扩容时复制数据的总次数加起来是 1248...最后一次不超过当前容量总复制量大约是当前容量的两倍。如果容量只加 1每次 push 都可能扩容复制量累计成 O(n^2)。当然翻倍也有代价容量很大但栈很空时会浪费内存我习惯在容量明显超过使用量时才考虑缩容比如capacity 1024 top capacity / 4时缩到一半避免频繁扩容缩容互相打架。还有一点要说明stackPop返回 -1 作为错误值是因为演示代码只处理非负整数。实际工程里栈可能存任意 int-1 也可能是合法值。更稳的做法是用输出参数比如int pop(Stack *s, int *out)返回 0 表示成功、-1 表示失败。接口一改后面所有调用点都要跟着改所以建议一开始就把接口想清楚。3.2 链表栈入栈出栈都在头部链表栈的思路非常直接把链表的头部当作栈顶。入栈就是创建一个新节点让它指向原来的 top再把 top 更新为新节点。出栈就是保存 top取出数据top 后移再 free 旧节点。结构体只需要一个 top 指针typedef struct NodeStack { Node *top; } NodeStack; void linkedStackPush(NodeStack *s, int val) { Node *newNode createNode(val); if (newNode NULL) { return; } newNode-next s-top; s-top newNode; } int linkedStackPop(NodeStack *s) { if (s-top NULL) { return -1; } Node *del s-top; int val del-data; s-top del-next; free(del); return val; }这个实现易错在两个地方。第一个是入栈顺序不能换newNode-next s-top必须在s-top newNode之前否则新节点自己指向了自己。第二个是出栈时先保存要 free 的节点再移动 top。不少新手写s-top s-top-next; free(s-top);结果把新栈顶给 free 了这是经典错误。链表栈和数组栈的性能差异我在第 1 部分已经说过链表栈省去了扩容搬移但每次 push 都多一次 malloc。实测下来数据规模小的时候差异不明显一旦频繁 push 几十万次malloc 的耗时会明显高于数组栈的扩容均摊。所以笔试题里我优先写数组栈只有题目明确要求“用链表实现栈”时才走链表。3.3 实战括号匹配和逆波兰式栈的两个经典应用很适合用来检验任意一种栈实现是否靠谱。第一个是括号匹配int isBalanced(const char *s) { ArrayStack stack; stackInit(stack, 32); while (*s) { if (*s ( || *s [ || *s {) { stackPush(stack, *s); } else if (*s ) || *s ] || *s }) { int left stackPop(stack); if (left -1) { return 0; } if (*s ) left ! () return 0; if (*s ] left ! [) return 0; if (*s } left ! {) return 0; } s; } return stack.top 0; }匹配的原理很朴素遇到左括号就入栈遇到右括号就出栈并检查是否配对。只要中间出现“栈空却遇到右括号”或“配对失败”就说明括号不合法。最后栈空表示所有左括号都找到了对应的右括号。这个例子能测出你的栈是否支持连续压入、弹出以及空栈保护是否做得到位。第二个是逆波兰式求值这里的数字和运算符都从输入里取遇到数字就入栈遇到运算符就弹出两个操作数计算后再压回去int evalRPN(const char **tokens, int n) { ArrayStack stack; stackInit(stack, 16); for (int i 0; i n; i) { const char *t tokens[i]; if (t[0] 0 t[0] 9) { stackPush(stack, atoi(t)); } else { int b stackPop(stack); int a stackPop(stack); switch (t[0]) { case : stackPush(stack, a b); break; case -: stackPush(stack, a - b); break; case *: stackPush(stack, a * b); break; case /: stackPush(stack, a / b); break; } } } return stackPop(stack); }这个示例偷了一点懒只处理了单个字符的非负整数。真实场景里数字可能是多位数也可能是负数那就要把 token 切成更细致的格式再解析。这里不展开重点是体会栈在“临时保存中间结果”这件事上的作用。把这两个应用跑通你的数组栈和链表栈基本就算过关了。4. 队列循环数组与链表方案队列的结构关键在“两头”入队从队尾出队从队头。这两端可能会在同一个数组里来回移动所以需要处理“环形”逻辑。链表队列没这个环的问题但要在 front 和 rear 两个指针之间做好配合。4.1 循环数组队列判空判满要讲套路直接开一个数组当队列出队时 front 后移入队时 rear 后移很快会遇到一个问题队头空出来了rear 却已经到数组末尾无法再入队。解决办法是把数组看成环形用取模运算把下标回绕到数组开头。我的结构体里特意加了 count这样判空和判满都不用靠 front 和 rear 的巧合来猜typedef struct { int *data; int capacity; int front; // 队首下标出队时移动 int rear; // 下一个入队位置 int count; // 当前元素个数 } CirQueue;入队、出队和扩容的代码如下void enqueue(CirQueue *q, int val) { if (q-count q-capacity) { int newCap q-capacity * 2; int *tmp (int *)malloc(newCap * sizeof(int)); for (int i 0; i q-count; i) { tmp[i] q-data[(q-front i) % q-capacity]; } free(q-data); q-data tmp; q-front 0; q-rear q-count; q-capacity newCap; } q-data[q-rear] val; q-rear (q-rear 1) % q-capacity; q-count; } int dequeue(CirQueue *q) { if (q-count 0) { return -1; } int val q-data[q-front]; q-front (q-front 1) % q-capacity; q-count--; return val; }扩容这一段其实是“重新排队”先把旧数组按从头到尾的顺序搬到新数组再把 front 重置为 0rear 放在 count 的位置。搬完后队列在物理上也变成了连续的一整段取模逻辑可以继续正常工作。判断队列是否为空看清 count比看 front 和 rear 是否相等更直观也避免了“空队列”和“满队列”状态下一不留神就混在一起的问题。我见过不少人用“浪费一个格子”的办法区分空和满front rear 表示空(rear 1) % capacity front表示满。这样做省一个 count 成员但容量实际少了 1而且代码一复杂就容易把判断写反。两者没有绝对优劣建议第一次写循环队列时老老实实加 count让代码意图更直白。4.2 链表队列小心尾部指针的边界链表队列的实现就是用两个指针分别指向链表的头和尾。入队在 rear 后面挂新节点出队从 front 拿掉节点。特殊之处在于队列从空到非空、从非空到空这两个临界点typedef struct { Node *front; Node *rear; } LinkedQueue; void linkedEnqueue(LinkedQueue *q, int val) { Node *newNode createNode(val); if (newNode NULL) { return; } if (q-rear NULL) { q-front newNode; } else { q-rear-next newNode; } q-rear newNode; } int linkedDequeue(LinkedQueue *q) { if (q-front NULL) { return -1; } Node *del q-front; int val del-data; q-front del-next; if (q-front NULL) { q-rear NULL; } free(del); return val; }这里最容易被忽略的是linkedDequeue里的最后一个 if。当队列只有一个节点时q-front被后移成 NULL但q-rear仍然指向这个已经被 free 的节点。如果不把 rear 也置空下一次入队时q-rear-next newNode就会对悬空指针做写入直接段错误。我初期写队列踩过好几次这种坑后来养成一个习惯只要动到 front 或 rear就在操作后问自己“另一个指针需不需要同步更新”。链表队列和循环数组队列还有一个细微差别链表队列的 rear 永远指向最后一个节点不存在“队列满”的状态但每次入队都要 malloc 一次节点出队又要 free。如果你的业务对延迟要求很高malloc/free 的波动可能比数组扩容更明显。选型时最好先用数据压一遍不要只看理论复杂度。4.3 队列的应用场景从 BFS 到任务调度队列最典型的应用是广度优先搜索。在图上从起点出发按层扩展每一层节点都要先放进队列再依次处理。我写了一个最简 BFS 骨架用的是刚才的循环数组队列void bfs(int start, int n, int (*graph)[n]) { CirQueue q; queueInit(q, n); int *visited (int *)calloc(n, sizeof(int)); visited[start] 1; enqueue(q, start); while (q.count 0) { int cur dequeue(q); printf(%d , cur); for (int i 0; i n; i) { if (graph[cur][i] !visited[i]) { visited[i] 1; enqueue(q, i); } } } printf(\n); free(visited); }这段代码用q.count 0作为循环条件本质就是在测队列是否为空。为什么 BFS 要用队列而不是栈因为队列先进先出能保证先发现的节点先被扩展从而按距离递增的顺序访问如果用栈就退化成了 DFS路径顺序就乱了。任务调度也是同样的逻辑先来的请求先处理来的顺序不能乱掉。这两种场景都能直接把队列的实现拿过去用。5. 常见问题与调试实录结构和代码都写完了我想专门聊一聊我在大量练习里遇见的错误。很多人代码写得快但在调试上花了很多时间其实大多数都是几个老问题。5.1 段错误的几类来源和现场特征链表、栈、队列相关的段错误归纳起来通常只有三类空指针解引用、野指针访问、越界写。空指针很好认调试器会告诉你访问地址是 0x0野指针大多是 free 之后没把指针置空或者修改 next 时绕过了某个节点越界写经常发生在数组栈扩容时容量算错数据写到了data[capacity]之后。我举一个常见的“活例子”删除链表中某个节点后代码再用一个遍历函数打印所有节点数据。如果删除时只改了前驱的 next没有释放内存整个链表还能正常工作如果 free 之后又错误地继续访问了 del 节点那表现出来的就是“有时候能跑有时候崩溃”因为那块内存已经被分配器回收内容随时可能被改写。这类问题最坑表面看不出来规律实际原因就是访问了已经不属于自己的内存。5.2 内存泄漏与重复释放Valgrind 是最好的助手C 语言里没人替你回收内存漏了就是漏了。最简单的验证方法是 Valgrind零侵入直接编译后把可执行文件丢给它就行gcc -g -Wall -fsanitizeaddress -o demo demo.c valgrind --leak-checkfull ./demo代码编译时我习惯加-g这样报错里有行号。-Wall开启常见警告很多未用到的函数、类型不匹配都能提前暴露。-fsanitizeaddress是另一个利器数组越界、释放后访问这类问题跑起来就会直接报错并告诉你具体位置比纯 Valgrind 更快。等程序稳定了再去掉 sanitizer因为它的内存占用比较大。Valgrind 报告里最需要关注的字段是definitely lost和Invalid read/write。前者说明你漏了 free典型原因包括删除节点时没有把前驱的 next 跳过或者反转链表时把某个节点的指针弄丢了。后者说明你访问了已释放或越界的内存。我第一次用 Valgrind 的时候发现一个大程序里有 20 多处definitely lost全是早期写链表时留下来的“指针孤儿”改掉之后整晚都安心得多。5.3 用断言和防御式检查兜住低级错误一套负责的代码应该在“发现问题”和“掩盖问题”之间选择前者。C 语言里最廉价的防御是assertassert(p ! NULL)、assert(top -1)都是很好的观察点。断言只会在调试构建里生效正式编译加-DNDEBUG就自动关闭不影响性能。另一个建议是给所有“可能失败的接口”设计明确的错误返回约定。比如我上面写的return -1虽然简单但只能处理非负数据。更通用的做法是int tryPop(ArrayStack *s, int *out) { if (s-top 0) { return -1; } *out s-data[s-top]; s-top--; return 0; }调用方先看返回值再拿*out这样就不会出现“把 -1 当合法数据”的误判。这种设计学习曲线不高但对代码维护的帮助非常大尤其是在后面涉及到图算法、缓冲区管理等复杂场景时。6. 实操总结与往后的扩展建议到这里链表、栈、队列的 C 语言实现主体已经讲完。最后我想把测试方法和一个大的扩展方向留给你。6.1 一份简单但有效的测试模板数据结构代码光靠眼睛看不出来对错我习惯用宏搭一个极简测试框架static int test_count 0; #define CHECK(expr) do { \ test_count; \ if (!(expr)) { \ printf(FAIL: %s (line %d)\n, #expr, __LINE__); \ } \ } while (0)然后在 main 里依次验证正常、边界和异常三类用例。正常用例连续 push 5 个元素连续 pop 检查顺序。边界用例空链表插入、删除最后一个节点、队列只剩一个元素。异常用例空栈 pop、空队列 dequeue、删除不存在的位置。每一次测试跑完如果FAIL打印为 0我才敢说这一版基本稳了。边界用例的重要性远高于正常用例。我记得写循环数组队列时正常入队出队怎么跑都对唯独在“队列刚好满”和“队列只有一个元素”这两个状态下出了问题后来正是靠边界用例把 bug 抓出来。如果你自己实现这三种结构一定把边界情况列成清单别偷懒。6.2 从这堂基础课往外扩展的方向链表、栈、队列是线性结构的入门三件套但掌握之后可以直线往里走。最先值得做的是双向链表节点里加一个 prev 指针删除操作不需要从头遍历前驱代价是每个节点多 8 字节64 位系统下。接着是循环链表适合做约瑟夫环、进程轮转这类场景。再往上可以看跳表它给有序链表加了几层索引让查找从 O(n) 降到接近 O(log n)很多高性能缓存都会用到。栈和队列的进阶方向则是单调栈、单调队列、优先队列它们在算法题里出场率极高。我个人的体会是这三个结构的 C 语言实现本质上是在训练“手动管理内存 精确控制指针”的能力。能用好它们往后看树、图、哈希表思路都会顺很多。每实现一个结构都顺手写一遍测试宏和 Valgrind 检查这个习惯带到任何 C 项目里都不过时。如果你正在学数据结构的路上我建议你别只抄代码把示例跑通后再故意制造几个 bug比如交换插入的指针顺序、忘记更新 rear然后观察程序怎么崩溃。这种“主动失败”的训练方式比十遍默写代码更能加深理解。数据结构不难难的是自己动手踩一遍坑然后在下一次遇到同样的指针问题时能笑着说这个坑我熟。