欢迎阅读本篇学习笔记。本篇作为个人计算机专业的学习记录这里将系统梳理栈和队列的相关知识点从基础概念到代码实现逐步展开便于后续的复习巩固。如有不足欢迎大家在评论区交流指正感谢大家的阅读与支持栈栈的概念与结构栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。栈比起顺序表和链表有更多的限制顺序表链表允许在头尾中间这些位置任意地去插入和删除数据栈呢它只允许在固定的一端插入和删除数据。举个简单的例子顺序表和链表可以把它们当成开放式置物架、开放式抽屉。架子上所有东西随便碰不管是第一层、中间层还是最后一层想拿哪个就拿哪个想在中间插个东西、拿走中间的物件都没问题没有任何限制。平时随便存一堆数据、随时调取任意内容就用它们。栈栈就像一摞叠起来的盘子。你只能拿最上面那一个盘子底下被压住的盘子不能直接抽出来想放盘子也只能堆在最顶上。 必须遵循后放上去的盘子先拿走底层的要等上面全部取完才能碰。下图是栈的入栈和出栈大家可以类比一下生活中的羽毛球桶又或者说像弹匣先压进去的子弹最后才打出去。栈的实现了解完栈的概念和结构我们来看一下栈的实现。实现栈我们有两种方法一种是用数组。一种是用链表。先来看一下用数组实现。栈中没有规定哪一端必须是栈顶所以在这里我们让方向向右的这一端是栈顶另一端为栈底。入数据1234那么出数据就是4321。单链表也是如此同样地让方向向右的这一端是栈顶另一端为栈底入栈时头插数据就可以了。那么这两种我们该选择哪一个呢其实各有各的好如果说非要选一个的话我觉得数组实现更好一些。这里只是我个人的观点好处就是数据全都挨在一起存在连续内存里特别贴合 CPU 高速缓存的预取机制读数据的时候缓存命中率高跑起来速度快而且代码写起来简单画图也好懂新手一眼就能分清栈顶和栈底。缺点一开始就得提前定好最大容量装满了就溢出报错要是预留的空间开太大里面又没存多少东西大片内存空着白白浪费。所以本文就以顺序栈来详细展开。下图是动态数组栈顺序栈 的结构体定义STDataType* a堆上动态数组指针存放栈数据内存连续CPU 缓存读取更快top栈顶标记记录当前有效元素数量top0代表栈空capacity数组最大容量当top capacity 时需要扩容初始化栈这里我们的top指向的是栈顶数据的下一个位置。如下图所示这只是其中一种我们也可以让top直接指向栈顶元素。也就是指向4的位置。如下图当top指向的是栈顶元素时我们初始化的方式也就要做出相对应的改变就需要让top指向-1。当栈中有元素时第一种初始化方式的top的下标就是栈中元素个数第二种top下标则是栈中元素个数-1。方式 1top0top指向栈顶的下一个位置top的值等于栈中有效元素的总个数。示例存入 3 个元素 →top3元素数量为 3栈顶元素的下标为top-12。方式 2top-1top直接指向栈顶元素top的值等于栈中元素个数减 1。示例存入 3 个元素 →top23-12top即为栈顶元素的下标。这是两种不同的初始化方式大家可以根据自己的喜好或是项目的需求灵活选用。销毁栈销毁和初始化逻辑相同这里就直接代码呈现。入栈开头我们用 assert 校验栈指针避免空指针崩溃当记录元素数量的 top 等于数组最大容量 capacity 时说明空间已满需要扩容无初始内存就先分配 4 个位置已有内存则容量翻倍扩容时先用临时指针接收 realloc 分配的地址防止分配失败丢失原有数据分配成功再更新数组指针与容量最后把新数据存入 top 对应的空位并让 top 自增。出栈这个函数实现非常简洁。虽然如此简短的代码看起来似乎没必要单独封装成函数直接访问结构体也能实现相同功能但我们仍建议采用这种方式。主要原因如下首先这种做法更加规范我们希望所有对栈数据的访问都通过专门的函数来完成而不是直接操作底层结构体。好比快递柜拿快递一摞快递只能拿最顶上的包裹出栈就像拿走最上面快递看着只是抬手取走一步动作但必须单独设一个取件流程。要是不单独做这个流程所有人都能直接伸手挪动整堆快递很容易乱了顺序统一封装成单独操作所有人取件都走同一套规矩不会有人乱扒、乱改堆叠顺序。下面的函数也是如此不能因为它简单就不单独封装。取栈顶元素判空获取数据个数这些代码实现较为直观相信大家都能轻松理解因此不再赘述。队列队列的概念和结构入队列是1234那么出队列也一定是1234。队列本质就是排队所有需要“按顺序、不插队”处理的事底层逻辑都是队列队列遵循先来先处理的规则超市收银、奶茶取餐、医院挂号都是现实队列不能插队电脑多份打印任务会按提交顺序输出聊天消息、客服工单也按发送先后处理凡是要按顺序处理、禁止插队的场景都对应队列逻辑。实现队列我们去探索一下能否使用单链表毕竟单链表更节省空间能省则省。链表实现的队列优势明显它能动态分配内存不存在固定大小限制在无法预估元素数量上限时极具灵活性像网络数据传输这类场景就很适用。同时按需分配内存避免了内存浪费。虽然它有指针开销和实现复杂的小瑕疵但整体而言在应对多变数据规模的场景中链表实现的队列功能更为强大。所以我们在这里就使用单链表来实现队列。队列节点队列的实现大家都知道单链表找尾的效率不高。因为单链表的节点只有 “后继指针”要找尾节点必须从表头开始逐个遍历所有节点直到找到最后一个next NULL的节点。这个过程的时间复杂度是 O(n)n 是链表长度链表越长找尾的耗时越久。为了更方便我们给了两个指针一个头指针phead一个尾指针ptail。这样一来我们函数就需要传入多个值这种设计虽然可行但让函数接收过多参数显然不够理想。我们可以进一步优化设计创建一个包含头指针和尾指针的Queue结构体。这样只需传递结构体本身即可既解决了二级指针的问题又能通过size字段直接获取数据量无需额外遍历链表。这与我们之前讲解的单链表有所不同。在介绍单链表时我们并没有同时定义两个节点指针因为两个指针无法完全解决单链表的所有操作问题。虽然它们可以处理尾插操作但对于尾删操作就无能为力了因为尾删需要找到前一个节点。所以当时我们就只使用了一个指针。队列的初始化队列数据个数队尾插入断言pq非空避免调用函数时传入NULL导致的空指针错误增强代码健壮性。动态分配节点链表队列的节点是 “按需创建” 的用malloc分配内存同时必须检查malloc的返回值防止内存分配失败。新节点初始化newnode-next NULL是关键 —— 因为新节点是队尾后续不会有其他节点所以后继指针必须置空。分情况插入队列为空时头、尾指针都要指向新节点此时队列只有一个节点既是头也是尾队列非空时直接通过pq-ptail找到当前队尾把新节点链到队尾的next再更新ptail为新节点。更新size每次插入成功后队列长度 1方便后续获取队列元素个数。队头删除首先先做俩 “安全检查”先确认传进来的队列不是空的不然删个寂寞再确认队列里有东西空队列删不了。然后分两种情况删队列里就一个节点 队头后面没别的节点了那直接把这个队头的内存释放掉然后把队列的头和尾指针都设成空 —— 毕竟删完就没东西了。队列里有好几个节点 先把队头后面那个节点 “记下来”怕删了队头就找不着后面的了然后把当前队头的内存释放掉再让队头指针指向刚才记下来的那个节点 —— 相当于让原来的 “老二” 变成新队头。最后队列里的元素少了一个把记录长度的数减 1 就行。整个过程就是 “删队头要么删完空了要么让下一个顶上”很快不用遍历。当只有一个节点时这里free(pq-phead)也相当于free掉了ptail因为它们指向的是同一块空间不用再free掉ptail申请内存就像和银行借钱。可以把内存理解成 “银行的钱”malloc申请内存是 “找银行借一笔钱”—— 银行给你一笔钱你用这笔钱 “盖了个节点的房子”存数据、存指针。而free就是 “把这笔钱还给银行” 比如代码里的free(pq-phead)就相当于 “你把之前从银行借的、用来盖‘队头这个房子’的钱完整还给银行”—— 还钱之后“队头这个房子” 就不属于你了你不能再用它再操作这个节点会出问题。简单说malloc是 “借钱盖房”free是 “退房还钱”把借的内存钱还给系统银行避免 “欠银行的钱越积越多”内存泄漏。取队头队尾数据队列判空销毁队列先确认要清理的队列是有效的不是空指针然后从队头开始遍历所有节点。每处理一个节点时先记下它的下一个节点避免删完找不到后续节点再把当前节点的内存释放掉接着处理下一个。等所有节点都删完把队列的头、尾指针都设为空长度也重置为 0这样队列就完全清空不会占内存了之后还能重新用。好啦那这篇内容就先整理到这里这次把栈和队列的相关知识整理了一下为了方便自己日后复习回顾也希望能给正在学习的小伙伴一些参考。如果文中有理解不到位或是书写有误的地方欢迎大家在评论区指出一起交流共同进步。谢谢大家