1. 为什么值得用C语言把栈和队列从零写一遍栈和队列是数据结构里最基础、也最容易被低估的两个结构。很多人C语言学完指针就开始刷算法题却很少愿意老老实实用手写一遍栈和队列。但真正到了面试、做项目、读中间件源码的时候会发现到处是它们的身影函数调用栈、浏览器前进后退、消息队列、阻塞队列、任务调度……这套底层能力还真不是靠背几道题能补上的。这篇文章我想用C语言把栈和队列完整实现一遍从结构体定义到入栈出栈、入队出队再到循环队列的取模边界、链式队列的内存释放每一个细节都会讲到。适合刚学完C语言指针、正在上数据结构课的同学也适合想回头补基础的在职开发。读完以后我希望你能做到不看任何参考代码直接在白纸上写出一个能跑、能释放内存的版本。1.1 栈后进先出离我们最近的底层结构栈是一种只允许在一端进行插入和删除的线性表这一端叫栈顶另一端叫栈底。插入操作叫入栈push删除操作叫出栈pop这种“后进先出”的规则内部元素永远被压在下面。你可以把它想成一摞盘子后放上去的盘子最先被拿走想拿最底下的盘子只能先把上面的全部搬走。别觉得这个规则太简单操作系统里的函数调用栈就是最典型的例子。每调用一个函数CPU会把当前函数的返回地址、局部变量和参数按顺序压入系统栈函数返回时再从栈顶弹出。递归深度过大导致“栈溢出”本质就是压入栈的调用帧太多把系统分配的空间撑爆了。所以栈不是一个只在课本里出现的数据结构它是整个程序运行时的重要底层机制。1.2 队列先进先出系统解耦的顶梁柱队列同样是操作受限的线性表但它限制得更“公平”只能在队尾插入从队首删除。排过队的人都能理解这种场景先来的人先被服务后来的人只能排在队尾。打印机作业队列、键盘缓冲区、消息中间件里的消息队列本质上都是这种先进先出FIFO模型。有意思的是队列在业务系统里的地位比栈还要高。拿消息队列来说它的三个核心作用——解耦、异步、削峰全都建立在这个先进先出的底层结构上。生产端把消息按顺序放进队列消费端按顺序取出处理两端不需要直接依赖彼此。如果只从数据结构层面看消息队列就是一张可以跨进程、跨机器访问的超级队列。底层基础决定上层架构这句话在队列身上体现得淋漓尽致。1.3 手写栈和队列能收获什么有人可能会问C语言标准库里没有数据结构容器写一遍我会用就行了为什么非要手写我的看法是手写一遍不是为了应付考试而是为了搞清楚三个关键问题数据存哪里、指针怎么移动、内存怎么释放。C语言的优势就在于它的内存管理是显式的。你定义一个数组当栈就要自己算清楚top的取值范围你malloc一个新节点就要自己记得在什么时候free。这些操作如果换成Java或Python几乎会被语法屏蔽掉。很多人在高级语言里用得顺手但一旦遇到内存泄漏、段错误、程序崩溃就完全不知道从哪查起根子就在于没在底层图上建立直觉。C语言手写栈和队列就是成本最低的补课方式。2. 顺序栈实战从数组到核心操作的完整实现2.1 栈的结构体设计为什么要用top而不直接操作数组下标顺序栈是用一段连续内存保存元素最简单的方式就是数组加一个栈顶游标。这个游标不是真正的指针而是一个整型下标它用来标记当前栈顶元素在数组中的位置。为什么不直接用指针因为数组加整型下标更容易理解而且后续判空、判满、遍历都更直观对于教学和工程调试都友好。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SeqStack;这里的data是栈的存储区top是栈顶下标。我习惯把top初始化为-1代表空栈。这样设计的好处是栈里有元素时top始终指向当前栈顶元素的位置空栈时top为-1不合法的数组下标一眼就能被识别出来调试时不容易混淆。2.2 初始化、判空、判满先搭好骨架很多人写数据结构代码喜欢把所有逻辑都塞进main函数这是一个很不好的习惯。更合理的做法是先封装好栈的基本状态函数让每个函数只做一件事。初始化、判空、判满看起来简单但它们是后续一切操作的基础。void initStack(SeqStack* s) { s-top -1; } int isEmpty(SeqStack* s) { return s-top -1; } int isFull(SeqStack* s) { return s-top MAX_SIZE - 1; }为什么判满条件是top MAX_SIZE - 1因为数组下标从0开始当top等于99时第100个位置也就是最后一个元素都已经被占用数组确实满了。封装这三个函数以后不管是在push还是在pop里需要判断状态时直接调用就行逻辑清晰也不会因为某个地方直接拿魔数判断而出错。2.3 push和pop的边界处理top移动顺序别搞反入栈和出栈是整个顺序栈的核心也是最容易写错的地方。这里有一个细节必须形成肌肉记忆入栈时要先移动top到下一个位置再写入数据出栈时要先取出当前top位置的元素再让top回退。用一句口诀就是“入栈先加后用出栈先用后减”。void push(SeqStack* s, int x) { if (isFull(s)) { printf(栈已满无法入栈\n); return; } s-data[s-top] x; } int pop(SeqStack* s) { if (isEmpty(s)) { printf(栈为空无法出栈\n); return -1; } return s-data[s-top--]; } int peek(SeqStack* s) { if (isEmpty(s)) { printf(栈为空\n); return -1; } return s-data[s-top]; }入栈使用top出栈使用top--代码很简洁但如果你是新手我建议先写展开版再缩写成这样。因为出错往往就出在先后顺序上如果入栈时先赋值再top第一个元素会被写进data[0]但top还是-1这意味着后面出栈时永远读不到它如果出栈时先top--再取元素就会把当前栈顶下标减到前一个位置取到的是上一个元素的数据。还有个值得一提的点上面代码在栈为空时返回-1作为错误标志。这在元素本身可能为-1的场景下并不严谨更可靠的做法是传入一个结果指针用返回值表示操作是否成功例如int pop(SeqStack* s, int* value)。实际项目中我推荐使用后者教学场景里先理解-1这个错误标记没有太大问题。2.4 顺序栈的局限栈顶指针从-1开始的好处关于top从-1开始还是从0开始网上有过不少争论。从-1开始top指向当前栈顶入栈就是先加后用从0开始top指向下一个可用位置入栈就是先赋值后加。两种写法都能实现栈但我个人强烈推荐从-1开始。原因有三点第一空栈的判断条件top -1非常直观第二取栈顶元素时直接使用data[top]不需要额外减一第三在调试打印时如果看到top是非法值就说明栈状态出了问题。我刚开始学栈的时候曾为了“从0开始更符合数组习惯”而选择从0初始化结果每次取栈顶都容易差一个位置越改越乱。后来统一改成从-1开始整个人神清气爽。顺序栈最大的局限就是容量固定。MAX_SIZE是100就最多放100个元素一旦数据量不可控就会满。解决思路是改用动态扩容的数组或者直接用链式栈。3. 链式栈与动态内存管理让数据量不再受限3.1 链式栈结构一个头指针就够了链式栈的底层是单链表但不需要头结点和尾结点只需要一个栈顶指针也就是链表的头指针。为什么一个指针就够因为栈的所有插入和删除都在栈顶进行而链表的头插和头删正好都是时间复杂度为O(1)的操作。数据量不确定时链式栈能随用随开天然没有容量上限只有内存不够的问题。typedef struct Node { int data; struct Node* next; } StackNode; typedef struct { StackNode* top; } LinkedStack;你可能注意到我在这里把栈顶指针又包装进了一个结构体。这样设计的好处是后续函数参数传递时只需要传一个LinkedStack*而不需要传二级指针去操作头结点。代码里看起来只多了一层结构体但可读性和安全性能提升一个档次。3.2 入栈和出栈的实现头插法加释放链式栈的入栈本质上就是在链表头部插入新节点。新节点的next指向当前栈顶然后让top指向新节点。栈顶永远是最新的节点符合后进先出的逻辑。void pushLinked(LinkedStack* stack, int x) { StackNode* newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败\n); return; } newNode-data x; newNode-next stack-top; stack-top newNode; } int popLinked(LinkedStack* stack, int* value) { if (stack-top NULL) { printf(栈为空\n); return 0; } StackNode* temp stack-top; *value temp-data; stack-top temp-next; free(temp); return 1; }出栈时先用临时指针保存当前栈顶节点取出数据再把栈顶指针移动到下一个节点最后释放原栈顶节点。这里顺序不能乱尤其是不能先free再移动top否则后面就访问到非法内存了。我见过不少新手写链式栈出栈把free放在移动top之前然后程序一跑就段错误原因就是“先杀鸡后取卵”。链式栈还有一个容易被忽略的点程序结束前要遍历整条链表并释放所有节点。因为malloc申请的内存不会随着函数结束自动回收不释放就会造成内存泄漏。在长期运行的服务里哪怕每次泄漏一个小节点积累起来也可能让内存占用持续飙升。3.3 顺序栈还是链式栈一张表说清楚很多人纠结到底是顺序栈好还是链式栈好。这个问题没有标准答案完全看使用场景。我做了个对比方便你根据项目情况选择维度顺序栈链式栈存储方式连续数组非连续节点容量固定可动态扩容动态受内存限制缓存友好性高连续内存访问快低节点分散易缺页额外空间开销几乎没有每个节点多一个next指针扩容复杂度需要搬移数据每次malloc一个节点适用场景数据量稳定、性能敏感数据量波动大、不稳定从实际工程角度讲普通应用里顺序栈更常见因为它内存连续、缓存命中率高而且不需要频繁malloc和free性能更可控。链式栈的意义更多在于理解动态内存管理和为后续链表结构打基础。真到了生产环境很多程序员会直接用现成的动态数组做栈原因也是同理。4. 循环队列解决假溢出问题的标准答案4.1 普通顺序队列的假溢出问题到底出在哪队列如果也用数组实现绕不开一个经典难题假溢出。假设数组大小为5一开始front和rear都指向0。入队三个元素后rear变成3出队两个元素后front变成2。此时数组0号位和1号位其实已经空了但rear已经移动到下标3后面继续入队只能往后走直到rear走到数组末尾5然后明明数组前半部分还有空位却报告“队列已满”。这就是假溢出的本质数组没有被真正填满但rear已经走到了边界前面空出来的位置没法利用。解决思路有两个一是每次出队后把后面的元素全部前移这样能解决问题但时间复杂度是O(n)效率太差二是把数组在逻辑上首尾相连做成循环队列。4.2 循环队列的取模机制与队满判断循环队列的思路是让rear在到达数组末尾后通过取模运算回到数组开头。假设数组长度为N那么rear (rear 1) % Nfront也一样。这样数组在逻辑上就变成了一个环假溢出的空间被重新利用。但这带来了新的问题循环队列里空队列时front和rear相等满队列时front和rear也会相等。同一个条件两种含义怎么区分最常见的做法是牺牲一个存储空间当(rear 1) % N front时认为队列已满。也就是说数组长度为N的循环队列实际最多只能存N-1个元素保证rear永远追不上front。#define QUEUE_SIZE 100 typedef struct { int data[QUEUE_SIZE]; int front; int rear; } CirQueue; void initQueue(CirQueue* q) { q-front 0; q-rear 0; } int isFullQueue(CirQueue* q) { return (q-rear 1) % QUEUE_SIZE q-front; } int isEmptyQueue(CirQueue* q) { return q-rear q-front; }4.3 循环队列核心代码实现入队时先判断队列是否已满然后写入数据再让rear移动到下一个位置。出队时先判断是否为空取出当前front指向的位置再让front移动到下一个位置。两处都用取模运算来实现环形回绕。void enQueue(CirQueue* q, int x) { if (isFullQueue(q)) { printf(队列已满\n); return; } q-data[q-rear] x; q-rear (q-rear 1) % QUEUE_SIZE; } int deQueue(CirQueue* q, int* value) { if (isEmptyQueue(q)) { printf(队列为空\n); return 0; } *value q-data[q-front]; q-front (q-front 1) % QUEUE_SIZE; return 1; }循环队列里有一个常见疑问为什么出队只需要移动front而不需要清空原来的data位置因为队列的可用性只由front和rear之间维护的逻辑区间决定旧数据留在原地没有关系下次入队写入新值时会自然覆盖。如果你在调试时想看队列当前有多少元素可以用这个公式计算长度count (rear - front QUEUE_SIZE) % QUEUE_SIZE这个公式必须加上QUEUE_SIZE再取模因为rear回绕到前面后rear-front可能是负数加一次长度后再取模才能得到正确结果。4.4 队满判断的三种方案对比牺牲一个存储单元并不是唯一区分队空队满的方法我把三种常见方案列在一起方便你根据场合选择方案实现思路优点缺点牺牲一个单元(rear1)%N front判满实现简单判定快浪费一个存储位增加size计数入队size出队size--不浪费空间需要维护额外变量增加tag标记每次操作改变tag不浪费空间逻辑绕容易出错我个人在实际写代码时第一选择永远是牺牲一个单元。原因很简单它最不容易出错。size方案虽然不浪费空间但每次入队和出队都要同步修改size稍不留神就会和实际元素数量不一致。tag方案更是调试地狱判断队空队满还要回看上一次操作是入队还是出队。数据结构代码最好写的是能用最少状态表达最清晰逻辑的方案而不是用更复杂的逻辑去节省一个数组位。5. 链式队列front和rear两个指针的默契配合5.1 链式队列结构设计两个指针各管一头链式队列和链式栈类似底层是一个单链表但队列的插入发生在尾部、删除发生在头部所以单靠一个头指针根本不够用必须同时维护front和rear两个指针。front指向队首节点负责出队rear指向队尾节点负责入队。两个指针各管一端插入和删除都能达到O(1)。typedef struct QNode { int data; struct QNode* next; } QNode; typedef struct { QNode* front; QNode* rear; } LinkedQueue;这里有个细节很多教材会给链式队列加一个头结点让空队列和非空队列的处理逻辑尽量统一。但我建议初学阶段先不要带头结点因为不带头结点的版本虽然代码里多一些判空分支却更容易帮你理解front和rear的语义尤其是“队列变空后两个指针都要更新”这个关键点。5.2 入队出队完整流程与一个隐蔽的坑入队操作相对简单新建节点如果队列为空让front和rear都指向它否则把新节点链到rear后面再让rear指向新节点。出队操作要小心队列为空时报错不为空时保存队首数据移动front并释放原队首节点。void enQueueLinked(LinkedQueue* q, int x) { QNode* newNode (QNode*)malloc(sizeof(QNode)); if (newNode NULL) { printf(内存分配失败\n); return; } newNode-data x; newNode-next NULL; if (q-rear NULL) { q-front newNode; q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } } int deQueueLinked(LinkedQueue* q, int* value) { if (q-front NULL) { printf(队列为空\n); return 0; } QNode* temp q-front; *value temp-data; q-front temp-next; if (q-front NULL) { q-rear NULL; } free(temp); return 1; }链式队列最容易踩的坑就在出队的最后一步当队列只有一个节点时front在q-front temp-next之后会变成NULL此时如果不把rear也置成NULLrear就会变成一个悬挂指针指向已经被释放的节点。下次再调用enQueueLinked时q-rear NULL这个判断会让程序走“空队列”分支吗不会因为rear指向的地址虽然内存已释放但不一定等于NULL。于是代码会执行q-rear-next newNode访问非法内存直接段错误。我当初调这个bug调了一晚上最后打印front和rear的地址才恍然大悟。所以切记链式队列如果长度为1出队后front和rear都必须置NULL。这个条件在标准教材里可能只是短短一句但真正写代码时漏掉的人不在少数。5.3 链式队列和循环队列的实际选型思路链式队列不用固定长度入队基本不会满除非malloc失败循环队列用固定数组队列长度可控性能稳定。实际工程里怎么选如果队列的最大长度可以预估比如打印任务队列、串口缓冲区我会选择循环队列因为不需要频繁malloc和free也没有内存碎片问题。如果队列长度不可控比如消息分发场景消费者速度偶尔跟不上我会选择链式队列让队列有时间缓冲压力。还有一个很现实的场景多线程环境下的阻塞队列。无论是循环队列还是链式队列底层结构经常都要加上锁和条件变量才能变成线程安全的阻塞队列。很多框架里实现的ArrayBlockingQueue底层就是循环队列LinkedBlockingQueue底层则是链式队列。所以你现在把循环队列和链式队列都吃透了以后看Java并发包或者其他框架源码都会顺手很多。6. 栈和队列在真实项目里的典型应用6.1 栈的经典应用函数调用、括号匹配、表达式求值栈最常见的应用在函数调用机制里。程序运行时系统栈保存着每一层函数调用的返回地址和局部变量。写递归函数时每一层递归就相当于一次入栈递归出口就是出栈。理解了这一点你就能明白为什么递归栈溢出的报错叫“Stack Overflow”也能明白为什么把递归改成循环时往往需要自己显式定义一个栈来模拟系统栈。括号匹配是另一个经典场景也非常容易手写。遍历字符串遇到左括号就入栈遇到右括号就看看栈顶是不是对应的左括号匹配则出栈不匹配则失败。最后检查栈是否为空如果还有左括号残留说明有多余左括号。这个算法看起来简单但在编译器、代码编辑器的语法检查里和它类似的思路每天都在被用到。表达式求值也离不开栈。中缀表达式转后缀表达式需要一个符号栈后缀表达式求值需要一个操作数栈。很多学生第一次接触这里时觉得抽象但用笔在纸上按步骤推一遍马上就能明白为什么操作符能通过栈来调整优先级。这也是为什么很多面试官喜欢拿表达式求值考候选人因为它能同时考察栈的理解和边界思维。6.2 队列的经典应用消息队列、阻塞队列、任务调度队列在真实项目里的出场频率可能比栈更高。最典型的是消息队列生产者和消费者之间通过队列解耦生产端不用关心谁在处理消费端也不用关心数据从哪来。你可以把它理解成一个巨大的仓库上游只管往仓库货架上放货下游按自己的节奏取货仓库本身通过队列结构保证了先进先出的公平顺序。阻塞队列则是并发编程中的明星。当队列为空消费者线程会自动进入等待状态直到生产者写入数据后唤醒它当队列满了生产者线程会被阻塞直到消费者取走数据。这种机制很好地平衡了生产速度和消费速度避免双方互相拖垮。热词里常提到的延迟队列底层也还是队列思路只不过出队时会检查元素的延迟时间是否已到本质上是在队列节点里增加了“可执行时间”字段。6.3 从数据结构看后端技术栈为什么底层基础决定上层架构很多做开发的朋友不止一次听过“全栈工程师”这个词也有人为了一张技术栈清单东拼西凑。但真正的全栈不是会几个框架就行的而是能理解每一层是怎么组合起来的。就拿前后端、中间件这一路说下来消息队列是队列调用链追踪是栈网络数据包缓冲区也是队列甚至连递归遍历目录都要用栈或者队列来手动模拟。这也是我极力推荐你用C语言手写一遍栈和队列的原因。你亲手管理过内存你踩过悬挂指针的坑你看过数组溢出后的诡异表现以后用任何高级语言和框架再遇到类似问题底层的直觉马上能告诉你问题大概出在哪。数据结构不是拿来背的是拿来理解世界的。7. 新手常见问题与调试技巧实录7.1 传参问题为什么改了形参栈还是空新手写顺序栈时最典型的一个错误是在main里定义了一个SeqStack变量直接调用push(s, 10)结果运行完发现s.data里什么都没有。原因是C语言默认按值传递参数push(SeqStack s, int x)传入的只是结构体的副本函数内部对s的修改不会影响外部的原始变量。正确做法是给函数传结构体指针push(SeqStack* s, int x)函数内部通过箭头操作符访问成员。链表相关函数也同理如果函数内部要修改链表头指针的指向就必须传头指针的地址也就是二级指针。很多人一开始在链式栈和链式队列里碰到这个问题觉得指针好难其实只要记住一句话你想在函数里修改哪个变量就把它地址传进去。7.2 段错误排查三板斧段错误Segmentation Fault是C语言初学阶段躲不开的噩梦栈和队列的代码里尤其常见。我的排查顺序分三步。第一步检查是否有空指针被解引用比如malloc失败后没有判空就直接访问或者出队时队列本来就为空却没做检查。第二步检查是否有野指针比如链式队列出队后没有把rear置NULL或者free之后继续访问节点。第三步检查数组越界顺序栈入栈前没有判满top一路自增超过了MAX_SIZE迟早踩到非法区域。调试工具方面强烈建议在VSCode里配好C语言环境并学会用gdb。不需要花哨的操作在可疑代码行打断点用print打印变量地址和内容基本就能定位九成的问题。不要觉得调试器慢实际生产环境里靠猜定位内存问题时间成本是调试器的十倍以上。7.3 我的调试习惯打印法加小样例加画图我调试数据结构代码的习惯有三个第一在关键操作前后打印关键变量的值比如顺序栈的top、循环队列的front和rear、链式队列的指针地址第二永远先用最小样例测试边界比如空表操作一次、只有一个元素的表反复入队出队第三在纸上画图每次操作后更新图上的节点和指针。有人觉得打印太多输出很烦但调试期多打几行printf真不是坏事。你觉得输出乱可以封装一个printStack或printQueue函数需要时再调用。在数据结构的学习阶段可视化自己的每一步操作比空想“应该没问题”有效得多。等代码稳定后再把调试输出删掉或者用日志开关控制。7.4 常见问题速查表典型问题出现原因解决方法栈顶元素总是旧的入栈时先赋值再移动top导致top状态混乱统一使用data[top] x顺序栈访问越界push前没判满数组被写穿入栈前调用isFull判断链式队列出队后崩溃队列变空时rear未置NULL出队后检查front是否为空空则rear也置空函数修改结构体没生效传的是结构体值不是指针函数参数改成结构体指针内存越用越多链式栈/队列节点没有free出栈出队时保存temp后free程序结束前释放全部节点循环队列判错队满误用rear front判满使用(rear1)%N front或增加size计数这些坑我自己都一个一个踩过。说真的数据结构的学习没有什么捷径多写多错多改错到一定程度你对内存布局和指针的理解就自然上升一个台阶。栈和队列虽然只是入门级结构但只要你认真把所有边界条件都处理干净后面学二叉树、图、哈希表的时候会明显感觉轻松很多。
1. 为什么值得用C语言把栈和队列从零写一遍栈和队列是数据结构里最基础、也最容易被低估的两个结构。很多人C语言学完指针就开始刷算法题却很少愿意老老实实用手写一遍栈和队列。但真正到了面试、做项目、读中间件源码的时候会发现到处是它们的身影函数调用栈、浏览器前进后退、消息队列、阻塞队列、任务调度……这套底层能力还真不是靠背几道题能补上的。这篇文章我想用C语言把栈和队列完整实现一遍从结构体定义到入栈出栈、入队出队再到循环队列的取模边界、链式队列的内存释放每一个细节都会讲到。适合刚学完C语言指针、正在上数据结构课的同学也适合想回头补基础的在职开发。读完以后我希望你能做到不看任何参考代码直接在白纸上写出一个能跑、能释放内存的版本。1.1 栈后进先出离我们最近的底层结构栈是一种只允许在一端进行插入和删除的线性表这一端叫栈顶另一端叫栈底。插入操作叫入栈push删除操作叫出栈pop这种“后进先出”的规则内部元素永远被压在下面。你可以把它想成一摞盘子后放上去的盘子最先被拿走想拿最底下的盘子只能先把上面的全部搬走。别觉得这个规则太简单操作系统里的函数调用栈就是最典型的例子。每调用一个函数CPU会把当前函数的返回地址、局部变量和参数按顺序压入系统栈函数返回时再从栈顶弹出。递归深度过大导致“栈溢出”本质就是压入栈的调用帧太多把系统分配的空间撑爆了。所以栈不是一个只在课本里出现的数据结构它是整个程序运行时的重要底层机制。1.2 队列先进先出系统解耦的顶梁柱队列同样是操作受限的线性表但它限制得更“公平”只能在队尾插入从队首删除。排过队的人都能理解这种场景先来的人先被服务后来的人只能排在队尾。打印机作业队列、键盘缓冲区、消息中间件里的消息队列本质上都是这种先进先出FIFO模型。有意思的是队列在业务系统里的地位比栈还要高。拿消息队列来说它的三个核心作用——解耦、异步、削峰全都建立在这个先进先出的底层结构上。生产端把消息按顺序放进队列消费端按顺序取出处理两端不需要直接依赖彼此。如果只从数据结构层面看消息队列就是一张可以跨进程、跨机器访问的超级队列。底层基础决定上层架构这句话在队列身上体现得淋漓尽致。1.3 手写栈和队列能收获什么有人可能会问C语言标准库里没有数据结构容器写一遍我会用就行了为什么非要手写我的看法是手写一遍不是为了应付考试而是为了搞清楚三个关键问题数据存哪里、指针怎么移动、内存怎么释放。C语言的优势就在于它的内存管理是显式的。你定义一个数组当栈就要自己算清楚top的取值范围你malloc一个新节点就要自己记得在什么时候free。这些操作如果换成Java或Python几乎会被语法屏蔽掉。很多人在高级语言里用得顺手但一旦遇到内存泄漏、段错误、程序崩溃就完全不知道从哪查起根子就在于没在底层图上建立直觉。C语言手写栈和队列就是成本最低的补课方式。2. 顺序栈实战从数组到核心操作的完整实现2.1 栈的结构体设计为什么要用top而不直接操作数组下标顺序栈是用一段连续内存保存元素最简单的方式就是数组加一个栈顶游标。这个游标不是真正的指针而是一个整型下标它用来标记当前栈顶元素在数组中的位置。为什么不直接用指针因为数组加整型下标更容易理解而且后续判空、判满、遍历都更直观对于教学和工程调试都友好。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SeqStack;这里的data是栈的存储区top是栈顶下标。我习惯把top初始化为-1代表空栈。这样设计的好处是栈里有元素时top始终指向当前栈顶元素的位置空栈时top为-1不合法的数组下标一眼就能被识别出来调试时不容易混淆。2.2 初始化、判空、判满先搭好骨架很多人写数据结构代码喜欢把所有逻辑都塞进main函数这是一个很不好的习惯。更合理的做法是先封装好栈的基本状态函数让每个函数只做一件事。初始化、判空、判满看起来简单但它们是后续一切操作的基础。void initStack(SeqStack* s) { s-top -1; } int isEmpty(SeqStack* s) { return s-top -1; } int isFull(SeqStack* s) { return s-top MAX_SIZE - 1; }为什么判满条件是top MAX_SIZE - 1因为数组下标从0开始当top等于99时第100个位置也就是最后一个元素都已经被占用数组确实满了。封装这三个函数以后不管是在push还是在pop里需要判断状态时直接调用就行逻辑清晰也不会因为某个地方直接拿魔数判断而出错。2.3 push和pop的边界处理top移动顺序别搞反入栈和出栈是整个顺序栈的核心也是最容易写错的地方。这里有一个细节必须形成肌肉记忆入栈时要先移动top到下一个位置再写入数据出栈时要先取出当前top位置的元素再让top回退。用一句口诀就是“入栈先加后用出栈先用后减”。void push(SeqStack* s, int x) { if (isFull(s)) { printf(栈已满无法入栈\n); return; } s-data[s-top] x; } int pop(SeqStack* s) { if (isEmpty(s)) { printf(栈为空无法出栈\n); return -1; } return s-data[s-top--]; } int peek(SeqStack* s) { if (isEmpty(s)) { printf(栈为空\n); return -1; } return s-data[s-top]; }入栈使用top出栈使用top--代码很简洁但如果你是新手我建议先写展开版再缩写成这样。因为出错往往就出在先后顺序上如果入栈时先赋值再top第一个元素会被写进data[0]但top还是-1这意味着后面出栈时永远读不到它如果出栈时先top--再取元素就会把当前栈顶下标减到前一个位置取到的是上一个元素的数据。还有个值得一提的点上面代码在栈为空时返回-1作为错误标志。这在元素本身可能为-1的场景下并不严谨更可靠的做法是传入一个结果指针用返回值表示操作是否成功例如int pop(SeqStack* s, int* value)。实际项目中我推荐使用后者教学场景里先理解-1这个错误标记没有太大问题。2.4 顺序栈的局限栈顶指针从-1开始的好处关于top从-1开始还是从0开始网上有过不少争论。从-1开始top指向当前栈顶入栈就是先加后用从0开始top指向下一个可用位置入栈就是先赋值后加。两种写法都能实现栈但我个人强烈推荐从-1开始。原因有三点第一空栈的判断条件top -1非常直观第二取栈顶元素时直接使用data[top]不需要额外减一第三在调试打印时如果看到top是非法值就说明栈状态出了问题。我刚开始学栈的时候曾为了“从0开始更符合数组习惯”而选择从0初始化结果每次取栈顶都容易差一个位置越改越乱。后来统一改成从-1开始整个人神清气爽。顺序栈最大的局限就是容量固定。MAX_SIZE是100就最多放100个元素一旦数据量不可控就会满。解决思路是改用动态扩容的数组或者直接用链式栈。3. 链式栈与动态内存管理让数据量不再受限3.1 链式栈结构一个头指针就够了链式栈的底层是单链表但不需要头结点和尾结点只需要一个栈顶指针也就是链表的头指针。为什么一个指针就够因为栈的所有插入和删除都在栈顶进行而链表的头插和头删正好都是时间复杂度为O(1)的操作。数据量不确定时链式栈能随用随开天然没有容量上限只有内存不够的问题。typedef struct Node { int data; struct Node* next; } StackNode; typedef struct { StackNode* top; } LinkedStack;你可能注意到我在这里把栈顶指针又包装进了一个结构体。这样设计的好处是后续函数参数传递时只需要传一个LinkedStack*而不需要传二级指针去操作头结点。代码里看起来只多了一层结构体但可读性和安全性能提升一个档次。3.2 入栈和出栈的实现头插法加释放链式栈的入栈本质上就是在链表头部插入新节点。新节点的next指向当前栈顶然后让top指向新节点。栈顶永远是最新的节点符合后进先出的逻辑。void pushLinked(LinkedStack* stack, int x) { StackNode* newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败\n); return; } newNode-data x; newNode-next stack-top; stack-top newNode; } int popLinked(LinkedStack* stack, int* value) { if (stack-top NULL) { printf(栈为空\n); return 0; } StackNode* temp stack-top; *value temp-data; stack-top temp-next; free(temp); return 1; }出栈时先用临时指针保存当前栈顶节点取出数据再把栈顶指针移动到下一个节点最后释放原栈顶节点。这里顺序不能乱尤其是不能先free再移动top否则后面就访问到非法内存了。我见过不少新手写链式栈出栈把free放在移动top之前然后程序一跑就段错误原因就是“先杀鸡后取卵”。链式栈还有一个容易被忽略的点程序结束前要遍历整条链表并释放所有节点。因为malloc申请的内存不会随着函数结束自动回收不释放就会造成内存泄漏。在长期运行的服务里哪怕每次泄漏一个小节点积累起来也可能让内存占用持续飙升。3.3 顺序栈还是链式栈一张表说清楚很多人纠结到底是顺序栈好还是链式栈好。这个问题没有标准答案完全看使用场景。我做了个对比方便你根据项目情况选择维度顺序栈链式栈存储方式连续数组非连续节点容量固定可动态扩容动态受内存限制缓存友好性高连续内存访问快低节点分散易缺页额外空间开销几乎没有每个节点多一个next指针扩容复杂度需要搬移数据每次malloc一个节点适用场景数据量稳定、性能敏感数据量波动大、不稳定从实际工程角度讲普通应用里顺序栈更常见因为它内存连续、缓存命中率高而且不需要频繁malloc和free性能更可控。链式栈的意义更多在于理解动态内存管理和为后续链表结构打基础。真到了生产环境很多程序员会直接用现成的动态数组做栈原因也是同理。4. 循环队列解决假溢出问题的标准答案4.1 普通顺序队列的假溢出问题到底出在哪队列如果也用数组实现绕不开一个经典难题假溢出。假设数组大小为5一开始front和rear都指向0。入队三个元素后rear变成3出队两个元素后front变成2。此时数组0号位和1号位其实已经空了但rear已经移动到下标3后面继续入队只能往后走直到rear走到数组末尾5然后明明数组前半部分还有空位却报告“队列已满”。这就是假溢出的本质数组没有被真正填满但rear已经走到了边界前面空出来的位置没法利用。解决思路有两个一是每次出队后把后面的元素全部前移这样能解决问题但时间复杂度是O(n)效率太差二是把数组在逻辑上首尾相连做成循环队列。4.2 循环队列的取模机制与队满判断循环队列的思路是让rear在到达数组末尾后通过取模运算回到数组开头。假设数组长度为N那么rear (rear 1) % Nfront也一样。这样数组在逻辑上就变成了一个环假溢出的空间被重新利用。但这带来了新的问题循环队列里空队列时front和rear相等满队列时front和rear也会相等。同一个条件两种含义怎么区分最常见的做法是牺牲一个存储空间当(rear 1) % N front时认为队列已满。也就是说数组长度为N的循环队列实际最多只能存N-1个元素保证rear永远追不上front。#define QUEUE_SIZE 100 typedef struct { int data[QUEUE_SIZE]; int front; int rear; } CirQueue; void initQueue(CirQueue* q) { q-front 0; q-rear 0; } int isFullQueue(CirQueue* q) { return (q-rear 1) % QUEUE_SIZE q-front; } int isEmptyQueue(CirQueue* q) { return q-rear q-front; }4.3 循环队列核心代码实现入队时先判断队列是否已满然后写入数据再让rear移动到下一个位置。出队时先判断是否为空取出当前front指向的位置再让front移动到下一个位置。两处都用取模运算来实现环形回绕。void enQueue(CirQueue* q, int x) { if (isFullQueue(q)) { printf(队列已满\n); return; } q-data[q-rear] x; q-rear (q-rear 1) % QUEUE_SIZE; } int deQueue(CirQueue* q, int* value) { if (isEmptyQueue(q)) { printf(队列为空\n); return 0; } *value q-data[q-front]; q-front (q-front 1) % QUEUE_SIZE; return 1; }循环队列里有一个常见疑问为什么出队只需要移动front而不需要清空原来的data位置因为队列的可用性只由front和rear之间维护的逻辑区间决定旧数据留在原地没有关系下次入队写入新值时会自然覆盖。如果你在调试时想看队列当前有多少元素可以用这个公式计算长度count (rear - front QUEUE_SIZE) % QUEUE_SIZE这个公式必须加上QUEUE_SIZE再取模因为rear回绕到前面后rear-front可能是负数加一次长度后再取模才能得到正确结果。4.4 队满判断的三种方案对比牺牲一个存储单元并不是唯一区分队空队满的方法我把三种常见方案列在一起方便你根据场合选择方案实现思路优点缺点牺牲一个单元(rear1)%N front判满实现简单判定快浪费一个存储位增加size计数入队size出队size--不浪费空间需要维护额外变量增加tag标记每次操作改变tag不浪费空间逻辑绕容易出错我个人在实际写代码时第一选择永远是牺牲一个单元。原因很简单它最不容易出错。size方案虽然不浪费空间但每次入队和出队都要同步修改size稍不留神就会和实际元素数量不一致。tag方案更是调试地狱判断队空队满还要回看上一次操作是入队还是出队。数据结构代码最好写的是能用最少状态表达最清晰逻辑的方案而不是用更复杂的逻辑去节省一个数组位。5. 链式队列front和rear两个指针的默契配合5.1 链式队列结构设计两个指针各管一头链式队列和链式栈类似底层是一个单链表但队列的插入发生在尾部、删除发生在头部所以单靠一个头指针根本不够用必须同时维护front和rear两个指针。front指向队首节点负责出队rear指向队尾节点负责入队。两个指针各管一端插入和删除都能达到O(1)。typedef struct QNode { int data; struct QNode* next; } QNode; typedef struct { QNode* front; QNode* rear; } LinkedQueue;这里有个细节很多教材会给链式队列加一个头结点让空队列和非空队列的处理逻辑尽量统一。但我建议初学阶段先不要带头结点因为不带头结点的版本虽然代码里多一些判空分支却更容易帮你理解front和rear的语义尤其是“队列变空后两个指针都要更新”这个关键点。5.2 入队出队完整流程与一个隐蔽的坑入队操作相对简单新建节点如果队列为空让front和rear都指向它否则把新节点链到rear后面再让rear指向新节点。出队操作要小心队列为空时报错不为空时保存队首数据移动front并释放原队首节点。void enQueueLinked(LinkedQueue* q, int x) { QNode* newNode (QNode*)malloc(sizeof(QNode)); if (newNode NULL) { printf(内存分配失败\n); return; } newNode-data x; newNode-next NULL; if (q-rear NULL) { q-front newNode; q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } } int deQueueLinked(LinkedQueue* q, int* value) { if (q-front NULL) { printf(队列为空\n); return 0; } QNode* temp q-front; *value temp-data; q-front temp-next; if (q-front NULL) { q-rear NULL; } free(temp); return 1; }链式队列最容易踩的坑就在出队的最后一步当队列只有一个节点时front在q-front temp-next之后会变成NULL此时如果不把rear也置成NULLrear就会变成一个悬挂指针指向已经被释放的节点。下次再调用enQueueLinked时q-rear NULL这个判断会让程序走“空队列”分支吗不会因为rear指向的地址虽然内存已释放但不一定等于NULL。于是代码会执行q-rear-next newNode访问非法内存直接段错误。我当初调这个bug调了一晚上最后打印front和rear的地址才恍然大悟。所以切记链式队列如果长度为1出队后front和rear都必须置NULL。这个条件在标准教材里可能只是短短一句但真正写代码时漏掉的人不在少数。5.3 链式队列和循环队列的实际选型思路链式队列不用固定长度入队基本不会满除非malloc失败循环队列用固定数组队列长度可控性能稳定。实际工程里怎么选如果队列的最大长度可以预估比如打印任务队列、串口缓冲区我会选择循环队列因为不需要频繁malloc和free也没有内存碎片问题。如果队列长度不可控比如消息分发场景消费者速度偶尔跟不上我会选择链式队列让队列有时间缓冲压力。还有一个很现实的场景多线程环境下的阻塞队列。无论是循环队列还是链式队列底层结构经常都要加上锁和条件变量才能变成线程安全的阻塞队列。很多框架里实现的ArrayBlockingQueue底层就是循环队列LinkedBlockingQueue底层则是链式队列。所以你现在把循环队列和链式队列都吃透了以后看Java并发包或者其他框架源码都会顺手很多。6. 栈和队列在真实项目里的典型应用6.1 栈的经典应用函数调用、括号匹配、表达式求值栈最常见的应用在函数调用机制里。程序运行时系统栈保存着每一层函数调用的返回地址和局部变量。写递归函数时每一层递归就相当于一次入栈递归出口就是出栈。理解了这一点你就能明白为什么递归栈溢出的报错叫“Stack Overflow”也能明白为什么把递归改成循环时往往需要自己显式定义一个栈来模拟系统栈。括号匹配是另一个经典场景也非常容易手写。遍历字符串遇到左括号就入栈遇到右括号就看看栈顶是不是对应的左括号匹配则出栈不匹配则失败。最后检查栈是否为空如果还有左括号残留说明有多余左括号。这个算法看起来简单但在编译器、代码编辑器的语法检查里和它类似的思路每天都在被用到。表达式求值也离不开栈。中缀表达式转后缀表达式需要一个符号栈后缀表达式求值需要一个操作数栈。很多学生第一次接触这里时觉得抽象但用笔在纸上按步骤推一遍马上就能明白为什么操作符能通过栈来调整优先级。这也是为什么很多面试官喜欢拿表达式求值考候选人因为它能同时考察栈的理解和边界思维。6.2 队列的经典应用消息队列、阻塞队列、任务调度队列在真实项目里的出场频率可能比栈更高。最典型的是消息队列生产者和消费者之间通过队列解耦生产端不用关心谁在处理消费端也不用关心数据从哪来。你可以把它理解成一个巨大的仓库上游只管往仓库货架上放货下游按自己的节奏取货仓库本身通过队列结构保证了先进先出的公平顺序。阻塞队列则是并发编程中的明星。当队列为空消费者线程会自动进入等待状态直到生产者写入数据后唤醒它当队列满了生产者线程会被阻塞直到消费者取走数据。这种机制很好地平衡了生产速度和消费速度避免双方互相拖垮。热词里常提到的延迟队列底层也还是队列思路只不过出队时会检查元素的延迟时间是否已到本质上是在队列节点里增加了“可执行时间”字段。6.3 从数据结构看后端技术栈为什么底层基础决定上层架构很多做开发的朋友不止一次听过“全栈工程师”这个词也有人为了一张技术栈清单东拼西凑。但真正的全栈不是会几个框架就行的而是能理解每一层是怎么组合起来的。就拿前后端、中间件这一路说下来消息队列是队列调用链追踪是栈网络数据包缓冲区也是队列甚至连递归遍历目录都要用栈或者队列来手动模拟。这也是我极力推荐你用C语言手写一遍栈和队列的原因。你亲手管理过内存你踩过悬挂指针的坑你看过数组溢出后的诡异表现以后用任何高级语言和框架再遇到类似问题底层的直觉马上能告诉你问题大概出在哪。数据结构不是拿来背的是拿来理解世界的。7. 新手常见问题与调试技巧实录7.1 传参问题为什么改了形参栈还是空新手写顺序栈时最典型的一个错误是在main里定义了一个SeqStack变量直接调用push(s, 10)结果运行完发现s.data里什么都没有。原因是C语言默认按值传递参数push(SeqStack s, int x)传入的只是结构体的副本函数内部对s的修改不会影响外部的原始变量。正确做法是给函数传结构体指针push(SeqStack* s, int x)函数内部通过箭头操作符访问成员。链表相关函数也同理如果函数内部要修改链表头指针的指向就必须传头指针的地址也就是二级指针。很多人一开始在链式栈和链式队列里碰到这个问题觉得指针好难其实只要记住一句话你想在函数里修改哪个变量就把它地址传进去。7.2 段错误排查三板斧段错误Segmentation Fault是C语言初学阶段躲不开的噩梦栈和队列的代码里尤其常见。我的排查顺序分三步。第一步检查是否有空指针被解引用比如malloc失败后没有判空就直接访问或者出队时队列本来就为空却没做检查。第二步检查是否有野指针比如链式队列出队后没有把rear置NULL或者free之后继续访问节点。第三步检查数组越界顺序栈入栈前没有判满top一路自增超过了MAX_SIZE迟早踩到非法区域。调试工具方面强烈建议在VSCode里配好C语言环境并学会用gdb。不需要花哨的操作在可疑代码行打断点用print打印变量地址和内容基本就能定位九成的问题。不要觉得调试器慢实际生产环境里靠猜定位内存问题时间成本是调试器的十倍以上。7.3 我的调试习惯打印法加小样例加画图我调试数据结构代码的习惯有三个第一在关键操作前后打印关键变量的值比如顺序栈的top、循环队列的front和rear、链式队列的指针地址第二永远先用最小样例测试边界比如空表操作一次、只有一个元素的表反复入队出队第三在纸上画图每次操作后更新图上的节点和指针。有人觉得打印太多输出很烦但调试期多打几行printf真不是坏事。你觉得输出乱可以封装一个printStack或printQueue函数需要时再调用。在数据结构的学习阶段可视化自己的每一步操作比空想“应该没问题”有效得多。等代码稳定后再把调试输出删掉或者用日志开关控制。7.4 常见问题速查表典型问题出现原因解决方法栈顶元素总是旧的入栈时先赋值再移动top导致top状态混乱统一使用data[top] x顺序栈访问越界push前没判满数组被写穿入栈前调用isFull判断链式队列出队后崩溃队列变空时rear未置NULL出队后检查front是否为空空则rear也置空函数修改结构体没生效传的是结构体值不是指针函数参数改成结构体指针内存越用越多链式栈/队列节点没有free出栈出队时保存temp后free程序结束前释放全部节点循环队列判错队满误用rear front判满使用(rear1)%N front或增加size计数这些坑我自己都一个一个踩过。说真的数据结构的学习没有什么捷径多写多错多改错到一定程度你对内存布局和指针的理解就自然上升一个台阶。栈和队列虽然只是入门级结构但只要你认真把所有边界条件都处理干净后面学二叉树、图、哈希表的时候会明显感觉轻松很多。
