C语言手写栈与队列：从数组实现到链式存储详解

我第一次认真用C语言写栈和队列不是在课堂作业里而是在一个临时接的小工具中那是一个旧的命令行程序要加一个“撤销”功能操作记录必须按最近一次来恢复另一块日志要按产生顺序逐条转发先到先处理。前者就是后进先出后者就是先进先出。我翻出教材里的栈和队列章节才意识到这两样东西几乎是所有复杂系统的基础骨架。C语言跟其他高级语言不太一样标准库里没有现成的容器vector、list、stack 都得自己造。所以理解栈和队列不光是背“后进先出”“先进先出”这两个定义而是要在数组、指针、内存管理上都动真格。这篇文章不打算重复教材里的概念陈述我按照自己动手实现时的顺序把顺序栈、链式栈、循环队列、链式队列一个个写出来顺带讲清楚每一步背后的设计原因和调试心得。文章最后再延伸到工程实践聊聊它对消息队列、线程池任务队列这些场景的映射关系。适合看这篇文章的人正在学C语言数据结构的学生准备面试需要快速复习的开发者或者项目里需要手写一个简单数据结构的嵌入式、服务端同学。看完之后你至少能把一个可运行、可测试的栈和队列写出来并且知道边界条件为什么会出错。1. 动手前先分清数据结构栈、内存栈区、算法堆不是一回事讲C语言的栈和队列之前必须先解决一个让无数新手认知拧巴的问题栈这个词在计算机领域有三个完全不同的含义很多初学者把它们搅在一起后面越学越混乱。1.1 数据结构里的栈和队列到底在约束什么数据结构里的栈和队列本质上都是线性表区别在于操作受限的位置。栈只允许在同一端插入和删除这一端叫栈顶另一端叫栈底操作模式是后进先出。你可以把它类比成一叠盘子后放上去的盘子一定先被拿走你没法直接从中间抽一个。队列则只允许在一端插入、在另一端删除插入端叫队尾删除端叫队头操作模式是先进先出。这个更直观就像排队买奶茶先来的人先拿到后来的人只能站到队伍末尾。这两个结构的共同点是数据之间是线性关系一个挨一个排列。但它们又比普通数组多了一条约束——你不能随意访问中间元素只能从固定的口子进出。这条约束看起来是限制实际上带来了两个巨大好处操作逻辑简单边界清晰。正是因为接口少很多复杂系统的状态流转才敢放心用它们来管理。1.2 内存里的栈区、堆区与数据结构栈不能混为一谈C语言程序运行时内存会划分成若干区域其中两个区域的名字特别容易带来误解栈区和堆区。栈区由编译器自动管理存储局部变量、函数参数、返回地址。每次函数调用会压入一个栈帧函数返回时弹出栈帧它确实用到了后进先出的思想。你可以说“函数调用栈使用了栈这种组织方式”但不能说“栈区就是数据结构里的栈”。栈区是操作系统和编译器共同维护的一块物理内存区域数据结构栈是一种抽象的逻辑结构。堆区就更微妙了。运行期用malloc/calloc/realloc动态分配的内存就在堆区它需要你手动free。而数据结构里也有一个“堆Heap”通常指堆排序和优先队列里的二叉堆那是一种树形结构跟栈、队列完全不是一类东西。所以学的时候建议把三条线分开记概念本质典型用途栈Stack线性结构后进先出表达式求值、括号匹配、函数调用管理队列Queue线性结构先进先出任务调度、缓冲区、消息传递堆Heap内存区域或树形结构动态内存分配、优先队列、堆排序在文章里我们只讨论第一行和第二行至于内存布局里的栈区和堆区是“实现这些数据结构时底层内存从哪来”的背景知识。2. 顺序栈数组加 top 指针从固定容量到动态扩容顺序栈是所有栈实现里最直观、最容易写对的一种。核心思路是用一段连续内存数组保存元素再用一个整数记录栈顶位置。2.1 结构体设计top 为什么要从 -1 开始顺序栈的结构体一般长这样#include stdio.h #include stdlib.h #define INIT_CAPACITY 8 typedef struct { int *data; int top; // 栈顶下标指向栈顶元素 int capacity; // 当前容量 } SeqStack;top的初始值有两种流派一种初始化为-1一种初始化为0。我推荐前者而且必须配合“先移动指针再写入”的入栈逻辑。为什么用-1而不是0因为数组下标从 0 开始空栈时栈里没有任何元素top指向一个不存在的下标才是最合理的。如果初始化成 0空栈和“栈里已有一个元素在下标 0”的状态就很难区分要么多维护一个 size 字段要么每次都要想“top 到底指向栈顶还是栈顶下一个位置”。用-1的写法非常统一入栈先top再data[top] value出栈先*out data[top]再--top判空top 0栈顶元素data[top]2.2 入栈、出栈、取栈顶的完整代码SeqStack *stack_create(void) { SeqStack *s (SeqStack *)malloc(sizeof(SeqStack)); if (s NULL) return NULL; s-data (int *)malloc(sizeof(int) * INIT_CAPACITY); if (s-data NULL) { free(s); return NULL; } s-top -1; s-capacity INIT_CAPACITY; return s; } void stack_destroy(SeqStack *s) { if (s NULL) return; free(s-data); free(s); } int stack_push(SeqStack *s, int value) { if (s NULL || s-data NULL) return -1; // 栈满了就扩容 if (s-top s-capacity - 1) { int new_cap s-capacity * 2; int *new_data (int *)realloc(s-data, sizeof(int) * new_cap); if (new_data NULL) return -1; s-data new_data; s-capacity new_cap; } s-top; s-data[s-top] value; return 0; } int stack_pop(SeqStack *s, int *out) { if (s NULL || out NULL || s-top 0) return -1; *out s-data[s-top]; s-top--; return 0; } int stack_peek(SeqStack *s, int *out) { if (s NULL || out NULL || s-top 0) return -1; *out s-data[s-top]; return 0; } int stack_empty(SeqStack *s) { return s NULL || s-top 0; }这里有个细节值得展开为什么出栈时不用重置data[top]的值因为top已经指向了新的栈顶旧位置的数据虽然还残留在数组里但已经不在栈的逻辑范围内。下一次入栈时新的值会直接覆盖它。对于int这种基本类型没问题如果栈里存的是指针出栈时就要考虑要不要先置空防止有人拿着旧下标误访问已经“逻辑删除”的元素。2.3 动态扩容realloc 的错误用法比想象中多很多教材里的顺序栈容量固定但实际项目里你很难预估数据量所以动态扩容是刚需。扩容最常用的函数是realloc它能在原内存块上扩展如果原地址后面空间不够会重新分配一块更大的内存并复制旧数据。用的时候有一个非常经典的错误// 错误示范 s-data (int *)realloc(s-data, new_cap * sizeof(int));问题在于如果realloc失败它会返回NULL但原来的内存块不会释放。你把NULL直接赋给s-data原来的指针就丢了内存既没扩容成功也没办法释放等于泄漏。正确写法是用一个临时变量接收返回值成功后再赋值int *new_data (int *)realloc(s-data, sizeof(int) * new_cap); if (new_data NULL) return -1; s-data new_data; s-capacity new_cap;另外一个经验是扩容因子建议选 1.5 到 2 倍之间太小会导致频繁扩容太大一次性占太多内存。配合realloc的原地扩展能力2 倍是比较稳妥的选择。2.4 共享栈两个栈共用一个数组顺序栈还有一种变体叫共享栈在面试题里偶尔会出现用一个数组同时实现两个栈一个从数组头部往后增长一个从数组尾部往前增长。typedef struct { int *data; int left_top; // 左栈栈顶初始 -1 int right_top; // 右栈栈顶初始 capacity int capacity; } SharedStack;左栈入栈时data[left_top] value右栈入栈时data[--right_top] value左栈和右栈相遇时表示满。它能做到动态利用空间一个栈空闲时另一个栈可以多用一些避免两个栈各自预留一半空间造成浪费。3. 链式栈头插法背后的内存管理细节顺序栈的缺点是要预分配连续内存扩容时也可能搬移数据。链式栈则用一个个单独分配的节点来保存元素从空间上彻底摆脱了“连续内存”的束缚。3.1 为什么链式栈都用头插法链式栈的结构是两个结构体一个节点结构体保存数据和下一个节点指针一个栈结构体只保存栈顶指针。typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; } LinkedStack;入栈时把新节点插入链表头部出栈时删除头部节点。为什么不用尾插法因为不管是顺序栈还是链式栈栈的核心操作都在栈顶头插法让入栈和出栈都只操作头节点时间复杂度都是 O(1)。如果坚持用尾插法你还要额外维护一个尾指针入栈时更新尾指针出栈时还得从头部遍历到尾部找到新的尾节点反而把简单问题复杂化了。3.2 链式栈的完整实现LinkedStack *lstack_create(void) { LinkedStack *s (LinkedStack *)malloc(sizeof(LinkedStack)); if (s NULL) return NULL; s-top NULL; return s; } void lstack_destroy(LinkedStack *s) { if (s NULL) return; StackNode *cur s-top; while (cur ! NULL) { StackNode *tmp cur; cur cur-next; free(tmp); } free(s); } int lstack_push(LinkedStack *s, int value) { if (s NULL) return -1; StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) return -1; node-data value; node-next s-top; s-top node; return 0; } int lstack_pop(LinkedStack *s, int *out) { if (s NULL || out NULL || s-top NULL) return -1; *out s-top-data; StackNode *tmp s-top; s-top s-top-next; free(tmp); return 0; }这段代码里最值得说的是lstack_destroy。很多人销毁链表栈时只free了栈结构体本身忘了遍历释放所有节点结果就是内存泄漏。在 C 语言里malloc和free必须一一对应栈结构体是一个malloc每个节点是一次malloc释放时一个都不能少。3.3 顺序栈 vs 链式栈怎么选很多初学者会问既然链式栈不用扩容是不是应该优先用它还真不一定。频繁malloc和free是有系统调用开销的虽然现代分配器做了不少优化但性能仍然比数组下标操作慢一个量级。对于元素量可预估、追求性能的场景顺序栈是首选对于元素量无法预知、需要频繁动态增减的场景链式栈更合适。还有一个折中方案链式存储加节点池。一次性分配一批节点放进空闲链表需要时从池里取不用时归还到池里这样既保留了链式结构的灵活性又避免了频繁 malloc。这在嵌入式和高性能服务器里很常见不过作为学习阶段先把基础的链式实现写对更重要。4. 循环队列环形取模与判空判满的设计取舍队列的顺序实现比栈要麻烦一些核心原因是如果只用数组和两个下标出队后前面的空间会被白白浪费。4.1 假溢出普通数组模拟队列的问题想象一个长度为 8 的数组用front指向队头用rear指向队尾的下一个空位。入队时data[rear] value出队时*out data[front]。一开始没问题但随着出队front不断往后移动数组前部的空间变成“废区”虽然物理上还能用但逻辑上已经够不着了。当rear到达数组末尾时即使前面空着大片位置也无法继续入队。这就是假溢出数组没真满但队尾已经走到头了。解决办法就是循环队列让rear走到末尾后回到下标 0把数组逻辑上弯成一个环。移动下标时不再用front/rear而是用取模运算front (front 1) % capacity; rear (rear 1) % capacity;4.2 判空判满为什么标准做法要浪费一个元素空间循环队列的好写之处在于只要处理好“空”和“满”两种边界其他情况都水到渠成。但恰恰是边界判断特别容易踩坑。先看判空front rear没毛病。再看判满。如果满的条件也写成front rear那它和判空就冲突了——到底队列是空的还是满的根本无法区分。所以必须换一个条件。标准做法是让队列保持至少一个空位满的条件写成(rear 1) % capacity front也就是说当rear的下一个位置是front时认为队列满了。这样会牺牲一个数组单元但换来了足够清晰的边界判断。循环队列能放的元素个数最多是capacity - 1。如果你实在不想浪费这个空间也可以引入一个size字段记录当前元素个数入队时size出队时size--。判空条件变成size 0判满条件变成size capacity。这样front rear不会引起歧义因为size已经明确表达了状态。很多工程实现确实这么做不过教科书里面更常考察浪费一个元素空间的标准写法。4.3 循环队列完整代码与边界测试#define QUEUE_CAPACITY 8 typedef struct { int data[QUEUE_CAPACITY]; int front; // 队头下标 int rear; // 队尾的下一个空位 } CircleQueue; void queue_init(CircleQueue *q) { q-front 0; q-rear 0; } int queue_empty(CircleQueue *q) { return q-front q-rear; } int queue_full(CircleQueue *q) { return (q-rear 1) % QUEUE_CAPACITY q-front; } int queue_push(CircleQueue *q, int value) { if (queue_full(q)) return -1; q-data[q-rear] value; q-rear (q-rear 1) % QUEUE_CAPACITY; return 0; } int queue_pop(CircleQueue *q, int *out) { if (queue_empty(q)) return -1; *out q-data[q-front]; q-front (q-front 1) % QUEUE_CAPACITY; return 0; } int queue_size(CircleQueue *q) { return (q-rear - q-front QUEUE_CAPACITY) % QUEUE_CAPACITY; }我自己在测试循环队列时会故意做这样几个操作连续入队 7 个元素第 8 个应该失败因为浪费了一个空位出队 3 个再入队 3 个确认rear能绕回数组开头不断入队出队每次pop后检查queue_size是否等于实际元素个数。这几个用例能覆盖 90% 的循环队列边界问题。如果你把容量变成 1还会考验到自己对取模运算的理解容量为 1 的循环队列任何入队都会失败因为最多只能放 0 个元素。5. 链式队列front 和 rear 两个指针的协同链式队列跟链式栈最大的不同是队列需要两个指针一个管理队头一个管理队尾。入队在尾部出队在头部。5.1 结构设计与入队逻辑typedef struct QueueNode { int data; struct QueueNode *next; } QueueNode; typedef struct { QueueNode *front; QueueNode *rear; } LinkedQueue;入队时如果队列为空front和rear都指向新节点如果队列不为空新节点挂到rear-next后面然后更新rear。出队时正好相反取出front节点front后移如果队列变为空要把rear也置空。int lqueue_push(LinkedQueue *q, int value) { if (q NULL) return -1; QueueNode *node (QueueNode *)malloc(sizeof(QueueNode)); if (node NULL) return -1; node-data value; node-next NULL; if (q-rear NULL) { q-front node; q-rear node; } else { q-rear-next node; q-rear node; } return 0; } int lqueue_pop(LinkedQueue *q, int *out) { if (q NULL || out NULL || q-front NULL) return -1; *out q-front-data; QueueNode *tmp q-front; q-front q-front-next; if (q-front NULL) { q-rear NULL; } free(tmp); return 0; }5.2 出队时最容易漏掉的指针置空链式队列的坑主要集中在一个地方出队后队列变空时必须把rear置为 NULL。如果只更新front不更新rear那么rear会继续指向已经被 free 的节点形成悬空指针。下次入队时q-rear NULL的判断会失效代码会走到else分支试图往一块已经释放的内存上写next轻则产生野指针访问重则直接段错误。这跟链式栈不一样。链式栈出栈只动top除非销毁否则top为空就代表栈空没有第二个指针需要同步。但队列有两个指针一个指向入口一个指向出口出口空了不代表入口还安全协作关系必须维护好。5.3 带头结点和不带头结点的链队教材里链式队列还分两种写法带头结点和不带头结点。带头结点的链队front永远指向一个哑结点这个节点不存业务数据只起占位作用。判空条件变为front-next NULL入队时始终是rear-next node; rear node;不用再单独判断第一次入队的情况。好处是代码分支更少删除头节点时也更统一。不带头结点的链队就是上面我写的版本第一次入队和后续入队逻辑不同需要if (q-rear NULL)判断一次。两种都能用我个人更推荐不带头结点的版本配合LinkedQueue *封装原因是逻辑直观、没有多余的哑结点。但如果你写的是嵌入式底层的队列希望每条入队出队路径都尽量少分支带头结点会稍微快一点点。6. 经典应用括号匹配、表达式求值与函数调用栈学完四种种实现方式你可能会问这些东西实际能干嘛这一节用几个最经典的应用场景来回答也是面试和考试里出现频率最高的部分。6.1 括号匹配栈的“标定版”入门题给定一个只包含( ) [ ] { }的字符串判断括号是否合法匹配。典型的合法字符串是([{}])不合法的是([)]虽然左右括号数量相等但交叉嵌套是错误的。思路不复杂遇到左括号就入栈遇到右括号就从栈里弹出一个左括号检查是否匹配。如果最后栈为空说明所有括号都配上了。typedef struct { char data[128]; int top; } CharStack; void char_push(CharStack *st, char c) { st-data[st-top] c; } char char_pop(CharStack *st) { return st-data[st-top--]; } int is_valid_brackets(const char *s) { CharStack st; st.top -1; for (int i 0; s[i] ! \0; i) { char c s[i]; if (c ( || c [ || c {) { char_push(st, c); } else if (c ) || c ] || c }) { if (st.top 0) return 0; // 右括号多了 char left char_pop(st); if ((left ( c ! )) || (left [ c ! ]) || (left { c ! })) { return 0; // 括号类型不匹配 } } } return st.top 0; // 栈里还有左括号就说明多了 }这道题之所以经典是因为它把栈“只从一端操作”的特性表现得很彻底。字符串处理过程中你永远只关心最近出现的未匹配左括号这正是栈顶。6.2 中缀表达式转后缀表达式调度场思想计算机直接处理1 2 * 3这种中缀表达式很别扭因为要考虑运算符优先级。但把它转成后缀表达式1 2 3 * 后就可以用栈一次扫描求出结果。转换规则用到了两个结构一个栈保存运算符和左括号一个输出缓冲区保存后缀表达式。遇到数字直接输出遇到运算符把栈里优先级不低于当前运算符的依次弹出再压入当前运算符遇到左括号直接压栈遇到右括号把栈顶到左括号之间的运算符全部弹出。int op_priority(char c) { if (c || c -) return 1; if (c * || c /) return 2; return 0; } // 简化版只处理单个数字字符不处理空格和多位数字 void infix_to_suffix(const char *infix, char *suffix) { CharStack st; st.top -1; int j 0; for (int i 0; infix[i] ! \0; i) { char ch infix[i]; if (ch 0 ch 9) { suffix[j] ch; } else if (ch () { char_push(st, ch); } else if (ch )) { while (st.top 0 st.data[st.top] ! () { suffix[j] char_pop(st); } if (st.top 0 st.data[st.top] () { st.top--; // 弹出左括号 } } else if (ch || ch - || ch * || ch /) { while (st.top 0 st.data[st.top] ! ( op_priority(st.data[st.top]) op_priority(ch)) { suffix[j] char_pop(st); } char_push(st, ch); } } while (st.top 0) { suffix[j] char_pop(st); } suffix[j] \0; }求出后缀表达式后再用一个整数栈求值遇到数字压栈遇到运算符弹出两个操作数计算结果压回栈。这个简版代码限制很大比如数字只能是单字符、除法用整数除。真实项目里需要先做词法分析把多位数字和操作符拆成 token再走同样的调度场流程但核心栈思想不变。6.3 函数调用栈与递归的非递归改写每次函数调用系统都会在内存栈区压入一个栈帧保存局部变量、参数和返回地址。函数返回时栈帧弹出控制权回到调用点。因为函数调用总是“先调用的后返回”操作系统天然就用栈来管理这种嵌套关系。递归函数更是如此。递归深度过大时系统栈被压爆程序直接崩溃也就是常见的“栈溢出”。某些场景下你可以把递归改成显式栈系统帮你管理的隐式栈不要了自己用malloc分配内存建立一个显式栈手动压入待处理的子问题。这样栈的大小不再受系统限制而且可以更精确地控制内存占用。二叉树的非递归遍历就是典型例子前序、中序、后序遍历都能用循环加显式栈写出来。队列在工程里的角色则常常对应“生产者消费者模型”一个线程生产任务一个线程消费任务中间用一个队列缓冲。消息队列、线程池的任务队列本质都是“先进先出 多端并发”的扩展底层数据结构就是队列。线程池里的阻塞队列还会在入队、出队时加锁和条件变量保证多线程安全这已经超出了基础数据结构范畴但核心逻辑仍然是队列那套东西。7. 从刷题到工程栈与队列的常见坑和延伸数据结构的实现本身不难真正难的是边界条件和内存细节。这一节我把这几年里实际遇到的坑集中整理一下再聊一点延伸。7.1 top 指针约定不一致导致的混乱顺序栈最容易踩的坑是 top 初始值约定不清晰。有的人初始化为 -1有的人初始化为 0还有人把 top 定义成“栈顶元素的下一个位置”。如果同一个项目里两种写法混用读代码的人会非常崩溃。我的建议是在一个项目里从头到尾只保留一种约定并在结构体定义旁边注释清楚。上面我用的方案是 top 指向栈顶元素且初始为 -1这个约定在你写代码时逻辑最统一。无论写新代码还是 review 别人代码先确认 top 语义再动手。7.2 取模运算优先级和整数回绕循环队列里(rear 1) % capacity这个表达式括号一定不能省。C 语言的取模运算符优先级低于加号如果你写成rear 1 % capacity实际执行的是rear (1 % capacity)也就是rear 1完全失去循环回绕的能力。这种 bug 非常隐蔽编译不报错运行结果只在数组越界时才会暴露出来。另一个容易忽视的是队列长度公式(rear - front capacity) % capacity它之所以要加一个capacity再取模是因为rear - front可能为负数。比如front已经是 6rear绕回到 2实际元素个数是 4但直接2 - 6是-4再加容量 8 再取模就得到 4。7.3 内存泄漏、空指针、悬空指针C 语言写数据结构内存错误是最常见的。三个高频问题内存泄漏创建节点 malloc 了销毁时没 free。链式栈和链式队列尤其容易漏因为每个节点都是独立分配的。空指针访问出栈、出队前没有检查栈或队列是否为空。函数返回-1或者通过参数out返回数据时调用方必须检查返回值。悬空指针出队后队列为空但没有把rear置 NULL后续入队时访问已释放内存。排查这类问题我通常先用地址检查法在主要函数入口打印关键指针地址看哪个地址是 0x0 或者指向已释放区域。也可以用 Valgrind 跑一遍单元测试它会把每一处非法的内存读写精确到行号比自己肉眼扫代码高效得多。7.4 从基础数据结构延伸到阻塞队列和消息队列身边不少同学在学完栈和队列后会问课程里讲的东西跟网上说的“消息队列”“线程池阻塞队列”是一回事吗答案是底层思想一样但工程实现会多很多层。比如线程池的任务队列它通常不是一个裸的数组加两个下标而是一个带锁的环形缓冲区或者链表支持多线程同时入队、出队没有空时消费者线程会阻塞没有满时生产者线程会等待。这就是“阻塞队列”。消息队列跨进程甚至跨机器通信比线程内的队列复杂得多涉及到网络传输、持久化、事务、消息确认等机制。但不管外面包了多少层数据在内存中的排列方式仍然是“先进先出”的队列或“优先级排列”的优先队列。MySQL 底层里的冷热分离思想也跟队列有点关系热数据放在内存队列快速处理冷数据批量刷盘或归档本质上是按访问频率对数据进行分流排队。这些工程问题不会让你写一个struct Node *next但如果你连基础队列都实现不利索去理解那些设计就会非常吃力。7.5 一套适合巩固理解的练习组合如果你想真正吃透这两个结构我建议不要只抄一遍代码而是做四件事把文中的顺序栈、链式栈、循环队列、链式队列四个实现全部敲一遍每个都跑通上文的边界测试用括号匹配和表达式求值练手把栈当成一个已经封装好的工具来用试着把循环队列改成动态扩容版本容量满时重新分配一块更大的内存把旧数据重新排列到新数组开头找几道 C 语言相关的练习题字符串逆序用栈实现树的层序遍历用队列实现巩固“什么时候该用栈、什么时候该用队列”这个判断力。如果正在跟课程或刷在线题库建议每次写完都刻意检查一遍这个操作的边界条件有没有覆盖如果栈空/队列空怎么办如果内存分配失败怎么办把这些检查变成肌肉记忆之后你会发现写任何 C 语言代码都会稳很多。我自己整理这几个实现时最大的体会是栈和队列难的不是代码本身而是养成“先想边界再写逻辑”的习惯。顺序栈的 top 从 -1 开始、循环队列留一个空位判满、链式出队置空 rear这些处理都不是偶然的它们背后都对应着某个边界条件的取舍。把这些边界在草稿纸上先画清楚代码自然不容易错。