栈的规则

先进后出。如：依次入栈顺序为：A,B,C,D;怎出栈顺序为：D,C,B,A .

二叉树和表达式

• 表达式的二叉树展示方式
  例如：(a+b×(c-d))-e/f，我们平时数学中表达式，其实就是所谓的中缀表达式表达式用树形来表示，如图所示。运算符在树中放在非终端结点的位置上，操作数放在叶子结点处。

表达式二叉树
当我们对此二叉树进行先序、中序和后序遍历后，便可得到表达式的前缀、中缀和后缀书写形式：
前缀：-+a*b-cd/ef
中缀：a+b*c-d-e/f
后缀：abcd-*+ef/-
一般的解法，可以考虑将中缀表达式转换成二叉树，在求值。

• 前、中、后缀表达式
  举例：
  (3 + 4) × 5 - 6 就是中缀表达式
  - × + 3 4 5 6 前缀表达式
  3 4 + 5 × 6 - 后缀表达式

• 中缀表达式（中缀记法）
  直接按照数学逻辑求值就行了。个人感觉中缀表达式最容器转换成二叉树了，因为树的特点是：根节点为运算操作符，而非根叶子节点为操作数，根据这个规则和表达式的优先规则切分成根、左右子树就可以了。

• 前缀表达式（前缀记法、波兰式）
  特点：前缀表达式的运算符位于操作数之前。

  • 前缀表达式的计算机求值：
    从右至左（其实很简单记住扫描方向，就是从第一个操作数所在的那一端开始扫描）扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
    例如前缀表达式“- × + 3 4 5 6”：
    (1) 从右至左扫描，将6、5、4、3压入堆栈；
    (2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；
    (3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；
    (4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

  • 使用栈，将中缀表达式转换为前缀表达式
    遵循以下步骤：
    (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
    (2) 从右至左（和计算求值时的扫描方向是一致的）扫描中缀表达式；
    (3) 遇到操作数时，将其压入S2；
    (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
    (4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
    (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；（意思是栈顶的运算符优先级时刻至少要高于前面入栈的）
    (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
    (5) 遇到括号时：
    (5-1) 如果是右括号“)”，则直接压入S1；
    (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
    (6) 重复步骤(2)至(5)，直到表达式的最左边；
    (7) 将S1中剩余的运算符依次弹出并压入S2；
    (8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
    下面举例演示一下，省的画图了，就借用一下网上现成的吧，谢谢这位大神。
    例如，将中缀表达1+((2+3)×4)-5转换为前缀表达式的过程如下（最后S2出栈，结果为- + 1 × + 2 3 4 5）：

使用栈求前缀表达式

• 后缀表达式（后缀记法、逆波兰式）
  特点：后缀表达式与前缀表达式类似，只是运算符位于操作数之后。

  • 后缀表达式的计算机求值
    与前缀表达式求值方式差不多，只是扫描方向相反，从左到右开始扫描。

  • 将中缀表达式转换为后缀表达式
    与转换为前缀表达式相似，遵循以下步骤：
    (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
    (2) 从左至右（再提一次，此时操作数在左边）扫描中缀表达式；
    (3) 遇到操作数时，将其压入S2；
    (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
    (4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
    (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
    (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
    (5) 遇到括号时：
    (5-1) 如果是左括号“(”，则直接压入S1；
    (5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
    (6) 重复步骤(2)至(5)，直到表达式的最右边；
    (7) 将S1中剩余的运算符依次弹出并压入S2；
    (8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
    例如，将中缀表达1+((2+3)×4)-5转换为后缀表达式的过程如下（结果为1 2 3 + 4 × + 5 -（注意S2出栈后需要逆序输出）。）：

使用栈求后缀表达式

根据表达式反推二叉树

• 中缀表达式求二叉树：
  其实记住运算符为根节点，然后把操作数作为左右叶子节点，根据二叉树的中序遍历，构建一棵子树，不断自下而上，就能复原了。举例(3 + 4) × 5 - 6（画了个丑图）：

  中缀表达式转二叉树

• 后缀表达式求二叉树：
  思路是一样的，拿两个操作数和一个运算符，不断自底向上组建二叉树。举例：3 4 + 5 × 6 - 后缀表达式。（写字太丑了，我自己都看不下去了。。。。。）
  

  后缀表达式求二叉树

• 前缀表达式转二叉树
  抱歉，我想不出来。。。。

两个栈共用存储空间

栈满条件：栈1向上增长，栈2向下增长，显然当top[1]和top[2]相邻时，栈满。

栈满

栈和堆

栈区（stack）— 由编译器自动分配释放 ，存放为运行函数而分配的局部变量、函数参数、返回数据、返回地址等。
堆区（heap） — 一般由程序员分配释放， new, malloc之类的，若程序员不释放，程序结束时可能由OS回收 。