文章目录前言一、线性表、栈、队列的核心区别二、栈Stack核心概念1. 核心特性2. 基础术语3. 栈的分类4. 两种实现方式三、顺序栈完整实现空增栈1. 头文件定义 seqstack.h2. 接口实现 seqstack.c3. 【顺序栈易错踩坑点】四、链式栈完整实现带头结点1. 头文件定义 linkstack2. 接口实现 linkstack.c3. 【链式栈易错踩坑点】五、队列Queue核心概念1. 核心特性2. 基础术语3. 两种实现方式六、链式队列完整实现带头结点1. 接口说明2. 完整实现代码七、经典排错案例free(): double free detected in tcache 21. 报错含义2. 常见触发场景3. 避坑规范八、学习总结前言数据结构学习进入第四天今天的核心内容是操作受限的线性表 —— 栈和队列。相比于可以在任意位置插入删除的普通线性表栈和队列仅允许在指定端点进行操作是算法与工程开发中非常基础且高频使用的数据结构。本文整理了栈的核心概念、顺序栈与链式栈的完整代码实现、队列基础概念与链式队列实现同时汇总了今天实操中踩过的经典坑点方便复盘和后续查阅。一、线性表、栈、队列的核心区别普通线性表可在任意位置进行插入、删除操作操作自由度最高。栈和队列仅允许在指定位置进行插入删除属于「操作受限」的特殊线性表操作规则固定应用场景针对性强。二、栈Stack核心概念1. 核心特性先进后出FILO, First In Last Out/ 后进先出LIFO, Last In First Out最后存入的元素最先被取出。2. 基础术语栈顶允许进行入栈、出栈操作的一端是所有操作的唯一入口出口。栈底不允许进行插入删除操作的一端位置固定不变。入栈压栈将元素存入栈顶位置的操作。出栈弹栈将元素从栈顶位置取出的操作。栈针指向当前可入栈位置 / 栈顶元素的标识用于标记栈的当前状态。3. 栈的分类按栈针指向与内存增长方向区分空栈模型栈针指向下一个可存放元素的空位入栈时先存数据再挪动栈针。满栈模型栈针指向当前栈顶元素的位置入栈时先挪动栈针再存数据。增栈栈向内存高地址方向增长。减栈栈向内存低地址方向增长。本次代码实现采用空增栈模型也是最常用、最易理解的实现方式。4. 两种实现方式顺序栈底层基于数组实现内存连续访问效率高容量固定。链式栈底层基于单链表实现内存离散容量无上限伴随指针额外开销。三、顺序栈完整实现空增栈1. 头文件定义seqstack.h#ifndef SEQSTACK_H #define SEQSTACK_H typedef int DataType; typedef struct { DataType *pData; // 指向数据区首地址 int tLen; // 栈的最大容量 int Top; // 栈针指向下一个可入栈的位置 } Stack_t; Stack_t *CreateSeqStack(int Len); int IsEmptySeqStack(Stack_t *pTmpStack); int IsFullSeqStack(Stack_t *pTmpStack); int PushSeqStack(Stack_t *pTmpStack, DataType TmpData); DataType PopSeqStack(Stack_t *pTmpStack); int DestroySeqStack(Stack_t **ppTmpStack); #endif2. 接口实现seqstack.c#include stdio.h #include seqstack.h #include string.h #include stdlib.h // 创建顺序栈Len为最大容量 Stack_t *CreateSeqStack(int Len) { if (Len 0) { printf(栈容量必须大于0!\n); return NULL; } Stack_t *pTmpStack malloc(sizeof(Stack_t)); if (NULL pTmpStack) { printf(malloc stack head failed!\n); return NULL; } pTmpStack-pData malloc(Len * sizeof(DataType)); if (NULL pTmpStack-pData) { printf(malloc stack data failed!\n); free(pTmpStack); // 分配失败释放头结点防止内存泄漏 return NULL; } pTmpStack-tLen Len; pTmpStack-Top 0; memset(pTmpStack-pData, 0, Len * sizeof(DataType)); return pTmpStack; } // 判断栈空返回1为空0为非空 int IsEmptySeqStack(Stack_t *pTmpStack) { if (NULL pTmpStack) return -1; return pTmpStack-Top 0 ? 1 : 0; } // 判断栈满返回1为满0为未满 int IsFullSeqStack(Stack_t *pTmpStack) { if (NULL pTmpStack) return -1; return pTmpStack-Top pTmpStack-tLen ? 1 : 0; } // 入栈成功返回0失败返回-1 int PushSeqStack(Stack_t *pTmpStack, DataType TmpData) { if (NULL pTmpStack) return -1; if (IsFullSeqStack(pTmpStack)) { printf(栈满无法入栈\n); return -1; } pTmpStack-pData[pTmpStack-Top] TmpData; pTmpStack-Top; return 0; } // 出栈返回弹出的元素栈空返回0接口保持原设计 DataType PopSeqStack(Stack_t *pTmpStack) { if (NULL pTmpStack) { printf(栈指针为空\n); return 0; } if (IsEmptySeqStack(pTmpStack)) { printf(栈空不能出栈!\n); return 0; } pTmpStack-Top--; return pTmpStack-pData[pTmpStack-Top]; } // 销毁栈二级指针释放后置空 int DestroySeqStack(Stack_t **ppTmpStack) { if (NULL ppTmpStack || NULL *ppTmpStack) return -1; if ((*ppTmpStack)-pData ! NULL) { free((*ppTmpStack)-pData); (*ppTmpStack)-pData NULL; } free(*ppTmpStack); *ppTmpStack NULL; return 0; }3. 【顺序栈易错踩坑点】判空逻辑错误误用最大容量tLen判断空栈正确逻辑是判断Top 0。入栈缺少判满栈满后继续入栈会造成数组越界触发内存非法访问。出栈逻辑冗余多余的 for 循环完全无意义空栈出栈无返回值会触发未定义行为。内存泄漏创建栈时数据区分配失败未释放已分配的头结点。空指针未防护所有接口未判断入参是否为 NULL传入空指针直接段错误。四、链式栈完整实现带头结点1. 头文件定义linkstack#ifndef LINKSTACK_H #define LINKSTACK_H typedef int DataType; typedef struct Node { DataType Data; struct Node *pNext; } Node_t; Node_t *CreateLinkStack(void); int IsEmptyLinkStack(Node_t *pTmpStack); int PushLinkStack(Node_t *pTmpStack, DataType TmpData); DataType PopLinkStack(Node_t *pTmpStack); int DestroyLinkStack(Node_t **ppTmpStack); #endif2. 接口实现linkstack.c#include stdio.h #include linkstack.h #include stdlib.h // 创建链式栈带头结点 Node_t *CreateLinkStack(void) { Node_t *pTmpStack malloc(sizeof(Node_t)); if (NULL pTmpStack) { printf(malloc failed!\n); return NULL; } pTmpStack-pNext NULL; return pTmpStack; } // 判断栈空返回1为空0为非空 int IsEmptyLinkStack(Node_t *pTmpStack) { if (NULL pTmpStack) return -1; return pTmpStack-pNext NULL ? 1 : 0; } // 入栈头插法栈顶为头结点后的第一个节点 int PushLinkStack(Node_t *pTmpStack, DataType TmpData) { if (NULL pTmpStack) return -1; Node_t *pTmpNode malloc(sizeof(Node_t)); if (NULL pTmpNode) { printf(malloc failed!\n); return -1; } pTmpNode-Data TmpData; pTmpNode-pNext pTmpStack-pNext; pTmpStack-pNext pTmpNode; return 0; } // 出栈头删法返回弹出的元素 DataType PopLinkStack(Node_t *pTmpStack) { if (NULL pTmpStack) { printf(栈头指针为空\n); return -1; } if (IsEmptyLinkStack(pTmpStack)) { printf(栈空无法出栈\n); return -1; } Node_t *pTmpNode pTmpStack-pNext; DataType TmpData pTmpNode-Data; pTmpStack-pNext pTmpNode-pNext; free(pTmpNode); return TmpData; } // 销毁链式栈 int DestroyLinkStack(Node_t **ppTmpStack) { if (NULL ppTmpStack || NULL *ppTmpStack) return -1; Node_t *pCur *ppTmpStack; Node_t *pDel NULL; while (pCur ! NULL) { pDel pCur; pCur pCur-pNext; free(pDel); } *ppTmpStack NULL; return 0; }3. 【链式栈易错踩坑点】入栈写成尾插直接覆盖头结点的 next 指针导致旧节点全部丢失、内存泄漏栈中永远只能保存 1 个元素。出栈判空传错指针用栈顶数据节点代替头结点判空逻辑完全错误。节点分配失败未返回malloc 失败后继续执行空指针访问直接触发段错误。链表结构混乱指针赋值顺序错误导致链表断裂、节点丢失。五、队列Queue核心概念1. 核心特性先进先出FIFO, First In First Out/ 后进后出最先存入的元素最先被取出。2. 基础术语队头允许进行出队操作的一端。队尾允许进行入队操作的一端。入队将元素插入到队尾位置的操作。出队将元素从队头位置取出的操作。3. 两种实现方式顺序循环队列底层基于数组实现通过取模运算实现空间循环复用解决假溢出问题。链式队列底层基于单链表实现容量灵活无上限适合数据量不确定的场景。六、链式队列完整实现带头结点1. 接口说明保持与链式栈一致的代码风格接口定义如下Node_t *CreateLinkQueue(void); int IsEmptyLinkQueue(Node_t *pTmpQueue); int EnterLinkQueue(Node_t *pTmpQueue, DataType TmpData); DataType QuitLinkQueue(Node_t *pTmpQueue); int DestroyLinkQueue(Node_t **ppTmpQueue);2. 完整实现代码可直接复用链式栈的linkstack.h结构体定义新建linkqueue.c即可#include stdio.h #include linkstack.h #include stdlib.h // 创建链式队列带头结点 Node_t *CreateLinkQueue(void) { Node_t *pTmpQueue malloc(sizeof(Node_t)); if (NULL pTmpQueue) { printf(malloc queue head failed!\n); return NULL; } pTmpQueue-pNext NULL; return pTmpQueue; } // 判断队空返回1为空0为非空 int IsEmptyLinkQueue(Node_t *pTmpQueue) { if (NULL pTmpQueue) return -1; return pTmpQueue-pNext NULL ? 1 : 0; } // 入队尾插法新节点插入到链表尾部 int EnterLinkQueue(Node_t *pTmpQueue, DataType TmpData) { if (NULL pTmpQueue) return -1; Node_t *pTmpNode malloc(sizeof(Node_t)); if (NULL pTmpNode) { printf(malloc new node failed!\n); return -1; } pTmpNode-Data TmpData; pTmpNode-pNext NULL; // 找到队尾节点 Node_t *pCur pTmpQueue; while (pCur-pNext ! NULL) { pCur pCur-pNext; } pCur-pNext pTmpNode; return 0; } // 出队头删法删除队头节点并返回数据 DataType QuitLinkQueue(Node_t *pTmpQueue) { if (NULL pTmpQueue) { printf(队列指针为空!\n); return -1; } if (IsEmptyLinkQueue(pTmpQueue)) { printf(队空无法出队!\n); return -1; } Node_t *pDel pTmpQueue-pNext; DataType TmpData pDel-Data; pTmpQueue-pNext pDel-pNext; free(pDel); return TmpData; } // 销毁链式队列 int DestroyLinkQueue(Node_t **ppTmpQueue) { if (NULL ppTmpQueue || NULL *ppTmpQueue) return -1; Node_t *pCur *ppTmpQueue; Node_t *pDel NULL; while (pCur ! NULL) { pDel pCur; pCur pCur-pNext; free(pDel); } *ppTmpQueue NULL; return 0; }优化提示当前实现入队需要遍历到尾部时间复杂度 O (n)。工程中通常会额外维护一个队尾指针将入队操作优化为 O (1)初学阶段可先掌握基础逻辑。七、经典排错案例free(): double free detected in tcache 21. 报错含义同一块堆内存被连续调用了两次free()C 标准不允许重复释放glibc 内存管理器检测到后直接终止程序。2. 常见触发场景连续两次调用销毁函数第一次已释放全部内存第二次重复释放。接口内部已经 free 节点外部手动再次 free 该节点。链表结构损坏如入栈写成尾插导致指针混乱销毁循环中重复访问同一块内存。3. 避坑规范每次 free 后立即将对应指针置为 NULL避免野指针。内存释放统一交给销毁函数不要混用手动释放和接口释放。销毁函数入口必须增加空指针判断防御二次调用。确保链表插入删除逻辑正确不出现指针指向混乱、链表断裂。八、学习总结栈和队列本质都是操作受限的线性表核心差异在于操作规则栈后进先出队列先进先出。顺序结构顺序栈、顺序队列优势是访问效率高劣势是容量固定链式结构优势是容量灵活劣势是有指针开销、访问效率略低。C 语言实现数据结构三大高频错误空指针未判断、内存泄漏、重复释放写代码时必须养成防御性编程习惯。链式栈用头插 头删实现 O (1) 的入栈出栈链式队列基础版用尾插 头删实现入队可通过维护尾指针优化效率。