用两个栈来实现队列

用两个栈来实现队列

算法思想

1. 什么是栈，后进先出
2. 什么是队列，先进先出
3. 如果有两个栈，如何模拟队列先进先出？假设有三个元素ABC进入栈1，我们按照队列的要求，pop操作应该弹出A。但此时栈1的数据弹出顺序是CBA。解决方法：需要出栈的时候，先把栈1所有数据逐个pop，并push到栈2。最后从栈2出栈，那么我们就可以得到A了
4. 我们把栈1数据全部弹到栈2，那么要入栈如何破？自然是把栈2数据逐个pop，并push进入栈1。最后在把当前数据push进栈1，就好了不是么

上代码

import java.util.Stack;

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

    public void push(int node) {
        int val;
        // stack2 => stacl1
        while(!stack2.empty()){
            val = stack2.pop();
            stack1.push(val);
        }
        // push
        stack1.push(node);
    }

    public int pop() {
        int val;

        while(!stack1.empty()){
            val = stack1.pop();
            stack2.push(val);
        }

        return stack2.pop(); 
    }
}