拓冰网站定制 
博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub数据结构专栏路漫漫其修远兮吾将上下而求索文章目录前言栈专题一、概念二、代码实现准备头文件内容总览初始化判断空间容量添加入栈删除出栈获取栈顶元素判断是否为空获取元素个数销毁栈一份测试代码总结队列专题一、概念二、代码实现头文件内容总览初始化添加入队删除出队获取队头数据获取队尾数据判断是否为空获取元素个数销毁队列一份测试代码总结三、四种实现的全面对比方向选择对比表格整体总结四、练习前言——栈和队列是计算机科学中最基础、最常用的两种抽象数据类型。几乎每个程序员都能随口说出“栈是后进先出LIFO队列是先进先出FIFO”但在实际工程中选择数组还是链表作为底层容器会显著影响性能、内存占用和代码复杂度。本期将使用C语言实现栈和队列其主要内容包括1.使用头文件声明、源文件定义的形式呈现源码2.介绍栈与队列的概念并使用数组实现栈链表实现队列3.提供图例和使用链表实现栈数组实现队列的对比表格栈专题一、概念——栈是一种操作受限的线性表只允许在固定一端进行插入和删除数据操作进行插入和删除操作的一端称为栈顶另一端称为栈底栈中的数据遵循后进先出原则(LIFO:List In First Out)栈的插入操作被称为进栈入栈压栈在栈顶插入栈的删除操作被称为出栈在栈顶删除生活中的实例空羽毛球桶第一个被放入的羽毛球最后一个被取出最后一个被放入的羽毛球第一个被取出(在不暴力拆除桶底的情况下(▽))注说了这么多但总结来看数据结构栈的本质还是数组只是操作受限数据结构栈的物理结构和逻辑结构示例图二、代码实现准备前置知识assert()函数介绍C语言标准库中的调试宏用于在程序运行时检查条件是否成立。若条件为假0则输出错误信息文件、行号、表达式并调用 abort()终止程序若条件为真非0则无动作。常用于捕捉“不可能发生”的逻辑错误、验证函数前置条件等perror()函数介绍C 语言标准库函数用于打印错误信息。调用格式perror(“前缀字符串”)输出格式为“前缀字符串错误原因\n”常用于系统调用或库函数失败后快速定位错误原因exit()函数介绍C 语言标准库函数用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统0or EXIT_SUCCESS表示成功-1or EXIT_FAILURE表示失败布尔值C语言并不自带布尔值作为内置数据类型使用需引入标准库stdbool.h头文件内容总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintSTDataType;#栈typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;#初始化栈voidSTInit(ST*pst);#添加入栈voidSTPush(ST*pst,STDataType x);#删除出栈voidSTPop(ST*pst);#获取栈顶元素 STDataTypeSTTop(ST*pst);#判断是否为空 boolSTEmpty(ST*pst);#获取元素个数intSTSize(ST*pst);#销毁栈voidSTDestroy(ST*pst);栈的属性有使用动态开辟的数组 arr用于指向栈顶的指针 top 和用于存储数组当前容量的 capacity。栈从逻辑上操作受限因此除基础的初始化和销毁外只能从栈顶入栈和出栈不能在指定位置插入或删除元素也只能获取当前栈顶的元素。除此之外还有两个判断栈信息的函数用于确定栈是否为空以及返回当前栈内的元素个数初始化voidSTInit(ST*pst){assert(pst);pst-arrNULL;pst-top0;pst-capacity0;}传入栈并断言传入的指针不为 NULL关于 top 的初始化有一个重要的点涉及到后续操作的逻辑控制如果 top 指向栈顶则需将 top 初始化为 -1如果初始化为零会出现 top 为零时无法判断当前栈中是否还有元素的问题。如果 top 指向栈顶元素的下一个位置就将其初始化为零这种写法便于判满、入栈和返回元素个数判断空间容量voidSTCheckCapacity(ST*pst){if(pst-toppst-capacity){intnewcapacity(pst-capacity0?4:pst-capacity*2);STDataType*tmp(STDataType*)realloc(pst-arr,newcapacity*sizeof(STDataType));if(tmpNULL){perror(realloc fail);exit(1);}pst-arrtmp;pst-capacitynewcapacity;}}当 top 等于 capacity 时需动态扩容当第一次扩容时初始化容量为4否则扩容为当前容量的二倍扩容后需判断是否扩容成功失败返回提示信息后退出程序成功时再执行更新操作添加入栈voidSTPush(ST*pst,STDataType x){assert(pst);STCheckCapacity(pst);#入栈 pst-arr[pst-top]x;}传入栈与要添加的元素断言传入指针不为 NULL判断容量与顺序表相同在数组尾插数据并让 top删除出栈voidSTPop(ST*pst){assert(pstpst-top);#出栈 pst-top--;}传入栈断言传入指针不为 NULL 且栈中元素个数不为0与顺序表相同使 top-- 就能达到逻辑删除获取栈顶元素STDataTypeSTTop(ST*pst){assert(pstpst-top);#获取栈顶元素returnpst-arr[pst-top-1];}传入栈断言传入指针不为 NULL 且栈中元素个数不为0top 指向栈顶的下一个位置可以利用 top - 1 找到并返回栈顶元素判断是否为空boolSTEmpty(ST*pst){assert(pst);#判断是否为空returnpst-top0;}传入栈断言传入指针不为 NULL在数组中能根据每个元素的下标位置确定在这个元素前还有几个元素例如下标为3的元素它的前面就刚好有3个值所以我们同样可以根据 top 是否指向栈底判断栈是否为空为空返回 true否则返回 false获取元素个数intSTSize(ST*pst){assert(pst);#获取元素个数returnpst-top;}传入栈断言传入指针不为 NULL同上top 指向栈顶元素的下一个位置因此就为当前栈中的元素个数销毁栈voidSTDestroy(ST*pst){assert(pst);free(pst-arr);pst-arrNULL;pst-toppst-capacity0;}传入栈断言传入指针不为 NULL释放栈在堆区开辟的动态空间并将指针初始化初始化 top 和容量一份测试代码voidTest_Stack(){ST s;#初始化测试STInit(s);#入栈测试STPush(s,4);STPush(s,3);STPush(s,2);STPush(s,1);#出栈测试STPop(s);STPop(s);#获取栈顶元素测试printf(%d\n,STTop(s));#判断是否为空测试printf(%d\n,STEmpty(s));#获取元素个数测试printf(%d\n,STSize(s));#销毁测试STDestroy(s);}总结数组实现栈的优缺点维度分析时间复杂度所有操作均为O(1)空间复杂度O(N)但存在一定的容量预留可能导致空间浪费缓存命中率极好连续内存CPU 预加载效率高扩容成本动态扩容时需复制整个数组单次操作 O(N)但均摊后很低适用场景频繁压栈弹栈、对速度要求极高、元素数量可预估的场景队列专题一、概念——队列也是一种操作受限的线性表只允许在固定一端进行插入数据操作另一端进行删除数据操作插入数据的一端称为队尾删除数据的一端称为队头队列中的数据遵循先进先出的原则(FIFO:First In First Out)队列的插入操作被称为入队在队尾插入队列的删除操作被称为出队在队头删除生活中的实例排队购买先来的人先买到票后从队头离开后来的人排在队尾等待整个流程有序进行(没有人插队的情况)数据结构队列的物理结构和逻辑结构示例图二、代码实现头文件内容总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintQDataType;#定义队列的节点结构typedefstructQueueNode{QDataType data;#存储值structQueueNode*next;#指向下一个节点的指针}QNode;#定义存储队列信息的结构typedefstructQueue{QNode*phead;#指向队头的指针 QNode*ptail;#指向队尾的指针intsize;#当前的元素个数}Queue;#初始化队列voidQueueInit(Queue*pq);#添加入队voidQNodePush(Queue*pq,QDataType x);#删除出队voidQNodePop(Queue*pq);#获取队头数据 QDataTypeQueueFront(Queue*pq);#获取队尾数据 QDataTypeQueueBack(Queue*pq);#判断是否为空 boolQueueEmpty(Queue*pq);#获取元素个数intQSize(Queue*pq);#销毁队列voidQueueDestroy(Queue*pq);从代码看队列无疑多用了一个结构体用于实现完整结构该结构的作用在于明确队头和队尾在物理存储结构中的位置使我们无需考虑操作物理结构链表时执行的额外操作只需将重点放在对队列的操作逻辑上。与此同时我们注意到队列中有一个名为 QSize 的函数用于获取当前队列中的元素个数我们知道统计整条链表的元素个数需要完整遍历获得单次操作的时间复杂度为O(N)为高效可以在 Queue 结构体中额外维护一个变量 size 用于记录队列中的元素个数使 QSize 函数的时间复杂度优化为O(1)初始化voidQueueInit(Queue*pq){assert(pq);pq-pheadpq-ptailNULL;pq-size0;}传入队列并断言传入的指针不为 NULL当前队列中无节点因此将队头指针和队尾指针都置空并使 size 初始化为0添加入队voidQNodePush(Queue*pq,QDataType x){QNode*newnode(QNode*)malloc(sizeof(QNode));if(newnodeNULL){perror(malloc fail);return;}newnode-datax;newnode-nextNULL;#入队if(pq-ptailNULL){pq-pheadpq-ptailnewnode;}else{pq-ptail-nextnewnode;pq-ptailnewnode;}pq-size;}传入队列与要添加的元素断言传入指针不为 NULL创建新节点分为两种情况当队列中无任何元素时应该将队头指针与队尾指针同时指向入队节点否则就使当前队尾元素的 next 指向入队节点后修改队尾指针删除出队voidQNodePop(Queue*pq){assert(pqpq-size);#出队 #队列元素为1时删除导致队尾指针为野指针 QNode*nextpq-phead-next;free(pq-phead);if(nextNULL)pq-pheadpq-ptailnext;elsepq-pheadnext;pq-size--;}传入队列断言传入指针不为 NULL 且队列元素个数不为0分为队列元素个数为1和不为1两种情况为1时在销毁队头指针指向的节点后需同时修改头尾指针指向为 NULL不为1时只修改队头指针指向获取队头数据QDataTypeQueueFront(Queue*pq){assert(pqpq-size);#获取队头数据returnpq-phead-data;}传入队列断言传入指针不为 NULL 且队列元素个数不为0直接通过队头指针返回第一个元素获取队尾数据QDataTypeQueueBack(Queue*pq){assert(pqpq-size);#获取队尾数据returnpq-ptail-data;}传入队列断言传入指针不为 NULL 且队列元素个数不为0通过队尾指针返回最后一个元素判断是否为空boolQueueEmpty(Queue*pq){assert(pq);#判断是否为空returnpq-size0;}传入队列断言传入指针不为 NULL通过维护的变量 size 判断为空返回 true非空返回 false获取元素个数intQSize(Queue*pq){assert(pq);#获取元素个数returnpq-size;}传入队列断言传入指针不为 NULLpass销毁队列voidQueueDestroy(Queue*pq){assert(pq);QNode*curpq-phead;while(cur){QNode*nextcur-next;free(cur);curnext;}pq-pheadpq-ptailNULL;pq-size0;}传入队列断言传入指针不为 NULL与销毁链表的流程大致相同注意需初始化头尾指针和 size 变量一份测试代码voidTest_Queue(){Queue q;#初始化测试QueueInit(q);#入队测试QNodePush(q,1);QNodePush(q,2);QNodePush(q,3);QNodePush(q,4);#出队测试QNodePop(q);QNodePop(q);#获取队头数据测试printf(%d\n,QueueFront(q));#获取队尾数据测试printf(%d\n,QueueBack(q));#判断是否为空测试printf(%d\n,QueueEmpty(q));#获取元素个数测试printf(%d\n,QSize(q));#销毁队列测试QueueDestroy(q);}总结链表实现队列的优缺点维度分析时间复杂度所有操作均为 O(1)空间复杂度O(N)每个元素额外存储一个指针变量64 位系统下 8 字节缓存命中率较差节点在堆中分散分配跳跃访问导致缓存未命中扩容成本无需扩容动态增长无一次性复制开销适用场景元素数量动态变化大、无法预估容量、频繁入队出队且对内存分配不敏感的场景三、四种实现的全面对比方向选择我们换位思考先看链表实现栈的场景如果用表头做栈底表尾做栈顶则每次返回栈顶数据都需遍历链表操作的时间复杂度为O(N)。如果用表头做栈顶表尾做栈底则时间复杂度不变再看数组实现队列的场景使用高下标位的方向作为队头低下标位的方向作为队尾时执行入队操作时需整体右移元素时间复杂度为O(N)。使用高下标位的方向作为队尾低下标位的方向作为队头时执行出队操作时需整体左移元素时间复杂度为O(N)。如果两种操作均不移动元素在使用数组实现队列时会出现假溢出问题导致浪费空间越来越多由此关于栈顶、栈底、队头、队尾方向的选择问题便有了大致的概念对比表格为了更清晰地看到 数组 vs 链表 在栈和队列上的差异下表从多个维度做了详细对比对比维度数组实现栈链表实现栈链表实现队列数组实现队列底层结构连续内存数组单向链表头插/头删单向链表头删/尾插连续内存数组 头尾指针核心操作入栈、出栈在数组末尾入栈、出栈在链表头部入队在尾部出队在头部入队在尾部出队在头部最坏时间复杂度入栈扩容时 O(N)始终 O(1)始终 O(1)入队扩容时 O(N)需要搬移元素 O(N)空间占用容量可能大于实际元素数浪费空间每个元素多一个指针额外空间开销大每个元素多一个指针额外空间开销大容量可能浪费但无指针开销缓存命中率极好顺序访问差节点分散差节点分散极好顺序访问是否需要动态扩容需要有复制成本不需要动态分配节点不需要动态分配节点需要有复制成本空栈/空队列判断top 0head NULLsize 0front rear典型应用场景函数调用栈、表达式求值浏览器历史可双向消息队列、BFS 队列任务队列但实际多用链表——数组天生适合栈因为栈的操作只在一端进行数组的末尾操作O(1)且缓存命中率高扩容成本均摊后微乎其微。链表天生适合队列因为队列要在两端操作链表的头删尾插均为O(1)且无需搬移元素动态增长无容量限制。整体总结通过本文你不仅掌握了栈和队列的核心概念与操作更重要的是我们从底层存储视角剖析了数组与链表这两种实现方式的内在权衡➤数组的优势在于缓存命中率高和随机访问但扩容和搬移元素是它的代价。因此数组适合操作集中于末尾(比如栈)的场景而在队列中需要额外设计来避免搬移元素(循环队列)。➤链表的优势在于动态伸缩和无需搬移元素但代价是指针占用额外空间和缓存命中率低。链表适合两端操作频繁的队列而在实现栈中并非最优解。四、练习推荐以下LeetCode题目20. 有效的括号 链接link.225. 用队列实现栈 链接link.232. 用栈实现队列 链接link.⚛️EL PSY CONGROO十分感谢你的阅读本期不确定推荐的练习题是否充足是否“高效” 深入栈与队列的概念和底层结构实现（数组 vs 链表）
博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub数据结构专栏路漫漫其修远兮吾将上下而求索文章目录前言栈专题一、概念二、代码实现准备头文件内容总览初始化判断空间容量添加入栈删除出栈获取栈顶元素判断是否为空获取元素个数销毁栈一份测试代码总结队列专题一、概念二、代码实现头文件内容总览初始化添加入队删除出队获取队头数据获取队尾数据判断是否为空获取元素个数销毁队列一份测试代码总结三、四种实现的全面对比方向选择对比表格整体总结四、练习前言——栈和队列是计算机科学中最基础、最常用的两种抽象数据类型。几乎每个程序员都能随口说出“栈是后进先出LIFO队列是先进先出FIFO”但在实际工程中选择数组还是链表作为底层容器会显著影响性能、内存占用和代码复杂度。本期将使用C语言实现栈和队列其主要内容包括1.使用头文件声明、源文件定义的形式呈现源码2.介绍栈与队列的概念并使用数组实现栈链表实现队列3.提供图例和使用链表实现栈数组实现队列的对比表格栈专题一、概念——栈是一种操作受限的线性表只允许在固定一端进行插入和删除数据操作进行插入和删除操作的一端称为栈顶另一端称为栈底栈中的数据遵循后进先出原则(LIFO:List In First Out)栈的插入操作被称为进栈入栈压栈在栈顶插入栈的删除操作被称为出栈在栈顶删除生活中的实例空羽毛球桶第一个被放入的羽毛球最后一个被取出最后一个被放入的羽毛球第一个被取出(在不暴力拆除桶底的情况下(▽))注说了这么多但总结来看数据结构栈的本质还是数组只是操作受限数据结构栈的物理结构和逻辑结构示例图二、代码实现准备前置知识assert()函数介绍C语言标准库中的调试宏用于在程序运行时检查条件是否成立。若条件为假0则输出错误信息文件、行号、表达式并调用 abort()终止程序若条件为真非0则无动作。常用于捕捉“不可能发生”的逻辑错误、验证函数前置条件等perror()函数介绍C 语言标准库函数用于打印错误信息。调用格式perror(“前缀字符串”)输出格式为“前缀字符串错误原因\n”常用于系统调用或库函数失败后快速定位错误原因exit()函数介绍C 语言标准库函数用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统0or EXIT_SUCCESS表示成功-1or EXIT_FAILURE表示失败布尔值C语言并不自带布尔值作为内置数据类型使用需引入标准库stdbool.h头文件内容总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintSTDataType;#栈typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;#初始化栈voidSTInit(ST*pst);#添加入栈voidSTPush(ST*pst,STDataType x);#删除出栈voidSTPop(ST*pst);#获取栈顶元素 STDataTypeSTTop(ST*pst);#判断是否为空 boolSTEmpty(ST*pst);#获取元素个数intSTSize(ST*pst);#销毁栈voidSTDestroy(ST*pst);栈的属性有使用动态开辟的数组 arr用于指向栈顶的指针 top 和用于存储数组当前容量的 capacity。栈从逻辑上操作受限因此除基础的初始化和销毁外只能从栈顶入栈和出栈不能在指定位置插入或删除元素也只能获取当前栈顶的元素。除此之外还有两个判断栈信息的函数用于确定栈是否为空以及返回当前栈内的元素个数初始化voidSTInit(ST*pst){assert(pst);pst-arrNULL;pst-top0;pst-capacity0;}传入栈并断言传入的指针不为 NULL关于 top 的初始化有一个重要的点涉及到后续操作的逻辑控制如果 top 指向栈顶则需将 top 初始化为 -1如果初始化为零会出现 top 为零时无法判断当前栈中是否还有元素的问题。如果 top 指向栈顶元素的下一个位置就将其初始化为零这种写法便于判满、入栈和返回元素个数判断空间容量voidSTCheckCapacity(ST*pst){if(pst-toppst-capacity){intnewcapacity(pst-capacity0?4:pst-capacity*2);STDataType*tmp(STDataType*)realloc(pst-arr,newcapacity*sizeof(STDataType));if(tmpNULL){perror(realloc fail);exit(1);}pst-arrtmp;pst-capacitynewcapacity;}}当 top 等于 capacity 时需动态扩容当第一次扩容时初始化容量为4否则扩容为当前容量的二倍扩容后需判断是否扩容成功失败返回提示信息后退出程序成功时再执行更新操作添加入栈voidSTPush(ST*pst,STDataType x){assert(pst);STCheckCapacity(pst);#入栈 pst-arr[pst-top]x;}传入栈与要添加的元素断言传入指针不为 NULL判断容量与顺序表相同在数组尾插数据并让 top删除出栈voidSTPop(ST*pst){assert(pstpst-top);#出栈 pst-top--;}传入栈断言传入指针不为 NULL 且栈中元素个数不为0与顺序表相同使 top-- 就能达到逻辑删除获取栈顶元素STDataTypeSTTop(ST*pst){assert(pstpst-top);#获取栈顶元素returnpst-arr[pst-top-1];}传入栈断言传入指针不为 NULL 且栈中元素个数不为0top 指向栈顶的下一个位置可以利用 top - 1 找到并返回栈顶元素判断是否为空boolSTEmpty(ST*pst){assert(pst);#判断是否为空returnpst-top0;}传入栈断言传入指针不为 NULL在数组中能根据每个元素的下标位置确定在这个元素前还有几个元素例如下标为3的元素它的前面就刚好有3个值所以我们同样可以根据 top 是否指向栈底判断栈是否为空为空返回 true否则返回 false获取元素个数intSTSize(ST*pst){assert(pst);#获取元素个数returnpst-top;}传入栈断言传入指针不为 NULL同上top 指向栈顶元素的下一个位置因此就为当前栈中的元素个数销毁栈voidSTDestroy(ST*pst){assert(pst);free(pst-arr);pst-arrNULL;pst-toppst-capacity0;}传入栈断言传入指针不为 NULL释放栈在堆区开辟的动态空间并将指针初始化初始化 top 和容量一份测试代码voidTest_Stack(){ST s;#初始化测试STInit(s);#入栈测试STPush(s,4);STPush(s,3);STPush(s,2);STPush(s,1);#出栈测试STPop(s);STPop(s);#获取栈顶元素测试printf(%d\n,STTop(s));#判断是否为空测试printf(%d\n,STEmpty(s));#获取元素个数测试printf(%d\n,STSize(s));#销毁测试STDestroy(s);}总结数组实现栈的优缺点维度分析时间复杂度所有操作均为O(1)空间复杂度O(N)但存在一定的容量预留可能导致空间浪费缓存命中率极好连续内存CPU 预加载效率高扩容成本动态扩容时需复制整个数组单次操作 O(N)但均摊后很低适用场景频繁压栈弹栈、对速度要求极高、元素数量可预估的场景队列专题一、概念——队列也是一种操作受限的线性表只允许在固定一端进行插入数据操作另一端进行删除数据操作插入数据的一端称为队尾删除数据的一端称为队头队列中的数据遵循先进先出的原则(FIFO:First In First Out)队列的插入操作被称为入队在队尾插入队列的删除操作被称为出队在队头删除生活中的实例排队购买先来的人先买到票后从队头离开后来的人排在队尾等待整个流程有序进行(没有人插队的情况)数据结构队列的物理结构和逻辑结构示例图二、代码实现头文件内容总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintQDataType;#定义队列的节点结构typedefstructQueueNode{QDataType data;#存储值structQueueNode*next;#指向下一个节点的指针}QNode;#定义存储队列信息的结构typedefstructQueue{QNode*phead;#指向队头的指针 QNode*ptail;#指向队尾的指针intsize;#当前的元素个数}Queue;#初始化队列voidQueueInit(Queue*pq);#添加入队voidQNodePush(Queue*pq,QDataType x);#删除出队voidQNodePop(Queue*pq);#获取队头数据 QDataTypeQueueFront(Queue*pq);#获取队尾数据 QDataTypeQueueBack(Queue*pq);#判断是否为空 boolQueueEmpty(Queue*pq);#获取元素个数intQSize(Queue*pq);#销毁队列voidQueueDestroy(Queue*pq);从代码看队列无疑多用了一个结构体用于实现完整结构该结构的作用在于明确队头和队尾在物理存储结构中的位置使我们无需考虑操作物理结构链表时执行的额外操作只需将重点放在对队列的操作逻辑上。与此同时我们注意到队列中有一个名为 QSize 的函数用于获取当前队列中的元素个数我们知道统计整条链表的元素个数需要完整遍历获得单次操作的时间复杂度为O(N)为高效可以在 Queue 结构体中额外维护一个变量 size 用于记录队列中的元素个数使 QSize 函数的时间复杂度优化为O(1)初始化voidQueueInit(Queue*pq){assert(pq);pq-pheadpq-ptailNULL;pq-size0;}传入队列并断言传入的指针不为 NULL当前队列中无节点因此将队头指针和队尾指针都置空并使 size 初始化为0添加入队voidQNodePush(Queue*pq,QDataType x){QNode*newnode(QNode*)malloc(sizeof(QNode));if(newnodeNULL){perror(malloc fail);return;}newnode-datax;newnode-nextNULL;#入队if(pq-ptailNULL){pq-pheadpq-ptailnewnode;}else{pq-ptail-nextnewnode;pq-ptailnewnode;}pq-size;}传入队列与要添加的元素断言传入指针不为 NULL创建新节点分为两种情况当队列中无任何元素时应该将队头指针与队尾指针同时指向入队节点否则就使当前队尾元素的 next 指向入队节点后修改队尾指针删除出队voidQNodePop(Queue*pq){assert(pqpq-size);#出队 #队列元素为1时删除导致队尾指针为野指针 QNode*nextpq-phead-next;free(pq-phead);if(nextNULL)pq-pheadpq-ptailnext;elsepq-pheadnext;pq-size--;}传入队列断言传入指针不为 NULL 且队列元素个数不为0分为队列元素个数为1和不为1两种情况为1时在销毁队头指针指向的节点后需同时修改头尾指针指向为 NULL不为1时只修改队头指针指向获取队头数据QDataTypeQueueFront(Queue*pq){assert(pqpq-size);#获取队头数据returnpq-phead-data;}传入队列断言传入指针不为 NULL 且队列元素个数不为0直接通过队头指针返回第一个元素获取队尾数据QDataTypeQueueBack(Queue*pq){assert(pqpq-size);#获取队尾数据returnpq-ptail-data;}传入队列断言传入指针不为 NULL 且队列元素个数不为0通过队尾指针返回最后一个元素判断是否为空boolQueueEmpty(Queue*pq){assert(pq);#判断是否为空returnpq-size0;}传入队列断言传入指针不为 NULL通过维护的变量 size 判断为空返回 true非空返回 false获取元素个数intQSize(Queue*pq){assert(pq);#获取元素个数returnpq-size;}传入队列断言传入指针不为 NULLpass销毁队列voidQueueDestroy(Queue*pq){assert(pq);QNode*curpq-phead;while(cur){QNode*nextcur-next;free(cur);curnext;}pq-pheadpq-ptailNULL;pq-size0;}传入队列断言传入指针不为 NULL与销毁链表的流程大致相同注意需初始化头尾指针和 size 变量一份测试代码voidTest_Queue(){Queue q;#初始化测试QueueInit(q);#入队测试QNodePush(q,1);QNodePush(q,2);QNodePush(q,3);QNodePush(q,4);#出队测试QNodePop(q);QNodePop(q);#获取队头数据测试printf(%d\n,QueueFront(q));#获取队尾数据测试printf(%d\n,QueueBack(q));#判断是否为空测试printf(%d\n,QueueEmpty(q));#获取元素个数测试printf(%d\n,QSize(q));#销毁队列测试QueueDestroy(q);}总结链表实现队列的优缺点维度分析时间复杂度所有操作均为 O(1)空间复杂度O(N)每个元素额外存储一个指针变量64 位系统下 8 字节缓存命中率较差节点在堆中分散分配跳跃访问导致缓存未命中扩容成本无需扩容动态增长无一次性复制开销适用场景元素数量动态变化大、无法预估容量、频繁入队出队且对内存分配不敏感的场景三、四种实现的全面对比方向选择我们换位思考先看链表实现栈的场景如果用表头做栈底表尾做栈顶则每次返回栈顶数据都需遍历链表操作的时间复杂度为O(N)。如果用表头做栈顶表尾做栈底则时间复杂度不变再看数组实现队列的场景使用高下标位的方向作为队头低下标位的方向作为队尾时执行入队操作时需整体右移元素时间复杂度为O(N)。使用高下标位的方向作为队尾低下标位的方向作为队头时执行出队操作时需整体左移元素时间复杂度为O(N)。如果两种操作均不移动元素在使用数组实现队列时会出现假溢出问题导致浪费空间越来越多由此关于栈顶、栈底、队头、队尾方向的选择问题便有了大致的概念对比表格为了更清晰地看到 数组 vs 链表 在栈和队列上的差异下表从多个维度做了详细对比对比维度数组实现栈链表实现栈链表实现队列数组实现队列底层结构连续内存数组单向链表头插/头删单向链表头删/尾插连续内存数组 头尾指针核心操作入栈、出栈在数组末尾入栈、出栈在链表头部入队在尾部出队在头部入队在尾部出队在头部最坏时间复杂度入栈扩容时 O(N)始终 O(1)始终 O(1)入队扩容时 O(N)需要搬移元素 O(N)空间占用容量可能大于实际元素数浪费空间每个元素多一个指针额外空间开销大每个元素多一个指针额外空间开销大容量可能浪费但无指针开销缓存命中率极好顺序访问差节点分散差节点分散极好顺序访问是否需要动态扩容需要有复制成本不需要动态分配节点不需要动态分配节点需要有复制成本空栈/空队列判断top 0head NULLsize 0front rear典型应用场景函数调用栈、表达式求值浏览器历史可双向消息队列、BFS 队列任务队列但实际多用链表——数组天生适合栈因为栈的操作只在一端进行数组的末尾操作O(1)且缓存命中率高扩容成本均摊后微乎其微。链表天生适合队列因为队列要在两端操作链表的头删尾插均为O(1)且无需搬移元素动态增长无容量限制。整体总结通过本文你不仅掌握了栈和队列的核心概念与操作更重要的是我们从底层存储视角剖析了数组与链表这两种实现方式的内在权衡➤数组的优势在于缓存命中率高和随机访问但扩容和搬移元素是它的代价。因此数组适合操作集中于末尾(比如栈)的场景而在队列中需要额外设计来避免搬移元素(循环队列)。➤链表的优势在于动态伸缩和无需搬移元素但代价是指针占用额外空间和缓存命中率低。链表适合两端操作频繁的队列而在实现栈中并非最优解。四、练习推荐以下LeetCode题目20. 有效的括号 链接link.225. 用队列实现栈 链接link.232. 用栈实现队列 链接link.⚛️EL PSY CONGROO十分感谢你的阅读本期不确定推荐的练习题是否充足是否“高效”