本篇核心知识栈、容器适配器、栈的分类顺序栈、链栈、基础操作一、栈基本概念1. 定义栈是受限线性表属于基础数据结构。核心规则先进后出FILO / 后进先出 LIFO操作限制插入入栈、删除出栈仅能在同一端进行这一端称为栈顶另一端固定不可操作称为栈底。2. 专业术语栈顶top允许插入、删除、访问的一端栈的操作核心端。栈底bottom固定端仅作为栈的起始位置不做增删操作。入栈压栈 /push向栈中添加元素。出栈弹栈 /pop从栈顶删除元素。栈空栈内无任何元素。栈满顺序栈特有概念存储空间被占满无法继续入栈。栈大小栈中当前元素总个数。二、栈的整体分类按照底层存储结构划分分为顺序栈和链栈两大类在 C 标准库中栈属于容器适配器。1. 顺序栈1底层结构依托数组连续内存实现数组整体作为栈的存储空间。数组下标通常用下标0作为栈底最后一个有效元素下标作为栈顶。标识一般定义一个栈顶指针 / 下标变量记录当前栈顶位置。2核心特点内存连续访问速度快随机访问能力。存在栈满问题数组长度固定空间一旦耗尽无法扩容静态顺序栈。实现简单、代码简洁适合元素数量固定、预估上限的场景。增删操作仅在数组尾部完成效率极高。3基础结构示意// C语言 静态顺序栈 简易结构 #define MAX_SIZE 100 // 栈最大容量 int stack[MAX_SIZE]; // 数组作为栈空间 int top -1; // 栈顶下标-1 表示栈空top -1栈空top MAX_SIZE - 1栈满。2. 链栈课堂重点讲解1底层结构依托单链表非连续内存实现链表整体作为栈链表头部作为栈顶链表头部增删效率最高。节点结构分为数据域存储元素 指针域指向下一个节点。无固定容量理论上只要内存足够可无限添加元素不存在栈满。2核心特点内存不连续动态分配节点内存按需申请、按需释放。无栈满限制适合元素数量动态变化、无法预估上限的场景。每次入 / 出栈都需要操作节点指针额外消耗少量内存指针域。链表头部作为栈顶增删效率和顺序栈一致。3节点结构C/C 通用// 链栈节点结构 struct Node { int data; // 数据域存储栈元素 Node* next; // 指针域指向下一个节点 }; Node* top nullptr; // 栈顶指针指向链表头部nullptr表示栈空4链栈节点指向规则课堂重点栈顶节点的next指向前一个入栈的节点。原因若反向指向出栈时无法回溯找到上一级节点会造成逻辑死区。3. C 容器适配器std::stack1概念容器适配器不独立实现底层存储复用已有标准容器vector/deque/list封装出栈结构。默认底层deque双端队列。特性仅对外暴露栈的标准接口屏蔽底层容器的其他操作。2接口规则std::stack 严格遵循栈规则仅支持栈顶操作不允许访问中间 / 栈底元素。常用接口push()入栈、pop()出栈、top()取栈顶元素、empty()判空、size()获取元素个数。3与原生栈的区别无需手动管理内存标准库封装完成开发效率高。底层可灵活切换容器适配不同性能需求。三、栈的通用基础操作顺序栈 链栈 通用逻辑所有栈的核心操作共 5 个判空、入栈、出栈、取栈顶元素、获取栈大小。重要原则出栈、取栈顶前必须先判断栈是否为空空栈执行这两个操作会引发程序异常。1. 判空empty顺序栈判断栈顶下标top -1。链栈判断栈顶指针top nullptr。标准栈直接调用stack.empty()。2. 入栈push顺序栈先判断是否栈满未满则top再向stack[top]赋值。链栈新建节点 → 新节点next指向原栈顶 → 更新栈顶为新节点。标准栈stack.push(元素)。3. 出栈pop顺序栈先判空非空则直接top--逻辑删除数据残留新元素会覆盖。链栈先判空暂存原栈顶节点 → 栈顶指针后移 → 释放原节点内存防止内存泄漏。标准栈stack.pop()仅删除不返回元素。4. 取栈顶元素top仅读取栈顶数据不删除元素。前提栈非空。5. 获取栈元素个数size顺序栈top 1top 从 - 1 开始。链栈需遍历链表统计节点个数无直接记录时也可额外定义变量实时计数。标准栈stack.size()。四、代码实现结合课堂讲解1. 静态顺序栈C 实现#include stdio.h #define MAX 10 // 栈最大容量 ​ int stack[MAX]; int top -1; // 栈空标识 // 1. 判空 int isEmpty() { return top -1; } // 2. 判满 int isFull() { return top MAX - 1; } // 3. 入栈 void push(int val) { if (isFull()) { printf(栈已满无法入栈\n); return; } stack[top] val; } // 4. 出栈 void pop() { if (isEmpty()) { printf(栈为空无法出栈\n); return; } top--; } // 5. 取栈顶 int getTop() { if (isEmpty()) return -1; return stack[top]; }2. 链栈C 实现#include iostream using namespace std; // 链栈节点 struct Node { int data; Node* next; }; Node* top nullptr; // 栈顶指针 ​ // 判空 bool isEmpty() { return top nullptr; } ​ // 入栈 void push(int val) { // 1. 新建节点 Node* newNode new Node; newNode-data val; // 2. 新节点指向原栈顶 newNode-next top; // 3. 更新栈顶 top newNode; } ​ // 出栈 void pop() { if (isEmpty()) { cout 栈空无法出栈 endl; return; } Node* temp top; // 暂存待删除节点 top top-next; // 栈顶后移 delete temp; // 释放内存防止内存泄漏 } ​ // 取栈顶 int getTop() { if (isEmpty()) return 0; return top-data; }3. C 标准栈std::stack#include iostream #include stack using namespace std; ​ int main() { stackint st; st.push(100); // 入栈 st.push(200); ​ cout st.top() endl; st.pop(); cout st.top() endl; ​ if (!st.empty()) { st.pop(); } cout st.size() endl; return 0; }五、顺序栈 vs 链栈 对比总结对比项顺序栈链栈底层结构数组连续内存链表非连续内存容量限制固定容量存在栈满动态扩容无栈满内存开销仅存储数据开销小额外存储指针开销略大访问速度连续内存访问更快链式遍历速度略低适用场景元素数量固定、数据量小元素动态变化、大数据量内存泄漏风险无数组自动回收需手动释放节点风险高六、栈的核心特性与拓展知识点1. 内存栈程序栈区拓展日常代码中栈内存和数据结构栈逻辑一致函数局部变量、形参、函数调用栈帧都存储在栈区。函数调用规则先调用后释放完全遵循后进先出。风险栈空间大小有限递归过深会造成栈溢出Stack Overflow。2. 栈的经典应用场景函数调用 递归程序利用栈记录函数调用层级、返回地址递归的逐层调用与回溯完全依赖栈结构。括号匹配校验编译器 / 编辑器校验()、[]、{}左括号入栈右括号出栈最终栈空则匹配合法。表达式求值后缀表达式中缀转后缀、后缀表达式计算是栈最经典的算法应用。浏览器前进 / 后退、APP 页面跳转页面跳转压入栈后退就是出栈。撤销 / 恢复功能Word、PS 等软件每一步操作入栈撤销即出栈。进制转换十进制转二进制 / 八进制除基取余余数入栈最后依次出栈得到结果。3. 易错点总结课堂强调空栈操作出栈、取栈顶必须先判空否则代码崩溃。链栈内存管理出栈必须delete节点长期不释放会造成内存泄漏。顺序栈栈满静态数组栈容量固定超出上限无法入栈。栈的访问限制严禁随机访问中间元素只能操作栈顶这是栈的核心约束。std::stack 注意pop()只删除元素不返回栈顶值需要先用top()获取。4. 容器适配器补充课堂内容Cstd::stack默认基于deque实现也可指定底层容器stackint, vectorint st; // 底层用vector stackint, listint st2; // 底层用list选择原则追求头尾操作效率优先deque单纯数组存储选vector。七、拓展栈的衍生结构双端栈一个数组两端分别作为栈顶共享存储空间节约内存。共享栈两个栈共用一片连续内存相向增长。单调栈算法专用栈栈内元素保持单调递增 / 递减常用于最大矩形、接雨水等经典算法题。