数据结构：栈
一、概念
对于学过数据结构的人来说，栈的概念应该不陌生，栈是一种先进后出的数据结构，可以把栈想象成一摞盘子，不管是加盘子还是拿盘子，都要从最上面拿。关于栈的详细概念，可以查阅严蔚敏的《数据结构》这本书。
二、例题
1、简单计算器
题目描述：读入一个只包含+,-,*,/的非负整数计算表达式，计算该表达式的值
输入样例：30\90-26=97-5-5-13/88*6+51/29+79*87+57*92
样例输出：12178.21
算法思路：通过栈实现先乘除，后加减，这里需要引入后缀表达式的概念，后缀表达式就是把一次运算的操作符放后边，运算数放前面，这样作的好处是不需要括号实现对运算顺序的控制，当然前提是先将带括号的中缀表达式（常见表达式）给出，转换成后缀表达式。后缀表达式更利与程序计算。
算法描述：
（1）先写出后缀表达式，定义一个队列，用来存放后缀表达式，一个栈，用来暂存操作符
（2）对于数字可以直接加入后缀表达式中，对于运算符，如果栈空就直接将运算符压入栈中，如果栈中有元素，就进行判断，当前入栈元素优先级大于栈顶元素优先级，就 压入栈中，如果当前元素优先级小于等于栈顶元素优先级，就将栈顶元素出栈到后缀表达式中，直到入栈元素优先级大于栈顶元素
（3）重复步骤（2）
（4）当转换成后缀表达式时就可以进行计算操作，
从左向右扫描后缀表达式（队列出队操作），对于操作数，直接入栈，对于操作符，就出栈两个操作数，进行运算后再入栈，重复此操作，直到队空，此时栈顶元素 就是结果
说明：此处因为408从未考过算法题，所以不再给出代码，但是可以参考该思路编写代码。注意对数字读入时多位数字作为整体进行读入。
原文：https://www.cnblogs.com/zyq79434/p/14883356.html