剑指offer-5:用两个栈实现队列

题目描述

　　用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

解题思路

　　首先，假如我们要插入一些数据“abcd”，我们知道按照这个顺序队列出现的结果也是“abcd”，而栈会出现“dcba”，刚好相反，因此将该栈的到的数据在插入另外一个栈中就会出现我们想要的结果。因此，我们定义两个栈为“stack1”和“stack2”，栈1只用来插入数据，栈2用来删除数据栈1插入进来的数据。

图（1）：将队列中的元素“abcd”压入stack1中，此时stack2为空；

图（2）：将stack1中的元素pop进stack2中，此时pop一下stack2中的元素，就可以达到和队列删除数据一样的顺序了；

图（3）：可能有些人很疑惑，就像图3，当stack2只pop了一个元素a时，stack1中可能还会插入元素e,这时如果将stack1中的元素e插入stack2中，在a之后出栈的元素就是e了，显然，这样想是不对的，我们必须规定当stack2中的元素pop完之后，也就是satck2为空时，再插入stack1中的元素。

代码

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();//压入栈
    Stack<Integer> stack2 = new Stack<Integer>();//弹出栈
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
    	//弹出栈没有元素时，压入元素必须将压入栈中的元素全部压入
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        //弹出中有元素时，弹出元素必须将弹出栈中的元素全部弹出
        return stack2.pop();
    }
}