数据结构（四）内核链表、栈与队列

一、内核链表基础

1. 什么是 Linux 内核链表？

Linux 内核链表是一种高效的 双向循环链表，广泛应用于内核模块开发中，用于管理数据结构。每个节点通过指针连接前一个和后一个元素，实现插入和删除的高性能。

2. 链表的定义与初始化

在 Linux 内核中，链表的实现依赖于 struct list_head 结构体，定义在头文件 <linux/list.h> 中：

struct list_head {
struct list_head *next, *prev;
};

为了在自定义结构体中集成链表，只需在结构体中包含 list_head 成员即可：

struct my_data {
int value;
struct list_head list;
}

链表初始化使用如下宏：

LIST_HEAD(my_list); // 静态初始化
// 或者
INIT_LIST_HEAD(&my_list); // 动态初始化

这两种方式都将 list.next 和 list.prev 指向自身，构成一个空的循环链表。

注意：内核链表已经将增删查改封装好了，开发者只需要聚焦于数据部分。

3. 内核链表设计思想

• 普通链表将数据和节点结构紧耦合。

• 内核链表则通过将链表节点作为结构体中的一个字段，从而实现结构体与链表解耦。

常用宏如下：

• offsetof()：用于计算某个成员在结构体中的偏移量。

• container_of()：用于通过结构体成员地址获取整个结构体指针。

#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))

4. 常用链表操作宏与函数

5. 使用链表需注意的要点

• 内存管理：新增节点前需手动分配内存；删除节点后应释放。

• 线程安全：多线程环境下需加锁。

• 性能考量：链表适合插入/删除频繁场景，但查找效率低。

二、栈（Stack）

1. 基本定义

栈是一种 只允许在一端（栈顶）进行插入和删除操作 的线性结构，遵循 后进先出（LIFO） 原则。

在 C 语言中，我们通常用动态内存（堆区）来实现线性栈结构。

2. 结构特点

• 栈顶（top）：允许插入/删除的一端。

• 栈底（bottom）：固定不动的一端。

• 空栈：栈中无任何数据元素。

3. 栈的类型

• 满增栈：栈满时从低地址向高地址增长。

• 空减栈：从高地址向低地址扩展。

• 实际实现时通常选择一种逻辑来处理栈顶移动。

📌 示例说明：

栈空间从底部开始增长，压栈操作使 top++，出栈使 top--。如果 top 达到容量限制，表示栈已满。

4. 栈的应用场景

• 递归求解 / 回溯问题

• 表达式求值（符号优先级）

• 函数调用管理（程序栈帧）

5. 栈的基本操作代码

#include <stdio.h>
#include "stack.h"
#include <stdlib.h>Stack *creatStack()
{Stack *pstack = malloc(sizeof(Stack));if(pstack == NULL){printf("malloc error\n");return NULL;}pstack->ptop = NULL;pstack->clen = 0;return pstack;
}int IsEmptyStack(Stack *pstack)
{return NULL == pstack->ptop;
}
int pushStack(Stack *pstack, DataType data)
{StNode *pnode = malloc(sizeof(StNode));if(NULL == pnode){printf("malloc error\n");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = pstack->ptop;pstack->ptop = pnode;pstack->clen++;return 1;
}/*** @brief 出栈，且出栈之前保存栈顶的元素，通过主函数定义的dadatype类型返回改后的数值* * @param pstack 栈头指针* @param data 返回的栈顶元素的值* @return int 成功出栈返回1，失败为0*/
int popStack(Stack *pstack, DataType *data)
{if(IsEmptyStack(pstack)){return -1;}StNode *temp = pstack->ptop;*data = temp->data;pstack->ptop = temp->pnext;free(temp);pstack->clen--;return 1;
}/*** @brief Get the Stack Top object* * @param pstack * @param data * @return int */
int getStackTop(Stack *pstack, DataType *data)
{if(IsEmptyStack(pstack)){return -1;}*data = pstack->ptop->data;return 1;
}void printStack(Stack *pstack)
{if(IsEmptyStack(pstack)){return ;}StNode *temp = pstack->ptop;while(temp){printf("%d ", temp->data);temp = temp->pnext;}puts("");return ;
}void destroyStack(Stack **pstack)
{StNode *temp = (*pstack)->ptop;while(temp){(*pstack)->ptop = temp->pnext;free(temp);temp = (*pstack)->ptop;}free(*pstack);*pstack = NULL;
}

三、队列（Queue）

1. 基本定义

队列是一种**先进先出（FIFO）**的数据结构，特点是：

• 从 队尾（tail） 进入数据

• 从 队头（head） 移除数据

2. 队列的应用场景

• 缓冲区管理

• 数据包调度

• 多任务之间的通信机制

3. 循环队列（环形队列）

为避免频繁移动数据，可将队列逻辑设计为循环结构。即：利用数组，头尾指针移动时利用求余操作形成环形效果。

next = (tail + 1) % MAX_LEN;

判断条件：

4. 队列的类型

• 顺序队列（数组实现）

• 链式队列（链表实现，扩展性强）

5. 链表型队列的代码

#include <stdio.h>
#include "linkqueue.h"
#include <stdlib.h>LQueue *creatQLink()
{LQueue *plink = malloc(sizeof(LQueue));if(NULL == plink){fprintf(stderr, "malloc error\n");return NULL;}plink->phead = NULL;plink->ptail = NULL;plink->clen = 0;return plink;
}int isEmptyLQueue(LQueue *plink)
{return NULL == plink->phead;
}int pushLQueue(LQueue *plink, DataType data)
{LQNode *pnode = malloc(sizeof(LQNode));if(pnode == NULL){fprintf(stderr, "malloc error\n");return -1;}pnode->data = data;pnode->pnext = NULL;if(isEmptyLQueue(plink)){plink->phead = pnode;plink->ptail = pnode;plink->clen++;}else{plink->ptail->pnext = pnode;plink->ptail = pnode;plink->clen++;}return 0;
}int popLQueue(LQueue *plink)
{if(isEmptyLQueue(plink)){fprintf(stderr,"is empty lqueue\n");return -1;}LQNode *temp = plink->phead;plink->phead = temp->pnext;if(NULL == temp->pnext){plink->ptail = NULL;}free(temp);plink->clen--;return 0;
}LQNode* getLQueueHeadNode(LQueue *plink)
{if(isEmptyLQueue(plink)){fprintf(stderr, "empty Lqueue\n");return NULL;}return plink->phead;
}void printLQueue(LQueue *plink)
{if(isEmptyLQueue(plink)){fprintf(stderr, "empty lqueue\n");return ;}LQNode *temp = plink->phead;while(temp){printf("%d ", temp->data);temp = temp->pnext;}puts("");return ;
}void destroyLQueue(LQueue **plink)
{LQNode *temp = (*plink)->phead;while(temp){(*plink)->phead = temp->pnext;free(temp);temp = (*plink)->phead;}free(*plink);*plink = NULL;return ;
}