C语言：单链表与栈队列实现

前言：

本文基于指针与动态内存管理核心知识点，系统讲解C语言三大基础数据结构。内容涵盖结构定义、核心操作实现及高频面试真题解析，所有代码严格遵循笔试规范，注重边界条件处理和内存安全。作为嵌入式及C/C++岗位笔试第二大高频考点，本专题既适合零基础入门，也适用于知识点巩固与校招/社招面试冲刺复习。

一、单链表全解

链表是线性表的链式存储结构，通过指针将离散的内存节点串联起来，解决了数组插入删除效率低、大小固定的痛点，是指针与动态内存最经典的落地场景。

1. 链表 vs 数组核心对比

2. 节点定义

#include <stdio.h> #include <stdlib.h> #include <assert.h> // 单链表节点结构 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; // 数据域 struct SListNode* next; // 指针域，指向下一个节点 } SListNode;

3. 核心操作手撕实现

① 创建新节点

// 创建一个值为x的新节点 SListNode* BuySListNode(SLTDataType x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); if (newNode == NULL) { perror("malloc failed"); exit(-1); } newNode->data = x; newNode->next = NULL; return newNode; }

② 尾插法：末尾插入节点

// 在链表尾部插入值为x的节点 void SListPushBack(SListNode** pphead, SLTDataType x) { assert(pphead != NULL); SListNode* newNode = BuySListNode(x); // 空链表：直接让头指针指向新节点 if (*pphead == NULL) { *pphead = newNode; return; } // 非空：找到尾节点 SListNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newNode; }

注意：修改头指针必须传二级指针，否则只是修改形参副本。

③ 头插法：头部插入节点

// 在链表头部插入值为x的节点 void SListPushFront(SListNode** pphead, SLTDataType x) { assert(pphead != NULL); SListNode* newNode = BuySListNode(x); // 新节点指向原头，头指针更新为新节点 newNode->next = *pphead; *pphead = newNode; }

④ 尾删法：删除尾节点

// 删除链表最后一个节点 void SListPopBack(SListNode** pphead) { assert(pphead != NULL); assert(*pphead != NULL); // 空链表不能删 // 只有一个节点：直接释放，头置空 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } // 多个节点：找到倒数第二个节点 SListNode* prev = *pphead; while (prev->next->next != NULL) { prev = prev->next; } free(prev->next); prev->next = NULL; }

⑤ 头删法：删除头节点

// 删除链表第一个节点 void SListPopFront(SListNode** pphead) { assert(pphead != NULL); assert(*pphead != NULL); SListNode* del = *pphead; *pphead = del->next; // 头指针移到下一个 free(del); }

⑥ 查找节点

// 查找值为x的节点，找到返回节点地址，找不到返回NULL SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }

⑦ 指定位置后插入

// 在pos节点之后插入值为x的节点 void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos != NULL); SListNode* newNode = BuySListNode(x); newNode->next = pos->next; pos->next = newNode; }

⑧ 销毁整个链表

// 销毁链表，释放所有节点 void SListDestroy(SListNode** pphead) { assert(pphead != NULL); SListNode* cur = *pphead; while (cur != NULL) { SListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }

二、栈的实现与应用

栈是一种 ** 后进先出（LIFO）** 的线性表，只能在栈顶进行插入和删除操作，是算法题中最常用的数据结构之一。

1. 顺序栈（数组实现）

数组实现的栈缓存友好、访问效率高，是工业界主流实现方式。

结构定义

typedef int STDataType; typedef struct Stack { STDataType* a; // 动态数组 int top; // 栈顶位置，指向栈顶元素的下一个位置 int capacity; // 栈容量 } Stack;

初始化与销毁

// 初始化栈 void StackInit(Stack* ps) { assert(ps != NULL); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { perror("malloc failed"); exit(-1); } ps->top = 0; ps->capacity = 4; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps != NULL); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }

入栈与扩容

// 元素入栈 void StackPush(Stack* ps, STDataType x) { assert(ps != NULL); // 满了则扩容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc failed"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; }

出栈与取栈顶

// 栈顶元素出栈 void StackPop(Stack* ps) { assert(ps != NULL); assert(ps->top > 0); // 空栈不能删 ps->top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps != NULL); assert(ps->top > 0); return ps->a[ps->top - 1]; } // 判断栈是否为空 int StackEmpty(Stack* ps) { assert(ps != NULL); return ps->top == 0; }

2. 链栈（链表实现）

用链表头作为栈顶，头插头删模拟入栈出栈，优点是无容量限制，缺点是每个节点有指针开销，缓存性差。

面试中优先写数组实现，更简洁高效，符合常规考察方向。

三、队列的实现与应用

队列是一种先进先出（FIFO）的线性表，只能在队尾插入、队头删除，常用于任务调度、消息缓冲等场景。

1. 循环队列（数组实现）

数组实现队列如果直接用头尾指针，出队后前面的空间会浪费，因此采用循环队列复用空间，是面试核心考点。

核心难点：判空与判满

循环队列头尾重合时，无法区分是空还是满，主流两种解决方案：

1. 牺牲一个存储单元：约定尾指针下一个是头指针时为满（最常用，面试首选）
2. 增加 size 计数变量：额外维护元素个数，空时 size=0，满时 size = 容量

结构定义（牺牲一个单元方案）

typedef int QDataType; typedef struct CircularQueue { QDataType* a; int front; // 队头下标 int rear; // 队尾下标，指向队尾元素的下一个位置 int capacity; // 总容量（实际有效元素数为capacity-1） } CQueue;

初始化

// 初始化循环队列，k为有效元素最大个数 void CQueueInit(CQueue* q, int k) { assert(q != NULL); // 多开一个空间用于区分空满 q->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1)); q->front = q->rear = 0; q->capacity = k + 1; }

入队与判满

// 入队，成功返回1，满了返回0 int CQueueEnQueue(CQueue* q, QDataType x) { assert(q != NULL); if ((q->rear + 1) % q->capacity == q->front) { return 0; // 队列已满 } q->a[q->rear] = x; q->rear = (q->rear + 1) % q->capacity; return 1; }

出队与判空

// 出队，成功返回1，空队列返回0 int CQueueDeQueue(CQueue* q) { assert(q != NULL); if (q->front == q->rear) { return 0; // 队列为空 } q->front = (q->front + 1) % q->capacity; return 1; } // 获取队头元素 QDataType CQueueFront(CQueue* q) { assert(q != NULL); assert(q->front != q->rear); return q->a[q->front]; } // 判断队列是否为空 int CQueueIsEmpty(CQueue* q) { assert(q != NULL); return q->front == q->rear; }

2. 链队列（链表实现）

用链表头尾分别作为队头队尾，尾插头删，适合元素数量不确定的场景，实现简单但缓存效率低。

四、高频面试手撕真题

1. 反转单链表（笔试 100% 高频）

题目：给你单链表的头节点，反转该链表并返回反转后的头节点。

思路：三指针迭代法，逐个改变节点指向。

struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev = NULL; struct ListNode* cur = head; while (cur != NULL) { struct ListNode* next = cur->next; // 保存下一个节点 cur->next = prev; // 反转当前节点指向 prev = cur; // prev后移 cur = next; // cur后移 } return prev; // prev最终成为新头 }

2. 链表判环（快慢指针经典题）

题目：判断链表中是否有环。

思路：快慢指针，快指针每次走两步，慢指针每次走一步，有环则一定会相遇。

bool hasCycle(struct ListNode *head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; }

3. 有效的括号（栈经典应用）

题目：给定一个只包含括号的字符串，判断括号是否有效闭合。

思路：左括号入栈，遇到右括号则匹配栈顶，不匹配或栈空则无效，最后栈空则有效。

bool isValid(char * s) { Stack st; StackInit(&st); for (int i = 0; s[i] != '\0'; i++) { // 左括号入栈 if (s[i] == '(' || s[i] == '[' || s[i] == '{') { StackPush(&st, s[i]); } else { // 右括号时栈空，无效 if (StackEmpty(&st)) { StackDestroy(&st); return false; } char top = StackTop(&st); StackPop(&st); // 匹配校验 if ((s[i] == ')' && top != '(') || (s[i] == ']' && top != '[') || (s[i] == '}' && top != '{')) { StackDestroy(&st); return false; } } } // 最后栈必须为空 bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }

4. 用栈实现队列

题目：用两个栈实现一个队列，支持入队、出队、取队头、判空。

思路：一个栈负责入队，一个栈负责出队；出队栈空时，把入队栈全部倒入出队栈，顺序就反转成了队列顺序。

typedef struct { Stack pushSt; // 入队栈 Stack popSt; // 出队栈 } MyQueue; void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushSt, x); } int myQueuePop(MyQueue* obj) { // 出队栈空了，把入队栈全部倒过来 if (StackEmpty(&obj->popSt)) { while (!StackEmpty(&obj->pushSt)) { StackPush(&obj->popSt, StackTop(&obj->pushSt)); StackPop(&obj->pushSt); } } int ret = StackTop(&obj->popSt); StackPop(&obj->popSt); return ret; }

五、面试高频考点与易错坑点

1. 经典面试问答

Q1：数组和链表有什么区别？各自的适用场景？

答：

1. 内存分布：数组是连续内存，链表是离散节点通过指针连接
2. 访问效率：数组支持 O (1) 随机访问，链表必须遍历 O (n)
3. 增删效率：数组中间增删需移动元素 O (n)，链表已知位置时增删 O (1)
4. 空间扩容：数组大小固定，扩容有开销；链表动态增减，按需分配 适用场景：数据量固定、频繁随机访问选数组；频繁增删、数据量不确定选链表。

Q2：栈和队列有什么区别？各有什么典型应用？

答： 栈是后进先出，队列是先进先出。 栈的典型应用：括号匹配、表达式求值、函数调用栈、递归转迭代； 队列的典型应用：任务调度、消息缓冲、广度优先搜索、生产者消费者模型。

Q3：循环队列为什么要牺牲一个单元？还有其他方案吗？

答： 因为循环队列中头尾指针重合时，无法区分队列是空还是满。 牺牲一个存储单元是最常用的方案：约定 rear 下一个位置是 front 时为满，空时则是 rear==front，以此区分两种状态。 其他方案：额外增加一个 size 变量记录元素个数，空时 size=0，满时 size 等于容量，逻辑更直观但多一个变量开销。

Q4：单链表为什么常用二级指针传参？什么时候需要二级指针？

答： 当我们需要修改链表的头指针本身时（比如头插、头删、空链表插入第一个节点），就必须传头指针的地址也就是二级指针。 因为 C 语言传参是传值，直接传头指针只是传了一份副本，函数内修改副本不会影响外面的头指针。如果只是遍历、修改节点数据，不修改头指针，传一级指针即可。

Q5：反转链表有哪些方法？迭代法的核心思路是什么？

答： 主要有迭代法和递归法两种，面试优先写迭代法，更直观无栈溢出风险。 迭代法核心是三指针：prev 记录前一个节点，cur 记录当前节点，next 保存下一个节点；遍历过程中逐个将 cur 的 next 指向 prev，同时三个指针同步后移，最终 prev 成为新的头节点。

2. 常见易错坑点

1. 空链表不判空：删除、查找操作前不判断链表是否为空，直接解引用空指针崩溃
2. 尾删漏处理单节点：只处理多节点情况，只剩一个节点时尾删会出现野指针
3. 修改头指针不传二级指针：头插头删只传一级指针，导致外面头指针没变化
4. 循环队列取模遗漏：头尾指针移动忘记取模，导致数组越界
5. 链表销毁只释放头节点：只 free 头节点，其余节点全部泄漏，必须遍历逐个释放
6. 插入节点顺序错误：先断开原链接再赋值新节点 next，导致后续节点地址丢失

以上就是单链表、栈、队列的全部核心内容，是数据结构的入门基础，也是笔试手撕代码的高频必考题，建议结合代码手动实现，重点掌握边界条件处理与底层逻辑。

---

制作不易，如果对你有用，希望能点赞收藏支持一下。