栈 stk 与队列 Q

1. 栈

   int stk[N] ,tt=-1 //tt 代表栈顶(目前位置)  。
   //插入  push
   stk[++tt] = x;  //++tt不要搞错，tt有值的
   //弹出   pop
   tt--;
   //查询   peek
   stk[tt];
   //判断栈是否为空
   if(tt>=0) //不空  tt=-1为空。
   

   题：

   1. 中缀表达式求值

      1. 利用双栈，一个存运算符，一个存值。

      2. 每次运算符栈顶元素对比此操作符优先级小于等于栈顶，全部计算，注意小于等于。遇到右括号全部计算到左括号。

      3. static void cal(){
             int a = pop2();
             int b = pop2();
             char op = pop1();
             int ans = 0;
          if(op=='*') ans= a*b;
             if(op=='/') ans= a/b;
             if(op=='+') ans= a+b;
             if(op=='-') ans= a-b;
             add2(ans); //入栈；
         }
         //--------------------------------------------
         for(int i = 0;i<N;i++){
             if(c[i]>='0'&&c[i]<='9'){  //如果是数字
                 int num = c[i]-'0';
                 while(c[i+1]>='0'&&c[i+1]<='9'){
                     num =num*10 + c[i+1]-'0';
                     i++;
                 }
                 add2(num);
             }else{   //是运算符或者括号
                 //处理括号
                 if(c[i]=='(') add1('(');
                 else if(c[i]==')'){
                     while(top1()!='('){
                         cal();  //计算
                     }
                     pop1(); //弹出左括号
                 }else{
                         while (tt1!=0 && prior.get(c[i])<=prior.get(top1())){   //优先级小于等于栈顶。先计算直到低优先级
                             cal();  //注意是小于等于！！！！！
                         }
                         add1(c[i]);
                 }
             }
         }
         while(tt1!=0){  //剩下的全部计算
             cal();
         }
         System.out.println(top2());
         

2. 队列

   int Q[N], hh=0,tt=-1//hh是队头弹出，tt是队尾插入
   //插入  push
   Q[++tt] = x;
   //弹出   pop
   hh++;  //队头后移，只有栈才是 -- 
   //判空  
   if(hh<=tt)  //不是空  hh>tt 才是空
   //查询队头 队尾  peel
    Q[hh];
    Q[tt];