LintCode 40用栈实现队列 Java实现

题目要求：
40. 用栈实现队列

正如标题所述，你需要使用两个栈来实现队列的一些操作。

队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。

pop和top方法都应该返回第一个元素的值。
样例

例1:

输入:
push(1)
pop()
push(2)
push(3)
top()
pop()
输出:
1
2
2
这道题我还在《程序员代码面试指南》-IT名企算法与数据结构题目最优解中也看到了，这道题不难，只要熟悉栈和队列的原则即可写出。

栈：先进后出；
队列：先进先出；

思路：可以利用两个栈，一个用于压入数据pushStack，一个取数据popStack；
push（）：数据压入pushStack栈中；
pop()：但当我们取数据时，不能直接从pushStack中取数据，因为要取的数据位于pushStack的底部，所以可以将pushStack中的数据倒入popStack中，这样来，数据就进行了反转，结合下图；
top（）：方法就是查看队列首元素，不取出，与pop（）基本完全一样。

还有要注意的是：popStack栈为空时，就需要倒数据了。

代码如下：

public class MyQueue {
    Stack<Integer> pushStack;
    Stack<Integer> popStack;
    public MyQueue() {
        // do intialization if necessary
        pushStack=new Stack<>();
        popStack=new Stack<>();
    }
    //入队列
    public void push(int element) {
        // write your code here
        pushStack.push(element);
    }
    //取队列元素
    public int pop() {
        // write your code here
        if(popStack.isEmpty()){//如果popStack为空，则倒数据
            if(pushStack.isEmpty()){
                throw new RuntimeException("队列为空，无法取出数据");
            }
            while (!pushStack.isEmpty()){
                popStack.push(pushStack.pop());
            } 
        }
        return popStack.pop();
    }
    //查看队列首元素
    public int top() {
        // write your code here
        if(popStack.isEmpty()){//如果popStack为空，则倒数据
            if(pushStack.isEmpty()){
                throw new RuntimeException("队列为空，无法取出数据");
            }
            while (!pushStack.isEmpty()){
                popStack.push(pushStack.pop());
            } 
        }
        return popStack.peek();
    }
}