写代码这么多年我有个习惯新接触一门语言第一件事不是去背语法而是先把栈和队列写一遍。尤其是C语言没有那些现成的容器可以用一切都要自己动手造轮子。C语言栈和队列的实现看起来是数据结构入门课里最基础的两块内容但你真的动手去写了之后才会发现top指针的指向、环形队列的取模、空队列的边界每一个细节都能让你栽跟头。这篇文章就围绕这两个结构展开从顺序存储到链式存储从代码实现到测试思路把我在实际写代码过程中踩过的坑和积累的经验一并分享出来。适合正在学数据结构的初学者、准备面试的开发者以及想夯实C语言功底的朋友参考。1. 动手之前先想清楚栈和队列到底模拟了什么逻辑很多人在学栈和队列的时候第一反应是背定义栈是后进先出队列是先进先出。定义背得滚瓜烂熟但一写代码就卡住。我觉得问题不在于不会写代码而在于没有理解这两个结构在真实世界中到底对应了什么场景。我习惯用生活中的例子来建立直觉然后再把这个直觉映射到代码上。1.1 栈一摞盘子最后放上去的先用栈的逻辑最贴切的类比就是一摞盘子。餐厅后厨里洗好的盘子一个一个叠上去取用的时候一定是从最上面拿。最后放上去的盘子永远最先被拿走。这就是后进先出LIFOLast In First Out。你在编辑器里按CtrlZ撤销操作用的就是栈。每做一步操作系统就把这个操作压入栈撤销的时候从栈顶弹出最近一次的操作。浏览器里的后退按钮也一样你访问的每个页面都被压进一个栈点后退就是弹出栈顶页面。函数调用更是典型的栈应用A函数调用B函数B调用CC返回之后才轮到B继续执行最后回到A这种嵌套返回的顺序天然就是后进先出。写代码实现栈的时候脑子里想的是一摞盘子这个画面你就会很自然地明白入栈push就是往盘子堆上放一个新盘子出栈pop就是从盘子堆顶部拿走一个盘子栈顶top就是那摞盘子最上面的位置。数据结构里的抽象落到代码里其实就是数组或者链表上的几个操作。1.2 队列排队打饭先来的先吃队列的直觉更简单就是排队。食堂打饭排在前面的人先打到饭后来的人只能排在队尾。这就是先进先出FIFOFirst In First Out。打印机任务队列、操作系统的进程调度、网络数据包的收发缓冲本质上都是队列。近些年很火的消息队列比如Kafka、RabbitMQ、RocketMQ这些中间件底层的核心思想也是队列生产者把消息放进队列消费者从队列里取消息先生产的消息先被消费。只不过它们把队列这个数据结构做成了分布式系统增加了持久化、分区分片、消费组这些企业级能力但FIFO这个最基本的模型没有变。写代码的时候脑子里想的是排队打饭这个画面入队enqueue就是新来的同学站到队伍末尾出队dequeue就是队伍最前面的同学打好饭离开队头front就是队伍最前面那个人队尾rear就是队伍最后面那个人。1.3 为什么C语言必须亲手写一遍有人会问Python里有list和collections.dequeJava里有Stack和ArrayDequeC里有std::stack和std::queue为什么还要用C语言手写一遍我的看法是正因为在C语言里没有现成的容器你才被迫把存储结构、指针操作、内存分配、边界条件这些问题全部暴露出来。用Python写一个栈可能三五行代码就完了用C语言写你得自己定义结构体、手动malloc内存、检查栈满栈空、处理free的时机。这个过程是痛苦的但对理解数据结构的本质帮助极大。另外面试也是一个现实因素。很多公司的手写代码环节特别喜欢考栈和队列尤其是队列的变体题目出现频率很高。如果只停留在知道原理的程度面试现场根本写不出无bug的代码。亲手实现过一遍并且在纸上能流畅地默写出来这才是真正掌握了。2. 顺序栈数组加一根top指针函数调用的核心模型顺序栈就是用数组来模拟栈的行为。这个实现比较直观但有一个关键点很多人都没想透top指针到底应该指向什么位置。这个选择直接决定了你的入栈出栈代码长什么样。2.1 top指针的两个流派从-1开始还是从0开始网上关于top指针的说法有两种。一种是top -1表示空栈入栈时先top再赋值另一种是top 0表示空栈入栈时先赋值再top。这两种写法都能实现对但初学者如果没搞清楚就混着写很容易出现第一个元素不知道存到哪里的问题。我推荐使用top -1这个流派理由很简单它让栈顶位置和栈内元素个数这两个概念在代码里非常自然。当top -1时说明没有任何元素当栈里有3个元素时top 2刚好是数组最后一个有效元素的下标。入栈操作等价于先把top往上挪一格再把元素放到这个新位置出栈操作等价于取出当前位置的元素再把top往下挪一格。整个过程和一摞盘子的直觉完全对应。来看一下结构体的定义#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶元素的下标空栈时为-1 } SqStack;2.2 核心操作的完整实现顺序栈需要实现的操作主要有五个初始化、判空、判满、入栈、出栈另外还需要一个取栈顶元素的函数。下面是完整实现代码没有做什么花哨的封装方便你直接照着理解#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SqStack; // 1. 初始化 void initStack(SqStack* s) { s-top -1; } // 2. 判空 bool isEmpty(SqStack* s) { return s-top -1; } // 3. 判满 bool isFull(SqStack* s) { return s-top MAX_SIZE - 1; } // 4. 入栈 bool push(SqStack* s, int value) { if (isFull(s)) { printf(栈已满无法入栈 %d\n, value); return false; } s-data[(s-top)] value; return true; } // 5. 出栈 bool pop(SqStack* s, int* value) { if (isEmpty(s)) { printf(栈为空无法出栈\n); return false; } *value s-data[(s-top)--]; return true; } // 6. 取栈顶元素不弹出 bool peek(SqStack* s, int* value) { if (isEmpty(s)) { printf(栈为空无栈顶元素\n); return false; } *value s-data[s-top]; return true; }注意出栈函数的写法先取出当前栈顶元素再进行top--。如果你写反了先减再取取到的就是上一个元素这是一个很隐蔽的错误我见过不止一个初学者在这里翻车。2.3 顺序栈最容易翻车的三个边界写顺序栈的时候有三个地方最容易出问题。第一个是入栈前的满检查。数组大小是MAX_SIZE栈满时top MAX_SIZE - 1。如果不做这个检查继续入栈就会越界写C语言不会提醒你但可能悄悄改坏相邻内存的数据。数据被改坏还不是最可怕的更麻烦的是这种错误往往不会立刻暴露而是运行很久之后才出现莫名其妙的结果排错的时候让人抓狂。第二个是出栈前的空检查。空栈时top -1此时如果还去访问data[top]访问的是数组下标为-1的内存这是未定义行为。在实际运行中可能不会立刻崩溃但结果完全不可控。第三个是运算符的优先级问题。s-data[(s-top)]这里我加了一对括号目的是明确先自增再取下标。虽然的优先级高于[]但不同编译器在复杂表达式下的行为可能会让人犯迷糊。我的习惯是涉及指针或下标自增自减时尽量用括号把运算顺序写明白避免靠优先级猜。这种好习惯能帮你少调试很多莫名其妙的bug。3. 链栈没有容量上限的栈头插法立刻出结果顺序栈有一个硬伤容量写死了。你用MAX_SIZE 100就只能存100个元素。如果想动态扩容还得写realloc之类的逻辑。链栈解决了这个问题理论上只要内存够链栈可以不停入栈不存在栈满的概念。3.1 为什么入栈要改造成头插链栈的核心思路是用链表节点存储元素让链表头结点成为栈顶。这样入栈操作等价于在链表头部插入一个新节点出栈操作等价于删除链表头结点。你可能会有疑问为什么不用尾插法因为如果使用尾插你还需要额外维护一个尾指针每次入栈都得通过尾指针插入出栈又得找到倒数第二个节点复杂度变高了。而头插法天然就匹配栈的操作特性最新的节点永远在最前面取栈顶只需要看头结点时间复杂度是O(1)。为了验证头插法确实能让栈操作更高效我对比一下尾插法出栈时如果是单链表你只能从头遍历到倒数第二个节点时间复杂度O(n)而头插法出栈直接操作头结点即可时间复杂度O(1)。这个差距在元素很多时非常明显。入栈同理。所以链栈设计成头部即栈顶是数据结构里的一个典型权衡。3.2 链栈实现与动态内存管理链栈的节点定义和单链表节点一样每个节点包含一个数据域和一个指针域typedef struct StackNode { int data; struct StackNode* next; } StackNode; typedef struct { StackNode* top; // 栈顶指针 int size; } LinkStack;这里我额外维护了一个size字段用来记录栈内元素个数。有了它取栈长度的操作就变成O(1)而不是O(n)。完整实现如下#include stdio.h #include stdlib.h #include stdbool.h typedef struct StackNode { int data; struct StackNode* next; } StackNode; typedef struct { StackNode* top; int size; } LinkStack; void initLinkStack(LinkStack* s) { s-top NULL; s-size 0; } bool isLinkStackEmpty(LinkStack* s) { return s-top NULL; } // 入栈头插法 bool linkStackPush(LinkStack* s, int value) { StackNode* node (StackNode*)malloc(sizeof(StackNode)); if (node NULL) { printf(内存分配失败\n); return false; } node-data value; node-next s-top; s-top node; s-size; return true; } // 出栈删除头结点 bool linkStackPop(LinkStack* s, int* value) { if (isLinkStackEmpty(s)) { printf(栈为空无法出栈\n); return false; } StackNode* temp s-top; *value temp-data; s-top temp-next; free(temp); s-size--; return true; } // 取栈顶 bool linkStackPeek(LinkStack* s, int* value) { if (isLinkStackEmpty(s)) { printf(栈为空\n); return false; } *value s-top-data; return true; } // 释放整个栈 void destroyLinkStack(LinkStack* s) { StackNode* cur s-top; while (cur ! NULL) { StackNode* temp cur; cur cur-next; free(temp); } s-top NULL; s-size 0; }这段代码里有一个特别需要注意的地方出栈时一定要先把temp节点的next保存下来或者先让top指向后一个节点再free。有些初学者会写这样的代码free(s-top); s-top s-top-next; // 错误s-top已经被释放了这里一旦执行free(s-top)该内存块就已经被系统回收了再去访问-next是未定义行为。正确顺序是先取值、再改指针、最后释放节点。关于内存管理还有一个容易被忽略的问题在销毁整个栈时也要一个一个节点地free不能只把top置为NULL。否则会造成内存泄漏。程序跑的时间短可能察觉不到但如果是长期运行的服务程序或嵌入式环境内存泄漏是个很严重的问题。3.3 链栈和顺序栈怎么选很多初学者会问那以后写栈到底用哪种我的建议是根据场景来对比项顺序栈链栈容量固定满了要扩容动态受限于内存内存分配一次性连续分配每次入栈单独分配访问速度快缓存友好稍慢涉及指针跳转和内存分配开销栈满判断需要不需要使用场景容量可预估、要求高性能容量不可预估、频繁创建销毁栈在实际项目中如果栈的最大深度是明确的顺序栈通常更合适因为数组在内存中是连续存储的CPU缓存命中率高性能更好。如果栈的深度完全不可预估链栈更合适至少不用担心栈满。这只是经验之谈具体情况还得看实际应用场景。4. 环形队列把你从假溢出里解救出来的写法队列的顺序存储比栈复杂一点。如果你直接用数组做一个普通队列很快就会发现一个尴尬的问题明明数组前面还有很多空位置但rear指针已经走到末尾了新元素入不进来。这就是经典的假溢出问题。4.1 线性队列的假溢出陷阱先用代码模拟一下线性队列的行为。假设队列容量为5一开始入队三个元素A、B、C。此时front 0指向Arear 3指向下一个空闲位置。然后连续出队三次队列里的A、B、C都走了front 3rear 3。虽然队列为空但数组的前面几个位置已经被浪费了。现在想入队一个新元素D按线性队列的逻辑应该放在data[rear]这个位置也就是data[3]。入队成功后rear 4。再入队Erear 5。此时rear已经等于容量MAX_SIZE程序会认为队列满了无法再入队。可是从数组内存来看data[0]、data[1]、data[2]这三个位置明明是空的。这就是假溢出数组空间没有真的用完但因为rear到了末尾队列却无法继续使用了。解决办法就是环形队列——把数组在逻辑上首尾相连当rear到达末尾时让它重新回到数组开头继续使用。4.2 环形队列如何用取模完成循环环形队列的实现并不复杂核心就一个操作取模。入队时rear (rear 1) % MAX_SIZE出队时front (front 1) % MAX_SIZE。这个取模运算把数组在逻辑上变成了一个环。打个比方环形队列就像一个圆形的转盘指针沿着转盘循环移动。转盘上有N个格子指针走到第N-1个格子后下一步就走回第0个格子。这个回绕操作在计算机里就是一次取模。结构体定义如下#define QUEUE_SIZE 5 typedef struct { int data[QUEUE_SIZE]; int front; // 指向队头元素 int rear; // 指向队尾的下一个空闲位置 } CircularQueue;这里有一个重要的设计约定front指向当前队头元素的位置rear指向下一个将要放入元素的位置。两个指针最初都指向下标0。4.3 判空判满的三种主流方案环形队列最经典的问题是怎么判断空和满。方案一牺牲一个存储单元。约定(rear 1) % MAX_SIZE front时队列为满。也就是始终浪费一个位置不用用于区分空和满。这种方法最简单常用缺点是要少存一个元素。方案二设置一个计数器。维护一个size变量入队加一出队减一size 0为空size MAX_SIZE为满。这种方法性能略差一点每次入队出队都要更新计数但逻辑直观不会浪费存储空间。方案三设置一个标志位。维护一个布尔变量flag入队时置true出队时置false然后靠front rear flag判断队列状态。我个人在写代码时最常用方案一因为它不需要额外维护变量而且在绝大多数场景下少存一个元素的影响微乎其微。下面我主要基于方案一来写代码。4.4 环形队列完整实现与测试环形队列的完整代码如下#include stdio.h #include stdbool.h #define QUEUE_SIZE 5 typedef struct { int data[QUEUE_SIZE]; int front; int rear; } CircularQueue; void initQueue(CircularQueue* q) { q-front 0; q-rear 0; } bool isQueueEmpty(CircularQueue* q) { return q-front q-rear; } bool isQueueFull(CircularQueue* q) { return (q-rear 1) % QUEUE_SIZE q-front; } bool enQueue(CircularQueue* q, int value) { if (isQueueFull(q)) { printf(队列已满无法入队 %d\n, value); return false; } q-data[q-rear] value; q-rear (q-rear 1) % QUEUE_SIZE; return true; } bool deQueue(CircularQueue* q, int* value) { if (isQueueEmpty(q)) { printf(队列为空无法出队\n); return false; } *value q-data[q-front]; q-front (q-front 1) % QUEUE_SIZE; return true; } int queueSize(CircularQueue* q) { return (q-rear - q-front QUEUE_SIZE) % QUEUE_SIZE; }这里有个很值得说道的小细节queueSize函数的写法。因为rear可能已经绕回前面了直接用rear - front可能得到负数。所以需要先加上QUEUE_SIZE再取模才能得到正确的元素个数。比如rear 1front 3实际有(1 - 3 5) % 5 3个元素这个结果是正确的。测试的时候我建议你专门写一个测试函数把边界情况都跑一遍。以QUEUE_SIZE 5为例空队列出队应该返回false。连续入队4个元素0、1、2、3此时第5个位置因为判满方案被占住了再入队第5个应该失败。出队一个元素后再入队一个元素此时应该成功而且新元素会出现在数组开头附近的位置。不断交替入队出队确保代码在绕圈的时候不会出错。实际操作下来环形队列的代码本身不算难但容易出现忘记取模的错误。比如入队后直接写q-rear只在初始化或者某些特殊情况下才凑巧正确等队列真的绕回起点的时候就会数组越界。5. 链式队列front和rear双指针缺一个效率就塌方链式队列是又一个用链表实现的队列。它和链栈不同链栈用头插法很合适但队列是先进先出必须从两端操作入队发生在队尾出队发生在队头。这就引出一个问题需要几个指针才够用5.1 为什么必须同时保留队头和队尾如果只有一个头指针指向队头节点出队时直接删除头结点就行这个容易。但入队就要从队头开始遍历整个链表一直走到最后一个节点再在末尾插入新节点。这个操作的时间复杂度是O(n)。如果你频繁入队队列长度又比较大这个性能开销是没法接受的。解决方案就是再加一个尾指针始终指向链表的最后一个节点。这样入队操作就变成tail-next指向新节点然后更新tail时间复杂度降为O(1)。代价是结构体多了一个指针字段以及你需要在每次入队出队时小心维护这个尾指针的状态。这个结构还有一个名字叫链队列在操作系统任务队列、异步任务调度等场景中非常常见。它相比环形队列最大的优势是容量动态可扩展不会突然满了。结构体定义如下typedef struct QueueNode { int data; struct QueueNode* next; } QueueNode; typedef struct { QueueNode* front; // 队头指针 QueueNode* rear; // 队尾指针 int size; } LinkQueue;5.2 入队出队完整实现与空队列边界处理链式队列的入队和出队操作代码如下#include stdio.h #include stdlib.h #include stdbool.h typedef struct QueueNode { int data; struct QueueNode* next; } QueueNode; typedef struct { QueueNode* front; QueueNode* rear; int size; } LinkQueue; void initLinkQueue(LinkQueue* q) { q-front NULL; q-rear NULL; q-size 0; } bool isLinkQueueEmpty(LinkQueue* q) { return q-front NULL; } // 入队在rear后面插入 bool linkQueueEn(LinkQueue* q, int value) { QueueNode* node (QueueNode*)malloc(sizeof(QueueNode)); if (node NULL) { printf(内存分配失败\n); return false; } node-data value; node-next NULL; if (q-rear NULL) { q-front node; q-rear node; } else { q-rear-next node; q-rear node; } q-size; return true; } // 出队从front删除 bool linkQueueDe(LinkQueue* q, int* value) { if (isLinkQueueEmpty(q)) { printf(队列为空无法出队\n); return false; } QueueNode* temp q-front; *value temp-data; q-front temp-next; free(temp); q-size--; if (q-front NULL) { q-rear NULL; } return true; } // 释放整个队列 void destroyLinkQueue(LinkQueue* q) { QueueNode* cur q-front; while (cur ! NULL) { QueueNode* temp cur; cur cur-next; free(temp); } q-front NULL; q-rear NULL; q-size 0; }这个代码里最关键的一点在出队操作的最后如果删除了队头节点后队列为空front变成了NULL此时必须同步把rear也置为NULL。如果不这么做会怎样想象一下队列里只有一个节点出队后front和rear都指向这个已经被free的节点。此时rear变成了一个悬空指针。如果再调用入队函数它会判断q-rear NULL发现不为空因为还指向残留地址于是执行q-rear-next node写入一个已释放的内存地址结果完全不可控。这个问题非常隐蔽我在调试时遇到过好几次最终都是在加了if (q-front NULL) q-rear NULL;之后才解决。另外我在这个实现里维护了一个size字段。其实队列的size不比栈通过front到rear不好算因为rear不记录位置所以想快速获取长度就必须额外维护一个计数器。5.3 链式队列与环形队列的取舍链式队列和环形队列哪个更好它们没有绝对优劣关键看使用场景。链式队列的优点很明显容量动态最多受内存限制插入和删除都是O(1)。缺点也很实在每次入队都要malloc频繁分配释放内存会带来开销和时间损耗。环形队列的优点则相反内存是提前分配好的连续空间不存在malloc开销CPU缓存友好性能更好。缺点就是容量固定。我的选择习惯是嵌入式开发、网络驱动这类对性能敏感且容量可预估的场景用环形队列上层业务逻辑里容量不确定、经常需要动态创建队列的场景用链式队列。6. 从实现到应用两个经典问题检验你是否真的懂了写完了四种结构光会实现还不算完。我始终觉得判断一个数据结构是不是真掌握要看你能不能用它解决实际问题。下面这两个经典题目栈和队列的底层能力会被体现得比较充分。6.1 括号匹配用栈做一次性语法检查这个题目在各种教材里出现频率极高给定一个只包含()[]{}的字符串判断括号是否成对匹配。思路就是用栈遍历字符串遇到左括号就入栈遇到右括号时弹出栈顶元素检查是否匹配。如果栈为空或者不匹配直接返回false。遍历结束之后如果栈不为空说明还有左括号没配对上也返回false。这里有一个栈的变体入栈的其实不一定是左括号本身也可以是对应的右括号。这样遇到右括号时就只需要比较是否和栈顶相等少写一个匹配函数。代码如下#include stdio.h #include stdbool.h #include string.h #define MAX_SIZE 100 typedef struct { char data[MAX_SIZE]; int top; } CharStack; void initCharStack(CharStack* s) { s-top -1; } bool charStackPush(CharStack* s, char c) { if (s-top MAX_SIZE - 1) return false; s-data[(s-top)] c; return true; } bool charStackPop(CharStack* s, char* c) { if (s-top -1) return false; *c s-data[(s-top)--]; return true; } bool isMatching(char* str) { CharStack stack; initCharStack(stack); for (int i 0; i strlen(str); i) { char ch str[i]; if (ch ( || ch [ || ch {) { // 入栈对应的右括号 char pushChar; if (ch () pushChar ); else if (ch [) pushChar ]; else pushChar }; if (!charStackPush(stack, pushChar)) { return false; } } else if (ch ) || ch ] || ch }) { char topChar; if (!charStackPop(stack, topChar)) { return false; // 栈为空右括号多了 } if (topChar ! ch) { return false; // 不匹配比如 ( 对上了 ] } } } return stack.top -1; // 所有左括号都被配对 }这段代码里入栈的是对应的右括号所以匹配时的比较变成了简单的字符相等判断。测试用例值得多跑几个()[]{}应该通过([)]应该失败((()))应该通过(()应该失败因为栈最后还有残留。6.2 用两个栈模拟队列面试经典变形题这是一个非常经典的面试题使用两个栈实现一个队列支持入队和出队操作。思路是栈A专门用来入队栈B专门用来出队。入队时直接push到栈A。出队时如果栈B不为空直接从栈B pop如果栈B为空就把栈A的所有元素依次pop并push到栈B中然后再从栈B pop。为什么这样能实现FIFO因为栈的LIFO特性可以反转元素顺序。第一次把元素压入栈A时顺序是正着的把栈A的元素倒到栈B后顺序就反了栈B栈顶元素恰好是最先进入栈A的元素。每次出队都从栈B取栈顶就相当于取了最早入队的元素。这段逻辑用上一节的顺序栈改一改就能跑通#include stdio.h #include stdbool.h // 这里直接复用之前实现的SqStack假设已有push、pop、isEmpty等函数 typedef struct { SqStack s1; // 入队栈 SqStack s2; // 出队栈 } QueueWithTwoStacks; void initQueueWithTwoStacks(QueueWithTwoStacks* q) { initStack((q-s1)); initStack((q-s2)); } bool pushToQueue(QueueWithTwoStacks* q, int value) { return push((q-s1), value); } bool popFromQueue(QueueWithTwoStacks* q, int* value) { if (isEmpty((q-s2))) { // s2为空先把s1全部倒过来 while (!isEmpty((q-s1))) { int temp; pop((q-s1), temp); push((q-s2), temp); } } if (isEmpty((q-s2))) { return false; // 两个栈都是空的队列为空 } return pop((q-s2), value); }这个设计的复杂度是均摊O(1)。每个元素最多经历一次入s1、一次倒到s2、一次出s2都是常数次操作。这个知识点面试时经常被追问建议你把这段逻辑彻底想透。还有一个类似的变形题是用两个队列模拟栈思路稍有区别入栈时往非空队列里入队出栈时把非空队列的前n-1个元素出队并入队到空队列最后一个元素就是栈顶直接出队。核心逻辑就是把队列前面的元素挪开让最后一个露出来。有了前面的基础实现起来应该不难。结尾在实际敲代码的过程中我比较深的体会是学栈和队列最怕的就是看着会了一写就废。数据结构这门课没有捷径只有基于代码实现加上足够的边界测试才算真正掌握。建议你可以把本文的四种结构都默写一遍然后准备一组边界测试用例——空栈出栈、栈满入栈、空队出队、环形队列满入队、链式队列删到空再入队——把这些情况都跑一遍哪里出问题就说明哪里还有理解漏洞。最后再分享一个小技巧如果你在编译器上调试环形队列的取模逻辑可以在入队出队操作里临时打印front和rear的值盯着它们观察是否真的在绕着0到MAX_SIZE-1循环。很多取模错误肉眼就能看出来不用闷头苦想。把这四种实现和两个经典应用吃透之后后面的二叉树、图、递归这些内容学起来会轻松不少。
写代码这么多年我有个习惯新接触一门语言第一件事不是去背语法而是先把栈和队列写一遍。尤其是C语言没有那些现成的容器可以用一切都要自己动手造轮子。C语言栈和队列的实现看起来是数据结构入门课里最基础的两块内容但你真的动手去写了之后才会发现top指针的指向、环形队列的取模、空队列的边界每一个细节都能让你栽跟头。这篇文章就围绕这两个结构展开从顺序存储到链式存储从代码实现到测试思路把我在实际写代码过程中踩过的坑和积累的经验一并分享出来。适合正在学数据结构的初学者、准备面试的开发者以及想夯实C语言功底的朋友参考。1. 动手之前先想清楚栈和队列到底模拟了什么逻辑很多人在学栈和队列的时候第一反应是背定义栈是后进先出队列是先进先出。定义背得滚瓜烂熟但一写代码就卡住。我觉得问题不在于不会写代码而在于没有理解这两个结构在真实世界中到底对应了什么场景。我习惯用生活中的例子来建立直觉然后再把这个直觉映射到代码上。1.1 栈一摞盘子最后放上去的先用栈的逻辑最贴切的类比就是一摞盘子。餐厅后厨里洗好的盘子一个一个叠上去取用的时候一定是从最上面拿。最后放上去的盘子永远最先被拿走。这就是后进先出LIFOLast In First Out。你在编辑器里按CtrlZ撤销操作用的就是栈。每做一步操作系统就把这个操作压入栈撤销的时候从栈顶弹出最近一次的操作。浏览器里的后退按钮也一样你访问的每个页面都被压进一个栈点后退就是弹出栈顶页面。函数调用更是典型的栈应用A函数调用B函数B调用CC返回之后才轮到B继续执行最后回到A这种嵌套返回的顺序天然就是后进先出。写代码实现栈的时候脑子里想的是一摞盘子这个画面你就会很自然地明白入栈push就是往盘子堆上放一个新盘子出栈pop就是从盘子堆顶部拿走一个盘子栈顶top就是那摞盘子最上面的位置。数据结构里的抽象落到代码里其实就是数组或者链表上的几个操作。1.2 队列排队打饭先来的先吃队列的直觉更简单就是排队。食堂打饭排在前面的人先打到饭后来的人只能排在队尾。这就是先进先出FIFOFirst In First Out。打印机任务队列、操作系统的进程调度、网络数据包的收发缓冲本质上都是队列。近些年很火的消息队列比如Kafka、RabbitMQ、RocketMQ这些中间件底层的核心思想也是队列生产者把消息放进队列消费者从队列里取消息先生产的消息先被消费。只不过它们把队列这个数据结构做成了分布式系统增加了持久化、分区分片、消费组这些企业级能力但FIFO这个最基本的模型没有变。写代码的时候脑子里想的是排队打饭这个画面入队enqueue就是新来的同学站到队伍末尾出队dequeue就是队伍最前面的同学打好饭离开队头front就是队伍最前面那个人队尾rear就是队伍最后面那个人。1.3 为什么C语言必须亲手写一遍有人会问Python里有list和collections.dequeJava里有Stack和ArrayDequeC里有std::stack和std::queue为什么还要用C语言手写一遍我的看法是正因为在C语言里没有现成的容器你才被迫把存储结构、指针操作、内存分配、边界条件这些问题全部暴露出来。用Python写一个栈可能三五行代码就完了用C语言写你得自己定义结构体、手动malloc内存、检查栈满栈空、处理free的时机。这个过程是痛苦的但对理解数据结构的本质帮助极大。另外面试也是一个现实因素。很多公司的手写代码环节特别喜欢考栈和队列尤其是队列的变体题目出现频率很高。如果只停留在知道原理的程度面试现场根本写不出无bug的代码。亲手实现过一遍并且在纸上能流畅地默写出来这才是真正掌握了。2. 顺序栈数组加一根top指针函数调用的核心模型顺序栈就是用数组来模拟栈的行为。这个实现比较直观但有一个关键点很多人都没想透top指针到底应该指向什么位置。这个选择直接决定了你的入栈出栈代码长什么样。2.1 top指针的两个流派从-1开始还是从0开始网上关于top指针的说法有两种。一种是top -1表示空栈入栈时先top再赋值另一种是top 0表示空栈入栈时先赋值再top。这两种写法都能实现对但初学者如果没搞清楚就混着写很容易出现第一个元素不知道存到哪里的问题。我推荐使用top -1这个流派理由很简单它让栈顶位置和栈内元素个数这两个概念在代码里非常自然。当top -1时说明没有任何元素当栈里有3个元素时top 2刚好是数组最后一个有效元素的下标。入栈操作等价于先把top往上挪一格再把元素放到这个新位置出栈操作等价于取出当前位置的元素再把top往下挪一格。整个过程和一摞盘子的直觉完全对应。来看一下结构体的定义#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶元素的下标空栈时为-1 } SqStack;2.2 核心操作的完整实现顺序栈需要实现的操作主要有五个初始化、判空、判满、入栈、出栈另外还需要一个取栈顶元素的函数。下面是完整实现代码没有做什么花哨的封装方便你直接照着理解#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SqStack; // 1. 初始化 void initStack(SqStack* s) { s-top -1; } // 2. 判空 bool isEmpty(SqStack* s) { return s-top -1; } // 3. 判满 bool isFull(SqStack* s) { return s-top MAX_SIZE - 1; } // 4. 入栈 bool push(SqStack* s, int value) { if (isFull(s)) { printf(栈已满无法入栈 %d\n, value); return false; } s-data[(s-top)] value; return true; } // 5. 出栈 bool pop(SqStack* s, int* value) { if (isEmpty(s)) { printf(栈为空无法出栈\n); return false; } *value s-data[(s-top)--]; return true; } // 6. 取栈顶元素不弹出 bool peek(SqStack* s, int* value) { if (isEmpty(s)) { printf(栈为空无栈顶元素\n); return false; } *value s-data[s-top]; return true; }注意出栈函数的写法先取出当前栈顶元素再进行top--。如果你写反了先减再取取到的就是上一个元素这是一个很隐蔽的错误我见过不止一个初学者在这里翻车。2.3 顺序栈最容易翻车的三个边界写顺序栈的时候有三个地方最容易出问题。第一个是入栈前的满检查。数组大小是MAX_SIZE栈满时top MAX_SIZE - 1。如果不做这个检查继续入栈就会越界写C语言不会提醒你但可能悄悄改坏相邻内存的数据。数据被改坏还不是最可怕的更麻烦的是这种错误往往不会立刻暴露而是运行很久之后才出现莫名其妙的结果排错的时候让人抓狂。第二个是出栈前的空检查。空栈时top -1此时如果还去访问data[top]访问的是数组下标为-1的内存这是未定义行为。在实际运行中可能不会立刻崩溃但结果完全不可控。第三个是运算符的优先级问题。s-data[(s-top)]这里我加了一对括号目的是明确先自增再取下标。虽然的优先级高于[]但不同编译器在复杂表达式下的行为可能会让人犯迷糊。我的习惯是涉及指针或下标自增自减时尽量用括号把运算顺序写明白避免靠优先级猜。这种好习惯能帮你少调试很多莫名其妙的bug。3. 链栈没有容量上限的栈头插法立刻出结果顺序栈有一个硬伤容量写死了。你用MAX_SIZE 100就只能存100个元素。如果想动态扩容还得写realloc之类的逻辑。链栈解决了这个问题理论上只要内存够链栈可以不停入栈不存在栈满的概念。3.1 为什么入栈要改造成头插链栈的核心思路是用链表节点存储元素让链表头结点成为栈顶。这样入栈操作等价于在链表头部插入一个新节点出栈操作等价于删除链表头结点。你可能会有疑问为什么不用尾插法因为如果使用尾插你还需要额外维护一个尾指针每次入栈都得通过尾指针插入出栈又得找到倒数第二个节点复杂度变高了。而头插法天然就匹配栈的操作特性最新的节点永远在最前面取栈顶只需要看头结点时间复杂度是O(1)。为了验证头插法确实能让栈操作更高效我对比一下尾插法出栈时如果是单链表你只能从头遍历到倒数第二个节点时间复杂度O(n)而头插法出栈直接操作头结点即可时间复杂度O(1)。这个差距在元素很多时非常明显。入栈同理。所以链栈设计成头部即栈顶是数据结构里的一个典型权衡。3.2 链栈实现与动态内存管理链栈的节点定义和单链表节点一样每个节点包含一个数据域和一个指针域typedef struct StackNode { int data; struct StackNode* next; } StackNode; typedef struct { StackNode* top; // 栈顶指针 int size; } LinkStack;这里我额外维护了一个size字段用来记录栈内元素个数。有了它取栈长度的操作就变成O(1)而不是O(n)。完整实现如下#include stdio.h #include stdlib.h #include stdbool.h typedef struct StackNode { int data; struct StackNode* next; } StackNode; typedef struct { StackNode* top; int size; } LinkStack; void initLinkStack(LinkStack* s) { s-top NULL; s-size 0; } bool isLinkStackEmpty(LinkStack* s) { return s-top NULL; } // 入栈头插法 bool linkStackPush(LinkStack* s, int value) { StackNode* node (StackNode*)malloc(sizeof(StackNode)); if (node NULL) { printf(内存分配失败\n); return false; } node-data value; node-next s-top; s-top node; s-size; return true; } // 出栈删除头结点 bool linkStackPop(LinkStack* s, int* value) { if (isLinkStackEmpty(s)) { printf(栈为空无法出栈\n); return false; } StackNode* temp s-top; *value temp-data; s-top temp-next; free(temp); s-size--; return true; } // 取栈顶 bool linkStackPeek(LinkStack* s, int* value) { if (isLinkStackEmpty(s)) { printf(栈为空\n); return false; } *value s-top-data; return true; } // 释放整个栈 void destroyLinkStack(LinkStack* s) { StackNode* cur s-top; while (cur ! NULL) { StackNode* temp cur; cur cur-next; free(temp); } s-top NULL; s-size 0; }这段代码里有一个特别需要注意的地方出栈时一定要先把temp节点的next保存下来或者先让top指向后一个节点再free。有些初学者会写这样的代码free(s-top); s-top s-top-next; // 错误s-top已经被释放了这里一旦执行free(s-top)该内存块就已经被系统回收了再去访问-next是未定义行为。正确顺序是先取值、再改指针、最后释放节点。关于内存管理还有一个容易被忽略的问题在销毁整个栈时也要一个一个节点地free不能只把top置为NULL。否则会造成内存泄漏。程序跑的时间短可能察觉不到但如果是长期运行的服务程序或嵌入式环境内存泄漏是个很严重的问题。3.3 链栈和顺序栈怎么选很多初学者会问那以后写栈到底用哪种我的建议是根据场景来对比项顺序栈链栈容量固定满了要扩容动态受限于内存内存分配一次性连续分配每次入栈单独分配访问速度快缓存友好稍慢涉及指针跳转和内存分配开销栈满判断需要不需要使用场景容量可预估、要求高性能容量不可预估、频繁创建销毁栈在实际项目中如果栈的最大深度是明确的顺序栈通常更合适因为数组在内存中是连续存储的CPU缓存命中率高性能更好。如果栈的深度完全不可预估链栈更合适至少不用担心栈满。这只是经验之谈具体情况还得看实际应用场景。4. 环形队列把你从假溢出里解救出来的写法队列的顺序存储比栈复杂一点。如果你直接用数组做一个普通队列很快就会发现一个尴尬的问题明明数组前面还有很多空位置但rear指针已经走到末尾了新元素入不进来。这就是经典的假溢出问题。4.1 线性队列的假溢出陷阱先用代码模拟一下线性队列的行为。假设队列容量为5一开始入队三个元素A、B、C。此时front 0指向Arear 3指向下一个空闲位置。然后连续出队三次队列里的A、B、C都走了front 3rear 3。虽然队列为空但数组的前面几个位置已经被浪费了。现在想入队一个新元素D按线性队列的逻辑应该放在data[rear]这个位置也就是data[3]。入队成功后rear 4。再入队Erear 5。此时rear已经等于容量MAX_SIZE程序会认为队列满了无法再入队。可是从数组内存来看data[0]、data[1]、data[2]这三个位置明明是空的。这就是假溢出数组空间没有真的用完但因为rear到了末尾队列却无法继续使用了。解决办法就是环形队列——把数组在逻辑上首尾相连当rear到达末尾时让它重新回到数组开头继续使用。4.2 环形队列如何用取模完成循环环形队列的实现并不复杂核心就一个操作取模。入队时rear (rear 1) % MAX_SIZE出队时front (front 1) % MAX_SIZE。这个取模运算把数组在逻辑上变成了一个环。打个比方环形队列就像一个圆形的转盘指针沿着转盘循环移动。转盘上有N个格子指针走到第N-1个格子后下一步就走回第0个格子。这个回绕操作在计算机里就是一次取模。结构体定义如下#define QUEUE_SIZE 5 typedef struct { int data[QUEUE_SIZE]; int front; // 指向队头元素 int rear; // 指向队尾的下一个空闲位置 } CircularQueue;这里有一个重要的设计约定front指向当前队头元素的位置rear指向下一个将要放入元素的位置。两个指针最初都指向下标0。4.3 判空判满的三种主流方案环形队列最经典的问题是怎么判断空和满。方案一牺牲一个存储单元。约定(rear 1) % MAX_SIZE front时队列为满。也就是始终浪费一个位置不用用于区分空和满。这种方法最简单常用缺点是要少存一个元素。方案二设置一个计数器。维护一个size变量入队加一出队减一size 0为空size MAX_SIZE为满。这种方法性能略差一点每次入队出队都要更新计数但逻辑直观不会浪费存储空间。方案三设置一个标志位。维护一个布尔变量flag入队时置true出队时置false然后靠front rear flag判断队列状态。我个人在写代码时最常用方案一因为它不需要额外维护变量而且在绝大多数场景下少存一个元素的影响微乎其微。下面我主要基于方案一来写代码。4.4 环形队列完整实现与测试环形队列的完整代码如下#include stdio.h #include stdbool.h #define QUEUE_SIZE 5 typedef struct { int data[QUEUE_SIZE]; int front; int rear; } CircularQueue; void initQueue(CircularQueue* q) { q-front 0; q-rear 0; } bool isQueueEmpty(CircularQueue* q) { return q-front q-rear; } bool isQueueFull(CircularQueue* q) { return (q-rear 1) % QUEUE_SIZE q-front; } bool enQueue(CircularQueue* q, int value) { if (isQueueFull(q)) { printf(队列已满无法入队 %d\n, value); return false; } q-data[q-rear] value; q-rear (q-rear 1) % QUEUE_SIZE; return true; } bool deQueue(CircularQueue* q, int* value) { if (isQueueEmpty(q)) { printf(队列为空无法出队\n); return false; } *value q-data[q-front]; q-front (q-front 1) % QUEUE_SIZE; return true; } int queueSize(CircularQueue* q) { return (q-rear - q-front QUEUE_SIZE) % QUEUE_SIZE; }这里有个很值得说道的小细节queueSize函数的写法。因为rear可能已经绕回前面了直接用rear - front可能得到负数。所以需要先加上QUEUE_SIZE再取模才能得到正确的元素个数。比如rear 1front 3实际有(1 - 3 5) % 5 3个元素这个结果是正确的。测试的时候我建议你专门写一个测试函数把边界情况都跑一遍。以QUEUE_SIZE 5为例空队列出队应该返回false。连续入队4个元素0、1、2、3此时第5个位置因为判满方案被占住了再入队第5个应该失败。出队一个元素后再入队一个元素此时应该成功而且新元素会出现在数组开头附近的位置。不断交替入队出队确保代码在绕圈的时候不会出错。实际操作下来环形队列的代码本身不算难但容易出现忘记取模的错误。比如入队后直接写q-rear只在初始化或者某些特殊情况下才凑巧正确等队列真的绕回起点的时候就会数组越界。5. 链式队列front和rear双指针缺一个效率就塌方链式队列是又一个用链表实现的队列。它和链栈不同链栈用头插法很合适但队列是先进先出必须从两端操作入队发生在队尾出队发生在队头。这就引出一个问题需要几个指针才够用5.1 为什么必须同时保留队头和队尾如果只有一个头指针指向队头节点出队时直接删除头结点就行这个容易。但入队就要从队头开始遍历整个链表一直走到最后一个节点再在末尾插入新节点。这个操作的时间复杂度是O(n)。如果你频繁入队队列长度又比较大这个性能开销是没法接受的。解决方案就是再加一个尾指针始终指向链表的最后一个节点。这样入队操作就变成tail-next指向新节点然后更新tail时间复杂度降为O(1)。代价是结构体多了一个指针字段以及你需要在每次入队出队时小心维护这个尾指针的状态。这个结构还有一个名字叫链队列在操作系统任务队列、异步任务调度等场景中非常常见。它相比环形队列最大的优势是容量动态可扩展不会突然满了。结构体定义如下typedef struct QueueNode { int data; struct QueueNode* next; } QueueNode; typedef struct { QueueNode* front; // 队头指针 QueueNode* rear; // 队尾指针 int size; } LinkQueue;5.2 入队出队完整实现与空队列边界处理链式队列的入队和出队操作代码如下#include stdio.h #include stdlib.h #include stdbool.h typedef struct QueueNode { int data; struct QueueNode* next; } QueueNode; typedef struct { QueueNode* front; QueueNode* rear; int size; } LinkQueue; void initLinkQueue(LinkQueue* q) { q-front NULL; q-rear NULL; q-size 0; } bool isLinkQueueEmpty(LinkQueue* q) { return q-front NULL; } // 入队在rear后面插入 bool linkQueueEn(LinkQueue* q, int value) { QueueNode* node (QueueNode*)malloc(sizeof(QueueNode)); if (node NULL) { printf(内存分配失败\n); return false; } node-data value; node-next NULL; if (q-rear NULL) { q-front node; q-rear node; } else { q-rear-next node; q-rear node; } q-size; return true; } // 出队从front删除 bool linkQueueDe(LinkQueue* q, int* value) { if (isLinkQueueEmpty(q)) { printf(队列为空无法出队\n); return false; } QueueNode* temp q-front; *value temp-data; q-front temp-next; free(temp); q-size--; if (q-front NULL) { q-rear NULL; } return true; } // 释放整个队列 void destroyLinkQueue(LinkQueue* q) { QueueNode* cur q-front; while (cur ! NULL) { QueueNode* temp cur; cur cur-next; free(temp); } q-front NULL; q-rear NULL; q-size 0; }这个代码里最关键的一点在出队操作的最后如果删除了队头节点后队列为空front变成了NULL此时必须同步把rear也置为NULL。如果不这么做会怎样想象一下队列里只有一个节点出队后front和rear都指向这个已经被free的节点。此时rear变成了一个悬空指针。如果再调用入队函数它会判断q-rear NULL发现不为空因为还指向残留地址于是执行q-rear-next node写入一个已释放的内存地址结果完全不可控。这个问题非常隐蔽我在调试时遇到过好几次最终都是在加了if (q-front NULL) q-rear NULL;之后才解决。另外我在这个实现里维护了一个size字段。其实队列的size不比栈通过front到rear不好算因为rear不记录位置所以想快速获取长度就必须额外维护一个计数器。5.3 链式队列与环形队列的取舍链式队列和环形队列哪个更好它们没有绝对优劣关键看使用场景。链式队列的优点很明显容量动态最多受内存限制插入和删除都是O(1)。缺点也很实在每次入队都要malloc频繁分配释放内存会带来开销和时间损耗。环形队列的优点则相反内存是提前分配好的连续空间不存在malloc开销CPU缓存友好性能更好。缺点就是容量固定。我的选择习惯是嵌入式开发、网络驱动这类对性能敏感且容量可预估的场景用环形队列上层业务逻辑里容量不确定、经常需要动态创建队列的场景用链式队列。6. 从实现到应用两个经典问题检验你是否真的懂了写完了四种结构光会实现还不算完。我始终觉得判断一个数据结构是不是真掌握要看你能不能用它解决实际问题。下面这两个经典题目栈和队列的底层能力会被体现得比较充分。6.1 括号匹配用栈做一次性语法检查这个题目在各种教材里出现频率极高给定一个只包含()[]{}的字符串判断括号是否成对匹配。思路就是用栈遍历字符串遇到左括号就入栈遇到右括号时弹出栈顶元素检查是否匹配。如果栈为空或者不匹配直接返回false。遍历结束之后如果栈不为空说明还有左括号没配对上也返回false。这里有一个栈的变体入栈的其实不一定是左括号本身也可以是对应的右括号。这样遇到右括号时就只需要比较是否和栈顶相等少写一个匹配函数。代码如下#include stdio.h #include stdbool.h #include string.h #define MAX_SIZE 100 typedef struct { char data[MAX_SIZE]; int top; } CharStack; void initCharStack(CharStack* s) { s-top -1; } bool charStackPush(CharStack* s, char c) { if (s-top MAX_SIZE - 1) return false; s-data[(s-top)] c; return true; } bool charStackPop(CharStack* s, char* c) { if (s-top -1) return false; *c s-data[(s-top)--]; return true; } bool isMatching(char* str) { CharStack stack; initCharStack(stack); for (int i 0; i strlen(str); i) { char ch str[i]; if (ch ( || ch [ || ch {) { // 入栈对应的右括号 char pushChar; if (ch () pushChar ); else if (ch [) pushChar ]; else pushChar }; if (!charStackPush(stack, pushChar)) { return false; } } else if (ch ) || ch ] || ch }) { char topChar; if (!charStackPop(stack, topChar)) { return false; // 栈为空右括号多了 } if (topChar ! ch) { return false; // 不匹配比如 ( 对上了 ] } } } return stack.top -1; // 所有左括号都被配对 }这段代码里入栈的是对应的右括号所以匹配时的比较变成了简单的字符相等判断。测试用例值得多跑几个()[]{}应该通过([)]应该失败((()))应该通过(()应该失败因为栈最后还有残留。6.2 用两个栈模拟队列面试经典变形题这是一个非常经典的面试题使用两个栈实现一个队列支持入队和出队操作。思路是栈A专门用来入队栈B专门用来出队。入队时直接push到栈A。出队时如果栈B不为空直接从栈B pop如果栈B为空就把栈A的所有元素依次pop并push到栈B中然后再从栈B pop。为什么这样能实现FIFO因为栈的LIFO特性可以反转元素顺序。第一次把元素压入栈A时顺序是正着的把栈A的元素倒到栈B后顺序就反了栈B栈顶元素恰好是最先进入栈A的元素。每次出队都从栈B取栈顶就相当于取了最早入队的元素。这段逻辑用上一节的顺序栈改一改就能跑通#include stdio.h #include stdbool.h // 这里直接复用之前实现的SqStack假设已有push、pop、isEmpty等函数 typedef struct { SqStack s1; // 入队栈 SqStack s2; // 出队栈 } QueueWithTwoStacks; void initQueueWithTwoStacks(QueueWithTwoStacks* q) { initStack((q-s1)); initStack((q-s2)); } bool pushToQueue(QueueWithTwoStacks* q, int value) { return push((q-s1), value); } bool popFromQueue(QueueWithTwoStacks* q, int* value) { if (isEmpty((q-s2))) { // s2为空先把s1全部倒过来 while (!isEmpty((q-s1))) { int temp; pop((q-s1), temp); push((q-s2), temp); } } if (isEmpty((q-s2))) { return false; // 两个栈都是空的队列为空 } return pop((q-s2), value); }这个设计的复杂度是均摊O(1)。每个元素最多经历一次入s1、一次倒到s2、一次出s2都是常数次操作。这个知识点面试时经常被追问建议你把这段逻辑彻底想透。还有一个类似的变形题是用两个队列模拟栈思路稍有区别入栈时往非空队列里入队出栈时把非空队列的前n-1个元素出队并入队到空队列最后一个元素就是栈顶直接出队。核心逻辑就是把队列前面的元素挪开让最后一个露出来。有了前面的基础实现起来应该不难。结尾在实际敲代码的过程中我比较深的体会是学栈和队列最怕的就是看着会了一写就废。数据结构这门课没有捷径只有基于代码实现加上足够的边界测试才算真正掌握。建议你可以把本文的四种结构都默写一遍然后准备一组边界测试用例——空栈出栈、栈满入栈、空队出队、环形队列满入队、链式队列删到空再入队——把这些情况都跑一遍哪里出问题就说明哪里还有理解漏洞。最后再分享一个小技巧如果你在编译器上调试环形队列的取模逻辑可以在入队出队操作里临时打印front和rear的值盯着它们观察是否真的在绕着0到MAX_SIZE-1循环。很多取模错误肉眼就能看出来不用闷头苦想。把这四种实现和两个经典应用吃透之后后面的二叉树、图、递归这些内容学起来会轻松不少。
