34_数据结构_栈

张开发
• 2026/4/14 16:54:04 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

34_数据结构_栈
一、栈的基本概念1. 栈的定义(1) 栈的逻辑结构a. 线性表的特例i. 只允许在一端插入和删除⓵ 栈顶与栈底2. 栈的特点(1) 后进先出a. LIFO 结构i. 最后进入的元素最先被访问二、栈的数学表示1. 栈的状态表示(1) 栈的序列形式KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…其中s1s_1s1​为栈底sns_nsn​为栈顶2. 栈的基本操作(1) 入栈KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…(2) 出栈KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…三、栈的存储结构1. 顺序栈(1) 基于数组实现a. 栈顶指针topi.top -1表示空栈(2) 代码结构/** Allman 风格*/KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…2. 链式栈(1) 基于链表实现a. 栈顶为链表头结点i. 入栈为头插法⓵ 出栈为删除头结点四、栈的时间复杂度分析1. 基本操作(1) 入栈a. 顺序栈未满O(1)O(1)O(1)b. 链式栈O(1)O(1)O(1)(2) 出栈a. 顺序栈非空O(1)O(1)O(1)b. 链式栈O(1)O(1)O(1)2. 栈的扩容(1) 动态顺序栈a. 均摊分析i. 均摊时间复杂度为O(1)O(1)O(1)五、栈的应用场景1. 函数调用栈(1) 递归函数的实现a. 每次调用压入栈帧i. 返回时弹出栈帧2. 表达式求值(1) 中缀转后缀a. 运算符优先级比较i. 使用栈临时存储运算符(2) 后缀表达式求值a. 遇到操作数入栈b. 遇到运算符弹出两个操作数3. 括号匹配(1) 算法流程a. 左括号入栈b. 右括号与栈顶匹配i. 匹配成功则弹出否则报错六、栈的常见问题与扩展1. 共享栈(1) 两个栈共享一个数组a. 栈底分别在数组两端i. 栈顶向中间移动2. 栈的溢出与下溢(1) 上溢a. 顺序栈满时继续入栈(2) 下溢a. 空栈时进行出栈操作3. 栈与队列的对比(1) 栈LIFO(2) 队列FIFO

更多文章