栈
栈是一种数据结构,其特点是后进先出(LIFO).计算机中有很多操作都采用了栈的数据结构,如浏览器的后退,文本编辑的撤销操作等.
栈的定义
- 栈的额定大小
- 栈的实际大小
- 栈的数据
栈的操作
- 入栈
- 出栈
- 清空栈
- 初始化栈
- 输出栈内容
栈的应用
中缀转后缀
- 从左到右遍历中缀表达式:
- 遇到数值时,直接输出;
- 遇到操作符时:
- 如果栈为空或操作符为
(,则操作符入栈 - 如果操作符为
),则一直弹栈到与其匹配的(为止 - 如果栈不为空,则将栈顶操作符与当前操作符进行比较:
- 如果当前操作符的优先级小于等于栈顶符号的优先级,则将栈顶操作符出栈输出,然后再次拿栈顶符号与当前操作符进行比较;
- 如果当前操作符的优先级大于栈顶操作符的优先级,则将当前操作符入栈;
- 直到表达式结束
后缀表达式的计算:
- 从左到右遍历表达式:
- 遇到数值直接进栈;
- 遇到操作符时,取出栈顶的两个元素进行计算,将计算结果入栈
- 直到表达式结束