队列、栈

队列
队列又称之为先进先出队列，从名字上我们就可以推断测是先来先处理。事实上确实这样，它是一种基于先进先出策略的集合类型，按照任务产生的顺序来完成它们的策略是我们每一天都会遇到的，最平常就是排队，接受服务最早的一定是第一个排队的人，或者说是优先服务等待时间最久的人。
我们在程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序。
一个典型的先进先出队列。

栈
栈也被称之为下压栈，与队列先进先出不同的是，栈是一种基于后进后出策略的集合类型。我们举个例子，就好比课代表收一叠作业交到老师手上，那么老师看的第一本作业一定是最后交到课代表手里的。我们平时上网的时候还会遇到这样的事情，比如通过当前A页面的一个超链接，进入到B页面（并将它压入栈），当我们需要回到A页面时就可以通过回退键回到A页面（从栈中弹出）。

我们来思考一个问题，如何在计算机上实现下面这个表达式的计算

（1+（（2+3）*（4*5）））

首先我们明确递归定义：算数表达式可能是一个数或者是一个

左括号+一个算数表达式+一个运算符+另一个运算符+一个右括号

那么我们如何来解析这样一个由括号，数字和运算符组成的字符串呢？
在上世纪60年代，Dijkstra发明了一个简单的算法，用两个栈来完成这个任务（一个用来保存运算符，另一个用来保存操作数）

• 将操作数压入操作数栈
• 将运算符压入运算符栈
• 忽略左括号
• 当遇到右括号时，弹出一个运算符，同时弹出所需数量的操作数，然后将运算符与操作数的运算结果压入操作数栈
  当我们处理完最后一个右括号后，操作数栈中将只剩下一个一个数，也就是表达式的值。
  

  public class Evaluate{
    public static void main(String[] args){
        Static<String> ops = new Stack<String>();
        Static<Double> vals = new Stack<Double>();
        while(!StdIn.isEmpty()){
            //读取字符串，如果是运算符则压入栈
            String s StdIn.readString();
            if      (s.equals("("))               ;
            else if (s.equals("-"))    ops.push(s);
            else if (s.equals("*"))    ops.push(s);
            else if (s.equals("/"))    ops.push(s);
            else if (s.equals("sqrt")) ops.push(s);
            else if (s.equals(")")){
            //如果字符为")"，弹出运算符和操作数，计算结果并压入栈
                String op =ops.pop();
                double v =vals.pop();
                if      (op.equals("+"))        v=vals.pop() + v;
                else if (op.equals("-"))        v=vals.pop() - v;
                else if (op.equals("*"))        v=vals.pop() * v;
                else if (op.equals("/"))        v=vals.pop() / v;
                else if (op.equals("sqrt"))     v=Math.sqrt(v);
                vals.push(v);
            }
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
  }