前言

数据结构学习进入第四天，今天的核心内容是操作受限的线性表 —— 栈和队列。相比于可以在任意位置插入删除的普通线性表，栈和队列仅允许在指定端点进行操作，是算法与工程开发中非常基础且高频使用的数据结构。

本文整理了栈的核心概念、顺序栈与链式栈的完整代码实现、队列基础概念与链式队列实现，同时汇总了今天实操中踩过的经典坑点，方便复盘和后续查阅。

一、线性表、栈、队列的核心区别

1. 普通线性表：可在任意位置进行插入、删除操作，操作自由度最高。
2. 栈和队列：仅允许在指定位置进行插入删除，属于「操作受限」的特殊线性表，操作规则固定，应用场景针对性强。

二、栈（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); #endif

2. 接口实现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. 【顺序栈易错踩坑点】

1. 判空逻辑错误：误用最大容量tLen判断空栈，正确逻辑是判断Top == 0。
2. 入栈缺少判满：栈满后继续入栈会造成数组越界，触发内存非法访问。
3. 出栈逻辑冗余：多余的 for 循环完全无意义，空栈出栈无返回值会触发未定义行为。
4. 内存泄漏：创建栈时数据区分配失败，未释放已分配的头结点。
5. 空指针未防护：所有接口未判断入参是否为 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); #endif

2. 接口实现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. 【链式栈易错踩坑点】

1. 入栈写成尾插：直接覆盖头结点的 next 指针，导致旧节点全部丢失、内存泄漏，栈中永远只能保存 1 个元素。
2. 出栈判空传错指针：用栈顶数据节点代替头结点判空，逻辑完全错误。
3. 节点分配失败未返回：malloc 失败后继续执行空指针访问，直接触发段错误。
4. 链表结构混乱：指针赋值顺序错误，导致链表断裂、节点丢失。

五、队列（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 2

1. 报错含义

同一块堆内存被连续调用了两次free()，C 标准不允许重复释放，glibc 内存管理器检测到后直接终止程序。

2. 常见触发场景

• 连续两次调用销毁函数，第一次已释放全部内存，第二次重复释放。
• 接口内部已经 free 节点，外部手动再次 free 该节点。
• 链表结构损坏（如入栈写成尾插导致指针混乱），销毁循环中重复访问同一块内存。

3. 避坑规范

1. 每次 free 后立即将对应指针置为 NULL，避免野指针。
2. 内存释放统一交给销毁函数，不要混用手动释放和接口释放。
3. 销毁函数入口必须增加空指针判断，防御二次调用。
4. 确保链表插入删除逻辑正确，不出现指针指向混乱、链表断裂。

八、学习总结

1. 栈和队列本质都是操作受限的线性表，核心差异在于操作规则：栈后进先出，队列先进先出。
2. 顺序结构（顺序栈、顺序队列）优势是访问效率高，劣势是容量固定；链式结构优势是容量灵活，劣势是有指针开销、访问效率略低。
3. C 语言实现数据结构，三大高频错误：空指针未判断、内存泄漏、重复释放，写代码时必须养成防御性编程习惯。
4. 链式栈用头插 + 头删实现 O (1) 的入栈出栈；链式队列基础版用尾插 + 头删实现，入队可通过维护尾指针优化效率。