Days 22栈与队列

一、前言程序 数据结构 算法栈和队列是开发中最基础、高频使用的受限线性表。 数组 / 普通链表可以在任意位置增删元素而栈、队列严格限制操作位置栈后进先出 LIFO仅栈顶插入、删除队列先进先出 FIFO队尾入队、队头出队本文基于 LinuxC 语言实现包含顺序栈、链式栈、循环队列、链式队列全套代码配套内存图解、易错点分析适合期末复习、面试基础复习。二、栈Stack核心理论2.1 栈核心规则操作端只有栈顶栈底固定入栈 (Push)数据放到栈顶出栈 (Pop)只取出栈顶元素判空无有效元素判满仅顺序栈存在数组空间用完两种实现顺序栈连续数组、链栈动态节点无容量上限2.2 顺序栈数组实现1. 结构体设计c运行typedef int DataType; typedef struct{ DataType *pData; // 动态数组存放栈数据 int tLen; // 栈最大容量 int Top; // 栈针指向下一个待写入位置Top0代表空栈 }Stack_t;内存图解pData是堆区连续内存Top 记录当前栈元素个数空栈Top 0满栈Top tLen2. 完整 seqstack.h 头文件c运行#ifndef __SEQSTACK_H__ #define __SEQSTACK_H__ typedef int DataType; typedef struct{ DataType *pData; int tLen; int Top; }Stack_t; // 创建栈指定最大容量 extern Stack_t *CreateSeqStack(int Len); // 判断栈空 extern int IsEmptySeqStack(Stack_t *pTmpStack); // 判断栈满 extern int IsFullSeqStack(Stack_t *pTmpStack); // 入栈 extern int PushSeqStack(Stack_t *pTmpStack, DataType TmpData); // 出栈返回栈顶值 extern DataType PopSeqStack(Stack_t *pTmpStack); // 销毁栈二级指针避免野指针 extern int DestroySeqStack(Stack_t **ppTmpStack); #endif3. seqstack.c 功能实现c运行#include seqstack.h #include stdio.h #include stdlib.h // 创建顺序栈 Stack_t *CreateSeqStack(int Len) { Stack_t *pTmpStack (Stack_t *)malloc(sizeof(Stack_t)); if (NULL pTmpStack) { perror(栈结构体申请失败); return NULL; } pTmpStack-tLen Len; pTmpStack-Top 0; pTmpStack-pData (DataType *)malloc(sizeof(DataType) * Len); if (NULL pTmpStack-pData) { perror(数组空间申请失败); free(pTmpStack); return NULL; } return pTmpStack; } // 判断栈空 int IsEmptySeqStack(Stack_t *pTmpStack) { return pTmpStack-Top 0; } // 判断栈满 int IsFullSeqStack(Stack_t *pTmpStack) { return pTmpStack-Top pTmpStack-tLen; } // 入栈 int PushSeqStack(Stack_t *pTmpStack, DataType TmpData) { if (IsFullSeqStack(pTmpStack)) { printf(栈已满无法入栈\n); return -1; } pTmpStack-pData[pTmpStack-Top] TmpData; pTmpStack-Top; return 0; } // 出栈先存数据再释放/移动栈针禁止free后取值 DataType PopSeqStack(Stack_t *pTmpStack) { 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; free((*ppTmpStack)-pData); free(*ppTmpStack); *ppTmpStack NULL; return 0; }4. main.c 测试代码c运行#include seqstack.h #include stdio.h int main(void) { Stack_t *pseq CreateSeqStack(10); // 入栈1~5 for(int i1;i5;i) PushSeqStack(pseq, i); // 出栈打印后进先出 5 4 3 2 1 while(!IsEmptySeqStack(pseq)) printf(%d , PopSeqStack(pseq)); DestroySeqStack(pseq); return 0; }5. 顺序栈优缺点✅ 优点随机访问栈顶、内存连续、读写速度快 ❌ 缺点容量固定扩容麻烦空间不足会栈满闲置数组会内存浪费。2.3 链式栈链表实现无容量限制1. 节点结构带哨兵头节点c运行typedef int DataType; typedef struct Node{ DataType data; struct Node *pNext; }Node_t;设计思路头插法头节点pNext直接指向栈顶入栈出栈仅操作头节点后第一个节点时间复杂度 O (1)。空栈pHead-pNext NULL无需判满堆内存足够可无限入栈2. 链栈核心实现关键易错点出栈逻辑必须遵循保存栈顶节点指针提前取出节点 data断开头节点与栈顶连接free 释放节点禁止先 free 再读取 data释放后内存失效程序段错误完整链栈 Push/Pop 示例c运行// 入栈 int PushLinkStack(Node_t *pHead, DataType val) { Node_t *pNew (Node_t*)malloc(sizeof(Node_t)); if(!pNew) return -1; pNew-data val; pNew-pNext pHead-pNext; pHead-pNext pNew; return 0; } // 出栈 DataType PopLinkStack(Node_t *pHead) { if(pHead-pNext NULL) { printf(链栈空\n); return 0; } Node_t *pDel pHead-pNext; DataType res pDel-data; // 先存数据 pHead-pNext pDel-pNext; free(pDel); return res; }链栈优缺点✅ 无容量上限、按需分配内存无空间浪费 ❌ 每个节点附带指针额外消耗内存无法随机访问。三、队列Queue核心理论3.1 队列规则先进先出 FIFO只能队尾插入入队 Enter、队头删除出队 Quit 两种实现循环顺序队列解决普通顺序队列假溢出、链式队列3.2 循环顺序队列普通数组队列会出现假溢出队头元素出队后前面空间闲置但无法入队循环队列通过取模(rear1)%maxlen实现环形复用。 判空front rear判满(rear1)%maxlen front牺牲一格空间区分空 / 满3.3 链式队列双指针设计头指针 front出队、尾指针 rear入队入队操作尾指针出队操作头指针无假溢出、无容量限制。四、栈和队列对比总结表格特性顺序栈链栈循环队列链队列存储连续数组离散链表节点环形数组离散链表容量固定上限无上限固定上限无上限操作复杂度O(1)O(1)O(1)O(1)内存开销仅数据数据 指针仅数据数据 指针溢出问题栈满溢出无溢出牺牲一格判满无溢出适用场景数据量固定数据动态增减固定批量任务持续大量任务五、高频面试 / 期末易错点顺序栈出栈不能 free 后取值必须先保存 data链栈统一头插法栈顶是头节点后继循环队列判满条件(rear1)%len front不可直接rearfront销毁容器使用二级指针将外部指针置 NULL杜绝野指针栈函数调用栈、表达式求值、括号匹配队列消息队列、任务调度、广度优先搜索 (BFS)。六、Linux 编译运行命令以顺序栈为例bash# 编译 gcc main.c seqstack.c -o stack -g # 运行 ./stack # gdb调试段错误 gdb ./stack # valgrind检测内存泄露 valgrind --toolmemcheck ./stack七、结尾栈和队列是二叉树、图、排序算法的基础容器建议手动完整敲一遍两套栈 两套队列代码吃透内存分配、指针操作、边界判空判满逻辑后续学习复杂数据结构会事半功倍。