开场白
早先军官们都爱用左轮手枪,而非弹夹式手枪。因为弹夹式手枪容易卡主臭弹。
栈的定义
栈这种后进先出的数据结构。
应用:
- 浏览器的“后退”键
- Word、Photoshop等撤销操作
允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈
栈元素具有线性关系,即前驱后继关系。它的特殊之处在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。
进栈出栈变化形式
最先进栈的元素,不一定最后出栈。312这个顺序不可能,因为3出栈了说明1,2都已经进栈了,1不可能比2先出栈
栈的抽象数据类型
对于栈来讲,理论上线性表的操作特性它都具备。顺序存储和链式存储,对于栈来说,也是同样适用。
栈的顺序存储结构及实现
栈的顺序存储结构
既然栈是线性表的特例,那么栈的顺序存储其实也是线性表顺序存储的简化。线性表是用数组来实现的。
栈的顺序存储结构——进栈操作
栈的顺序存储结构——出栈操作
复杂度均为O(1)
后缀表达式
从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终结果
中缀转后缀
从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即称为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止