数据结构篇（五）：线性表——栈

前言前面几篇讲了顺序表、单链表和双链表它们都是线性表的基础实现方式。而栈和队列本质上是对线性表的操作方式做了限制之后得到的两种特殊线性结构。本文来讲讲栈——一种后进先出的数据结构理解它是后续学习递归、DFS、表达式求值、括号匹配等内容的基础。一、什么是栈栈Stack是一种只允许在一端进行插入和删除操作的线性表。允许操作的一端叫栈顶top另一端叫栈底bottom。栈的核心特性是后进先出LIFOLast In First Out数据压入栈的顺序和弹出栈的顺序正好相反最后进栈的元素最先出来。生活中的例子1.一摞盘子只能从最上面拿也只能从最上面放2.浏览器的后退功能3.函数调用时的调用栈每次函数调用都会压栈返回时弹栈。二、栈的实现方式栈可以用数组实现也可以用链表实现。数组实现从数组尾部进行插入删除不需要挪动数据效率是O(1)且实现简单是实际中最常用的方式类似于顺序表的尾插尾删链表实现如果用链表实现一般选择在链表头部进行插入删除这样效率也是O(1)但相对数组实现要多一层指针操作实际使用较少。本文以数组实现为主进行讲解。三、栈的结构定义栈本质上就是一个支持动态扩容的顺序表只是把操作限制在了一端栈顶。typedef int STDataType; typedef struct Stack { STDataType* array; // 存储数据的数组 int top; // 栈顶下标也可以用size表示元素个数 int capacity; // 容量 } Stack;四、栈的基本操作4.1 初始化void StackInit(Stack* ps) { ps-array NULL; ps-top 0; // top指向栈顶元素的下一个位置初始为0表示空栈 ps-capacity 0; }4.2 检查容量扩容​void StackCheckCapacity(Stack* ps) { if (ps-top ps-capacity) { int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2; STDataType* tmp (STDataType*)realloc(ps-array, newCapacity * sizeof(STDataType)); if (tmp NULL) { perror(realloc fail); exit(-1); } ps-array tmp; ps-capacity newCapacity; } }4.3 入栈Pushvoid StackPush(Stack* ps, STDataType x) { assert(ps ! NULL); StackCheckCapacity(ps); ps-array[ps-top] x; ps-top; }4.4 出栈Popvoid StackPop(Stack* ps) { assert(ps ! NULL); assert(ps-top 0); // 栈不能为空 ps-top--; }4.5 取栈顶元素TopSTDataType StackTop(Stack* ps) { assert(ps ! NULL); assert(ps-top 0); return ps-array[ps-top - 1]; }4.6 判空bool StackEmpty(Stack* ps) { assert(ps ! NULL); return ps-top 0; }4.7 获取有效元素个数int StackSize(Stack* ps) { assert(ps ! NULL); return ps-top; }4.8 销毁void StackDestroy(Stack* ps) { assert(ps ! NULL); free(ps-array); ps-array NULL; ps-top ps-capacity 0; }五、完整测试代码int main() { Stack st; StackInit(st); StackPush(st, 1); StackPush(st, 2); StackPush(st, 3); StackPush(st, 4); printf(栈顶元素: %d\n, StackTop(st)); // 4 while (!StackEmpty(st)) { printf(%d , StackTop(st)); StackPop(st); } printf(\n); // 4 3 2 1正好和入栈顺序相反 StackDestroy(st); return 0; }六、时间复杂度分析操作时间复杂度说明入栈 pushO(1)均摊不涉及数据搬移出栈 popO(1)只需移动top取栈顶 topO(1)直接访问下标判空 emptyO(1)判断top是否为0栈的所有标准操作都是O(1)这也是为什么用数组实现栈是最优选择——完全不需要像顺序表那样考虑头部/中间插入删除因为栈根本不允许这样操作。七、栈的经典应用场景栈在实际开发和算法题中出镜率非常高常见应用包括括号匹配判断字符串中的()[]{}是否匹配利用栈后进先出的特性左括号入栈遇到右括号就弹栈比对逆波兰表达式后缀表达式求值操作数入栈遇到运算符就弹出栈顶两个元素运算结果再入栈函数调用栈程序运行时每次函数调用都会在栈上开辟一块栈帧保存局部变量、返回地址等信息函数返回时栈帧弹出这也是递归可能导致栈溢出Stack Overflow的根本原因浏览器前进后退、编辑器撤销重做Undo/Redo本质上都是用栈记录历史状态深度优先遍历DFS可以用递归实现也可以用显式栈模拟递归过程避免递归层数过深导致栈溢出。八、数组实现 vs 链表实现栈特性数组实现链表实现头部操作push/pop效率O(1)均摊O(1)空间利用率可能有扩容冗余每个节点有指针开销但按需申请实现复杂度简单相对复杂需要动态申请/释放节点缓存利用率高连续内存低不连续实际使用更常用较少一般只在教学中讲解综合来看实际开发和面试中栈基本都用数组来实现C STL中的stack默认底层容器也是deque本质上也是连续存储结构的组合。九、总结栈是一种操作受限的线性表核心特性只有一句话后进先出。它的实现并不复杂本质上就是只能在一端操作的顺序表所有标准操作的时间复杂度都是O(1)。真正的难点和考察重点在于灵活运用——括号匹配、表达式求值、单调栈、DFS模拟等都是建立在栈这个基础结构之上的经典问题建议在掌握实现之后多刷一些栈相关的算法题巩固理解。如果这篇文章对你有帮助欢迎点赞收藏下一篇预告队列的实现与应用敬请期待