1、线性表之栈(stack)-概述

  1. 1、栈(Stack)-概述：
  2.     1-1、栈是一种操作受限的数据结构，它只能在表尾进行插入和删除操作。【栈顶允许操作，栈底不允许操作。】
  3.     1-2、表尾[插入的一端]有特殊的含义，我们称为栈顶(top)，表头端[固定的一端]称为栈底(bottom), 不含元素的空表称为空栈。栈是一种后进先出(LIFO-Last in, First out) 的的线性表。
  4.     1-3、往栈里放数据，称为入栈(push);往栈里取数据，称为出栈(pop);
  5.     1-4、栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。

1.1、栈-分类

  1. 1、栈(Stack)-分类：
  2.     1-1、静态栈：用数组实现的栈，由于数组是固定大小的，所以叫做静态栈。
  3.     1-2、动态栈：用链表实现的栈，由于链表可以随时新增节点的，所以叫做动态栈。

1.2、栈-应用-前缀|中缀|后缀表达式-简析

  1. 1、栈(Stack)-应用：
  2.     1-1、前缀表达式、中缀、后缀表达式求法;
  3.         1-1-1、前缀表达式(波兰表达式)：运算符位于操作数之前，没有括号的算术表达式，它将运算符写在前面，操作数写在后面。
  4.             1-1-1-1、前缀表达式的计算机求值过程：[从右到左扫描表达式]，** 遇到数字，将数字都压入栈，遇到运算符时，弹出栈顶两个数 **，用运算符计算后将结果入栈，重复操作。
  5.             1-1-1-2、举例：(3+4)*5-6 对应前缀表达式: - * + 3 4 5 6
  6.             1-1-1-3、步骤：- 1 + 2 3
  7.                 a.初始化一个空栈。此桟用来对要运算的数字进出使用。
  8.                 b.扫描到3时，记录下这个数字串，将数字都压入栈，继续向左扫描。
  9.                 c.扫描到2时，记录下这个数字串，将数字都压入栈，继续向左扫描。
  10.                 d.当扫描到+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下这个新数字串，将数字都压入栈，并继续向左扫描。
  11.                 e.扫描到1时，记录下这个数字串，将数字都压入栈，并继续向左扫描。
  12.                 f.扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，所以表达式的值为-4。
  14.         1-1-2、中缀表达式：常见的运算表达式,为人们熟悉的数学运算式子写法。
  16.         1-1-3、后缀表达式(逆波兰表达式)：运算符位于操作数之后。
  17.             1-1-3-1、后缀表达式的计算机求值过程：[从左到右扫描表达式]，** 遇到数字，将数字都压入栈，遇到运算符时，弹出栈顶两个数 **，用运算符计算后将结果入栈，重复操作。
  18.             1-1-3-2、举例：(3+4)*5-6 对应后缀表达式：3 4 + 5 * 6 -
  19.             1-1-3-3、步骤：9 3 1-3*+ 10 2/+
  20.                     a.初始化一个空栈。此桟用来对要运算的数字进出使用。
  21.                     b.后缀表达式中前三个都是数字，所以9、3、1进栈。
  22.                     c.接下来是减号"-"，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈。
  23.                     d.接着是数字3进栈。
  24.                     e.后面是乘法"*"，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
  25.                     f.下面是加法"+"，所以找中6和9出找，9与6相加，得到15，将15进栈。
  26.                     g.接着是10与2两数字进栈。
  27.                     h.接下来是符号因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。
  28.                     i.最后一个是符号“+”，所以15与5出找并相加，得到20，将20进栈。
  29.                     j.结果是20出栈，栈变为空。
  31.         1-1-4、前缀表达式、中缀、后缀表达式求法-小结：通过利用栈的特性，我们可以从中缀表达式得到前后缀表达式，轻松的计算出其结果。
  32.             --

1.2.1、中缀表达式转换为前缀表达式|后缀表达式

  1. 1、转化步骤：
  2.     1-1、按照运算符的优先级对所有的运算单位加括号
  3.     1-2、将运算符移动到对应括号的前面(前缀表达式)或后面(后缀表达式)
  4.     1-3、去掉括号，得到前缀或后缀表达式
  6. 2、Demo-示例
  7.     -- 中缀表达式：1+(2+3)×4-5
  8.     2-1、加括号，式子变成 ((1+((2+3)×4))-5)
  9.     2-2、移动运算符
  10.         2-2-1、对于前缀表达式，变成了 -(+(1×(+(23)4))5)
  11.         2-2-2、对于后缀表达式：变成了((1((23)+4)×)+5)-
  12.     2-3、去掉括号
  13.         2-3-1、前缀表达式： - + 1 × + 2 3 4 5
  14.         2-3-2、后缀表达式：1 2 3 + 4 × + 5 -