用两个栈实现队列

用两个栈实现队列

这是一个剑指offer里面的题目，思路如下：

就是两个栈轮流存储，所以需要就需要一个change方法改变存储顺序，因为栈是先进后出，而队列是先进先出。

那么问题来了，什么时候应该改变存储顺序？

如果一直是push或者一直是pop的时候，我们其实不需要转换顺序，在当前的栈中进行就可以了，但是当pop和push进行交替的时候，我们就需要改变栈中数据的顺序，只可以用一个状态变量move处理

这里就带来了另一个问题，就是怎么记录数据当前存储在哪个栈里面？

这里也用一个状态变量flag处理就好了，只有在调用change方法的时候才会改变存储的栈

代码如下：

package question;

import java.util.Stack;

/**
 * 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
 * @author sx_xiongbin
 * @2018年12月26日
 */
public class Code6 {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    int flag=0;
    int move =0;
    public void push(int node) {
        if(move == 1) {
            change();
            move = 0;
        }
        if(flag == 0) {
            stack1.push(node);
        }else {
            stack2.push(node);
        }
        
    }
    
    public int pop() {
        if(move == 0) {
            change();
            move =1;
        }
        if(flag == 0) {
           return stack1.pop();
        }else {
            return stack2.pop();
        }
        
    }
    
    private void change() {
        if(flag == 0) {
            int size =stack1.size();
            for(int i=0;i<size;i++) {
                stack2.push(stack1.pop());
            }
            flag =1;
        }else {
            int size =stack2.size();
            for(int i=0;i<size;i++) {
                stack1.push(stack2.pop());
            }
            flag =0;
        }
    }
    
}