数据结构与算法之栈和队列_操作数栈是如何先进先出的

栈和队列

特点

1. 栈是一种先进后出的结构，队列是一种先进先出的结构
2. 栈通常不考虑排序，需要O（n）的时间复杂度才能找到栈中最大或者最小的数
3. Java虚拟机的实现是基于栈的，Java中有一个Stack类栈，
   Java中Stack类extend是Vector类

利用Satck进行四则运算：

第二个案列：a + b * c，我们从前向后扫描，遇到a，压到操作数栈里，遇到 + ，压到操作符栈里，下一个是 b，此时，我们是不能像后缀表达式求值那样，直接计算 a + b，然后压栈的。因为我们不确定，b 是否会先参与后面的运算，所以我们只能把 b 先压栈，继续向后扫描。看到 * 以后，再把 * 压到操作符栈里；看到 c 以后，也要把 c 先压栈，理由与 b 压栈相同。接下来，再往下扫描，就发现已经到了末尾了。那我们就可以放心地从操作符栈里取出顶上的操作符，在这个例子中，就是 *，然后再从操作数栈里取出两个操作数，就是 b 和 c，然后把b和c的积，不妨记为d，放到操作数栈里。接下来，再去看操作符栈里，还有一个 +，那就把 + 取出来，然后去操作数栈里取出 a 和 d，计算它们的和，这就是最终的结果了。

第二个案例：a + b + c，我们从前向后扫描，遇到a，压到操作数栈里，遇到 + ，压到操作符栈里，下一个是 b，压到操作数栈里。再下一个，又是 + ，由于加法的结合律，我们知道，先把a + b 的结果计算出来，或者后计算，都不会影响最终的结果。所以我们就把能做的化简先做掉。就是说，在扫描到第二个操作符是 + 以后，我们就把第一个操作符取出来，再把两个操作数取出来，求和并且把和送到操作数栈里。接下来的过程与第一个例子是相同的，不再赘述了。

通过这两个例子，我们看到，一个操作符究竟什么时候进行运算，并不取决于它前面的那个操作符是什么，而是取决于它后面的那个操作符是什么。更具体一点讲：如果后面的操作符的运算优化级比前面的操作符高，那么前面的操作符就必须延迟计算；如果后面的操作符优化级比前面的低或者相等，那么前面的操作符就可以进行计算了。上面这句话，非常重要，是我们这节课的核心。请多读几遍，结合上面的两个例子，务必想明白它。

遇到括号？

可以这样想，在遇到形如 a * (b + c) 这样的形式的时候，左边的乘法是一定不能做的，我们只需要将左括号进栈即可。所以，我们可以把TokenStream里取得的左括号看做是一个优先级无穷大的运算符，它使得左方的运算符都不能提前进行计算。

遇到右括号时，b + c 这个加法是可以进行运算的了，所以可以把右括号看作是一个优先级无穷小的运算符，它会使得操作符栈上的所有运算符都出栈并执行计算，直到遇到左括号。遇到左括号以后，只需要把左括号从栈里弹出来，然后让它和右括号一起狗带即可（这就是括号匹配啊，同学们~）。由于括号内的计算都已经完成了，结果是一个整数，我们已经在计算的过程中把这个整数放到操作数栈里了。所以整个括号内的求值就完成了

面试题用两个栈实现队列

import java.util.Stack; //使用栈记得引用java.util,Stack包  

public class Solution {  
   Stack<Integer> stack1 = new Stack<Integer>();  
   Stack<Integer> stack2 = new Stack<Integer>();  

//入栈函数  
   public void push(int num) {  
       stack1.push(num);    //要往栈中压入什么就直接用栈的push方法就好了        
    }  

//出栈函数  
   public int pop() {  
   Integer re=null;   
       if(!stack2.empty()){  // 如果栈2不是空的，那么把最上面那个取出来  
           re=stack2.pop();   
       }else{   
               //如果栈2是空的，就把栈1里的数一个个取出来，放到栈2里  
           while(!stack1.empty()){     
                re=stack1.pop();   
                stack2.push(re);   
                             }   
                  //栈2里有数之后，再次把里面的数取出来  
                  if(!stack2.empty()){   
                         re=stack2.pop();   
                   }   
       }   
       return re;   
    }  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29