数据结构--栈

栈是一种数据结构,其特点是后进先出(LIFO).计算机中有很多操作都采用了栈的数据结构,如浏览器的后退,文本编辑的撤销操作等.

栈的定义

  1. 栈的额定大小
  2. 栈的实际大小
  3. 栈的数据

栈的操作

  • 入栈
  • 出栈
  • 清空栈
  • 初始化栈
  • 输出栈内容

栈的应用

  • 中缀转后缀

    • 从左到右遍历中缀表达式:
    • 遇到数值时,直接输出;
    • 遇到操作符时:
    • 如果栈为空或操作符为(,则操作符入栈
    • 如果操作符为),则一直弹栈到与其匹配的(为止
    • 如果栈不为空,则将栈顶操作符与当前操作符进行比较:
    • 如果当前操作符的优先级小于等于栈顶符号的优先级,则将栈顶操作符出栈输出,然后再次拿栈顶符号与当前操作符进行比较;
    • 如果当前操作符的优先级大于栈顶操作符的优先级,则将当前操作符入栈;
    • 直到表达式结束
  • 后缀表达式的计算:

    • 从左到右遍历表达式:
    • 遇到数值直接进栈;
    • 遇到操作符时,取出栈顶的两个元素进行计算,将计算结果入栈
    • 直到表达式结束