数据结构笔记：线性表、栈与队列的存储结构详解

数据结构这门课我前前后后翻过不下五遍每次重读王道笔记都有新体会。第二篇笔记主要覆盖线性表后半段到栈、队列、串这几块内容也是很多人第一次真正被“指针绕晕”的地方。这篇笔记我打算换个讲法不按教材顺序平铺而是按“我当初哪里卡住、后来怎么想通、实际写代码时怎么用”这条线来组织。适合正在啃数据结构基础、准备考试或者想补一补底层功底的读者哪怕你之前只写过业务代码、没怎么碰过指针也能顺着往下看。核心关键词就三个线性表、栈与队列、存储结构这三个词基本决定了后面树、图、查找排序的学习手感。1. 整体设计思路为什么这几块内容要放在一起学1.1 线性表、栈、队列本质是同一条线的三种用法很多人学的时候把线性表、栈、队列当成三个独立知识点背背完发现记不住做题也不会。我后来想明白一件事它们本质都是“一条线”区别只在于允许在哪一端操作。线性表是两端都能插能删栈是只允许在一端栈顶插删队列是一端进一端出。你把这条线想清楚了三者的操作差异就是一句话的事。这个认知很关键因为它直接决定了你后面写代码时的选择。比如你要做一个“撤销”功能第一反应应该是栈因为撤销天然是后进先出你要做任务排队第一反应是队列先进先出符合公平性。如果脑子里只有“线性表”一个模糊概念遇到具体场景就选不出来。我当初踩的坑是把顺序表和链表当成两种“表”把栈和队列当成另外两种“结构”结果学完脑子里是四坨东西。后来重新梳理发现正确的理解是两个维度第一个维度是逻辑结构线性还是非线性第二个维度是存储结构顺序还是链式。线性表、栈、队列在逻辑结构上都是线性的只是操作受限程度不同而每一种都可以用顺序存储或链式存储来实现。这样一交叉四坨东西就变成了一个二维表格记忆量直接减半。1.2 存储结构的选择逻辑顺序还是链式顺序存储和链式存储的取舍是这一章最值得花时间想清楚的问题。我见过太多人背“顺序表随机访问快、链表插入删除快”但真到写代码或者做题时还是选错。原因是没有把“快”量化也没有结合具体场景。顺序存储的核心优势是随机访问 O(1)因为地址连续第 i 个元素的位置可以直接算出来base i * sizeof(ElemType)。这个公式是顺序表的命根子理解它你就理解了为什么下标从 0 开始、为什么插入要移动元素。链式存储的核心优势是插入删除 O(1)前提是已经定位到位置因为只需要改指针不需要搬数据。但这里有个隐藏前提经常被忽略链表的 O(1) 插入删除是建立在“你已经拿到那个结点的指针”之上的。如果你还要花 O(n) 去找位置那整体还是 O(n)。这一点在做题时特别容易翻车比如“在单链表第 i 个位置插入元素”定位本身就要 O(n)所以整体并不是 O(1)。我当初就是被这句“链表插入快”坑过做题时想当然写了个 O(1) 的答案结果错了。实际选型我一般按这个思路走如果数据量可预估、查询远多于增删优先顺序表如果数据量变化大、增删频繁且能拿到位置引用优先链表。还有一个容易被忽略的点是缓存友好性顺序表因为内存连续CPU 缓存命中率高实际跑起来往往比理论复杂度看起来更占优这一点在数据量大的时候尤其明显。1.3 这一章在整个数据结构体系里的位置线性表是后面所有内容的“地基”。栈和队列是线性表的受限版本串是线性表的元素特化为字符树可以看成是“一对多”的推广图是“多对多”的推广。你把线性表的顺序存储和链式存储这两套操作练熟了后面学树的二叉链表、图的邻接表本质上都是同一套指针操作换个形状。所以我的建议是这一章不要图快顺序表和单链表的基本操作插入、删除、查找、遍历最好能手写出来不看答案。这不是为了考试而是为了让手指记住指针的移动方式。我当初偷懒只背了伪代码结果学到二叉树的时候写递归建树卡了半天回头补链表才补回来。这个教训挺深的基础操作的手感是省不掉的。2. 顺序表与链表核心细节和手写要点2.1 顺序表的插入删除移动次数要会算顺序表插入的核心动作是“从后往前挪”。假设表长 n要在第 i 个位置1 ≤ i ≤ n1插入需要把第 i 到第 n 个元素整体后移一位移动次数是n - i 1。删除第 i 个元素1 ≤ i ≤ n需要把第 i1 到第 n 个元素前移一位移动次数是n - i。这两个公式建议不要死记而是画个图推一遍。我当初的记忆方法是插入是“腾位置”从最后一个开始往后挪挪到第 i 个为止所以是 n 到 i共 n-i1 个删除是“填坑”从第 i1 个开始往前挪挪到第 n 个为止共 n-i 个。画一次图比背十遍公式管用。平均移动次数也值得算一下。插入时假设在每个位置等概率插入平均移动n/2次删除时平均移动(n-1)/2次。所以顺序表的插入删除平均时间复杂度都是 O(n)。这个结论要理解成“因为要搬数据”而不是背下来。注意顺序表插入时判断“表满”要在移动之前做判断“i 是否合法”要在表满判断之前做。顺序反了边界情况就会出错。我见过有人先判断表满再判断 i结果 i 非法时也报了“表满”逻辑就乱了。2.2 单链表插入删除指针顺序是命门单链表最容易出错的地方不是思路而是指针赋值的顺序。以在结点 p 之后插入新结点 s 为例正确顺序是s-next p-next; p-next s;这两行的顺序绝对不能反。如果先写p-next s那 p 原来的后继就丢了s 的 next 指向哪里就无从谈起链表直接断掉。我当初练习时故意写反过一次程序跑起来遍历到一半就崩了调试了半天才反应过来。这个错误看起来低级但手写代码紧张时真的会犯。删除结点 p 的后继结点 q正确顺序是q p-next; p-next q-next; free(q);这里的关键是先保存 q再改 p 的指针最后释放。如果先p-next p-next-next再想释放那个结点已经找不到了造成内存泄漏。这个顺序问题在考试的手写代码题里非常常见评分点往往就在这几行的顺序上。还有一个经典技巧是头结点。带头结点的单链表插入删除时不需要单独处理“在第一个位置操作”的情况因为第一个位置前面永远有个头结点逻辑统一了。我强烈建议手写代码时默认带头结点能省掉大量 if-else 判断。代价是多占一个结点的空间完全值得。2.3 双链表与循环链表多一个指针的收益双链表每个结点多一个prior指针指向前驱好处是删除结点时不需要从头找前驱。单链表删除结点 p 需要知道 p 的前驱而双链表直接p-prior就拿到了。代价是插入删除时要维护两个指针代码量翻倍出错概率也翻倍。双链表插入有个口诀先连新结点的两个指针再改老结点的指针。以在 p 之后插入 s 为例s-prior p; s-next p-next; p-next-prior s; p-next s;这四行的顺序有讲究。前两行是给 s 赋值随便先写哪个都行第三行要求p-next还是原来的后继所以必须在第四行之前第四行一执行p-next就变了所以它必须最后。我记这个顺序的方法是“先让新结点站稳再动老结点”跟单链表“先接后断”是一个道理。循环链表则是把尾结点的 next 指回头结点或首结点形成一个环。它的好处是从任意结点出发都能遍历全表判断遍历结束的条件从“p 为空”变成“p 回到起点”。这个改动很小但用起来很顺手尤其是后面学循环队列的时候思想是相通的。2.4 静态链表用数组模拟指针静态链表是个容易被跳过但很值得看一眼的知识点。它用数组存结点每个结点里有一个“游标”代替指针指向下一个结点在数组中的下标。0 号位置通常当“头结点”用游标为 -1 表示结束。为什么要有这个东西因为在某些不支持指针的语言里或者在某些需要“地址稳定”的场景下用数组下标代替指针是常见做法。理解静态链表能帮你把“指针”这个概念从“内存地址”抽象成“指向关系”这对后面理解各种链式结构很有帮助。我当初学的时候觉得它没用后来发现它其实是“用索引代替指针”这一思想的原型很多实际系统里都能见到类似设计。3. 栈与队列从受限操作到实际应用3.1 栈的顺序存储top 指针的两种约定顺序栈用一个数组加一个 top 指针实现。这里有个细节经常让人困惑top 到底指向栈顶元素还是指向栈顶元素的下一个位置两种约定都有人用关键是前后一致。我习惯用“top 指向栈顶元素”的约定初始时top -1表示空栈。入栈是stack[top] x出栈是x stack[top--]。这种写法很对称不容易错。另一种约定是 top 指向下一个空位初始top 0入栈stack[top] x出栈x stack[--top]。两种都对但混用就会出 bug。栈满的条件也要看约定。top 指向栈顶元素时栈满条件是top MaxSize - 1top 指向下一个空位时栈满条件是top MaxSize。我当初做题时因为没注意题目用的是哪种约定判断栈满写错了白白丢分。所以看题第一件事是确认 top 的约定。提示共享栈是个常考的小技巧。两个栈共用一个数组一个从下标 0 往右长一个从 MaxSize-1 往左长栈满条件是top1 1 top2。这个设计能把空间利用率拉满思路值得记一下。3.2 栈的链式存储头插法的天然应用链栈其实就是只能在头部插入删除的单链表所以入栈出栈都在表头进行天然对应头插法。因为只在头部操作链栈不需要头结点栈顶指针直接指向第一个元素空栈时栈顶指针为空。链栈的好处是不用担心栈满除非内存耗尽。代价是每个元素多一个指针的空间开销而且出栈时要记得释放结点。我实际写链栈时出栈操作会写成x top-data; p top; top top-next; free(p);这里同样要注意“先保存再释放”的顺序跟单链表删除是一个道理。3.3 队列的顺序存储假溢出与循环队列顺序队列最坑的地方是假溢出。普通顺序队列用 front 和 rear 两个指针入队 rear 后移出队 front 后移。当 rear 到达数组末尾时即使前面还有空位也无法再入队了这就是假溢出。解决办法是循环队列把数组看成一个环rear 和 front 到达末尾后回到 0。这里有个经典问题如何区分队空和队满因为循环之后队空和队满时 front 和 rear 可能相等。常见有三种处理方式处理方式队空条件队满条件元素个数牺牲一个单元front rear(rear1) % MaxSize front(rear - front MaxSize) % MaxSize增设 size 变量size 0size MaxSizesize增设 tag 标志front rear 且 tag 0front rear 且 tag 1按 tag 推算考试里最常见的是第一种“牺牲一个单元”因为不需要额外变量。代价是数组里永远有一个位置空着实际容量是 MaxSize-1。我当初不理解为什么要牺牲一个单元后来想通了如果不牺牲队空和队满的条件就完全一样没法区分。牺牲一个单元本质是用一个位置换一个“判断依据”很划算。元素个数公式(rear - front MaxSize) % MaxSize建议理解着记rear 减 front 是两者距离加 MaxSize 是为了处理 rear 在 front 前面的情况负数取模是绕回环内。这个公式在写循环队列代码时天天用。3.4 队列的链式存储带头结点更省心链队列用单链表实现入队在表尾出队在表头。这里有个设计选择带不带头结点。我建议带头结点因为不带的话出队时如果队列只剩一个元素删除后要把 rear 指针也置空需要特判带头结点后这个特判就没了逻辑统一。链队列的队空条件是front rear都指向头结点入队是rear-next s; rear s;出队是p front-next; front-next p-next;如果出队的是最后一个元素还要rear front。这个“最后一个元素出队后 rear 回退”的细节很容易漏漏了之后下次入队就会出错。3.5 栈和队列的应用场景对照学完结构最重要的是知道什么时候用。我整理了一个对照表都是实际写代码时会遇到的场景场景用栈还是队列原因括号匹配栈后遇到的左括号先匹配后进先出表达式求值栈运算符优先级决定先算谁天然后进先出函数调用栈后调用的函数先返回撤销操作栈最近的操作最先撤销任务排队队列先来先服务公平广度优先遍历队列按层扩展先进先出缓冲区队列数据按到达顺序处理这张表我建议自己再补充几行把平时写业务代码遇到的场景往里填。填的过程就是理解的过程。比如我做过的消息处理多个生产者往一个队列里塞任务多个消费者按顺序取这就是典型的队列应用而嵌套的配置解析一层套一层用栈处理最自然。4. 串与常见问题排查实录4.1 串的存储与模式匹配入门串是元素为字符的线性表存储结构同样分顺序和链式。顺序存储就是字符数组链式存储因为每个结点存一个字符太浪费空间通常一个结点存多个字符叫“块链结构”。实际用的时候基本都是顺序存储因为字符串操作大多是整体处理链式反而麻烦。模式匹配是串这一节的重点。朴素匹配BF 算法的思路是从主串的每个位置开始逐个和模式串比较不匹配就主串指针回退到开始位置的下一个模式串指针回到 0。最坏时间复杂度 O(n*m)n 是主串长度m 是模式串长度。BF 算法的问题在于主串指针会回退做了很多重复比较。KMP 算法就是来解决这个问题的核心是利用模式串自身的部分匹配信息让主串指针不回退。KMP 的 next 数组是很多人卡住的地方我当初也是背了忘、忘了背。后来我的理解方式是next[j] 表示“模式串前 j 个字符中最长的相等前后缀长度”匹配失败时模式串跳到这个位置继续比因为前缀和后缀相等前面那段就不用再比了。next 数组的手算方法对每个位置 j看它前面的子串找最长的“前缀等于后缀”的长度。比如模式串ababj3字符 b前面是aba前缀a和后缀a相等长度 1所以 next[3]1。这个方法手算慢但不容易错考试时够用。真正写代码时我更倾向于直接调用现成的字符串查找函数除非题目明确要求手写 KMP。4.2 常见问题速查表这一章我踩过的坑和见过别人踩的坑整理成一张表做题或写代码前扫一眼能省不少时间问题现象可能原因排查方法链表遍历到一半崩溃插入时指针顺序写反链表断裂检查s-next p-next是否在p-next s之前删除结点后程序异常先改指针后释放或释放后还访问确认“保存-改指针-释放”的顺序循环队列元素个数算错忘记加 MaxSize 处理负数用(rear - front MaxSize) % MaxSize循环队列队满判断失效没牺牲单元也没加辅助变量确认采用哪种区分方式条件要配套链队列出队后入队出错最后一个元素出队后没回退 rear出队后判断是否为空空则rear front顺序表插入越界没先判断 i 的合法性先判 i再判表满最后移动栈的 top 约定混用一半按指向栈顶写一半按指向下一位置写全文统一一种约定KMP 的 next 算错前后缀理解偏差手算时逐个位置列前缀后缀对照这张表里前两个是手写代码最高频的错误中间三个是循环队列和链队列的经典坑后面三个是概念理解不到位的表现。我建议把自己做题时犯的错也往这张表里加慢慢就形成自己的“错题本”了。4.3 几个容易被忽略的实操心得第一个心得是画图。链表和栈队列的题光在脑子里想很容易乱拿张纸把结点和指针画出来标上序号插入删除时一步步改箭头错误率能降一大半。我当初嫌画图慢硬想结果反复出错后来老老实实画图反而快了。第二个心得是边界测试。写完一个链表操作至少测四种情况空表、只有一个元素、操作第一个元素、操作最后一个元素。这四种情况覆盖了绝大多数边界 bug。我见过太多代码在正常数据下跑得好好的一到空表就崩。第三个心得是复杂度要会推不要背。比如“顺序表插入平均移动 n/2 次”这个结论是假设等概率插入推出来的如果题目说“只在表尾插入”那平均移动就是 0。所以看到复杂度题先看前提条件别上来就套公式。第四个心得是代码风格统一。变量命名、top 的约定、是否带头结点这些在一道题里要前后一致。我当初做一道综合题前面用 top 指向栈顶后面写着写着变成指向下一位置自己都没发现检查时才对上。统一约定这件事说起来简单做起来真的需要刻意提醒自己。5. 我个人的学习节奏建议这一章的内容量不算大但细节密度高我的建议是分三轮走。第一轮通读把顺序表、链表、栈、队列、串的概念和基本操作过一遍不求全记住求有个整体印象第二轮动手把每种结构的插入删除查找遍历手写一遍写完自己造边界数据测第三轮查漏对着常见问题表过一遍把错过的题重做。三轮之间不用隔太久我当初是每轮隔两三天趁热打铁。拖太久前面忘光等于重来。另外手写代码这件事别只在纸上写找个能跑的环境实际跑一下指针错误在纸上不容易发现跑起来一崩就暴露了。我当初就是纸上写得好好的上机一跑全是段错误调了几次才养成“写完就跑”的习惯。最后分享一个我自己的小方法每学完一个结构试着用一句话说清楚“它是什么、它比别的结构强在哪、什么场景该用它”。说不出来说明还没真懂。这个自测方法很土但对我特别有效你也可以试试。