2025年对于一个头指针为head的带头结点（对于一个设有头指针和尾指针的单链表）

大家好，我是讯享网，很高兴认识大家。

1.1 带头双向循环链表

1.1.1 什么是带头双向循环链表

讯享网

带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”，头结点可以是任意的值。

由图我们可知道，带头：由头结点即哨兵位；双向：前一个结点可以指向后一个结点，后一个结点可以找到前一个结点；循环：形成一个闭合的环，头结点指向尾节点，尾节点指向头结点。

1.1.2 双向链表的定义

我们需要定义两个指针且需要指向结构体，一个指向结点的前一个结点，一个指向结点的后一个结点，还需要保存我们需要的值：

讯享网

我们定义后再typedef，重新定义一个结构体名字，我们使用该结构体时就不用再加struct了。

1.1.3 双向链表的功能

在我们学习了单链表，我们知道链表是用来储存的，双向链表也一样，我们需要对链表进行增删查改等功能的实现：

讯享网

我们需要这些功能。

1.1.4 功能的实现

1.1.4.1 链表的初始化

我们使用链表，前提是我们需要有一个链表：

1.1.4.2 链表的尾插

在进行插入时，我们都需要申请一块空间来存我们的结构体，所以再进行插入实现之前，我们封装一个函数来申请空间：

讯享网

封装函数可以更清晰的知道我们代码是用来干什么的。

在进行尾插之前，我们需要知道插入式改变了哪个结点的指针的指向。

由图可以知道，我们需要改变新节点的指针和原来链表头结点的前一个结点（d3）的指针的指向，我们可以得到该尾插：

1.1.4.3 链表的头插

进行头插前，我们也需要知道进行头插的时候，我们要改变哪些指针的指向：

在我们头插的时候，是在头结点的后面进行头插，头结点也是哨兵位不能改变。由图可知，我们需要改变新节点（d4）的指针指向和头结点以及原来头结点的下一个节点（d1）结点的指针指向

讯享网

1.1.4.4 链表的尾删

在进行尾删前，我们需要判断该链表除了头结点以外还有没有新的结点，尾删不能删除空链表，进行判空：

为空返回true，不为空返回false，再进行尾删的操作：

我们需要改变头结点指针的指向和头结点前一个节点指针的指向

讯享网

1.1.4.5 链表的头删

头删是删除头结点下一个的结点：

我们需要改变头结点指针的指向以及需要删除结点的下一个结点指针的指向

1.1.4.6 指定位置的插入

在指定位置插入的时候，我们需要改变指定位置节点前后指针的指向：

讯享网

2. 数据结构–栈

2.1 什么是栈？

我们在学习函数的时候，就知道函数栈帧了，那这里的栈与函数栈帧中的栈是一个东西吗？很显然，这两者并不是同一种。

栈：⼀种特殊的线性表，其只允许在固定的⼀端进行插⼊和删除元素操作。进行数据插入和删除操作的⼀端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2.2 栈的底层实现逻辑

栈的实现⼀般可以使⽤数组或者链表实现，相对而言数组的结构实现更优⼀些。因为数组在尾上插入数据的代价比较小。

2.3 栈的实现

栈是先进后出的原则，需要栈顶与栈底以及所保存的数据类型，我们可以得知需要两个指针和一个变量来对栈进行实现

2.4 栈功能的实现

相对于链表，我们栈功能实现就比较简单，需要实现的功能也相对较少：

讯享网

2.4.1 栈的初始化

我们进行初始化时只需要把我们所创建的结构体内容重置为0；

2.4.2 栈的销毁

有栈的创建，就需要销毁

讯享网

2.4.3 入栈

2.4.4 出栈

在进行出栈的操作时，如果栈为空，就不能进行出栈的操作，所以我们需要先进行判断是否为空

讯享网

判空的操作：如果为空返回非零，不为空返回0。

出栈:我们只需要把栈顶-1，就可以把栈顶元素删除。

2.4.5 取栈顶元素

讯享网

2.4.6 获取栈中有效元素个数

获取栈中有效元素个数只需要把栈容量个数返回

3. 数据结构–队列

3.1 什么是队列？

概念：只允许在⼀端进行插⼊数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插⼊操作的⼀端称为队尾

出队列：进行删除操作的⼀端称为队头

3.2 队列底层实现逻辑

队列也可以数组和链表的结构实现，使用链表的结构实现更优⼀些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

3.3 队列的实现

队列的定义需要有两部分：队列结点与队列结构（队头队尾）。所以我们需要定义两个结构体来实现队列

讯享网

3.4 队列功能的实现

这是我们需要实现的队列功能。

3.4.1 队列初始化

讯享网

3.4.2 入队

3.4.3 出队

讯享网

3.4.4 判空

3.4.5 队列结点个数

讯享网

3.4.6 取队头元素

3.4.7 取队尾元素

讯享网

3.4.8 队列的销毁

续集下次更精彩！！！