面试题 03.04. 化栈为队

解题思路

用两个栈来实现一个队列
1.队列的特性是先进先出，后进后出
2.题意分析：一个栈用来push操作，一个栈用来pop操作，peek操作也是第二个栈，empty操作就是判断第一个栈是否为空
3.每次pop或者peer时，需要先把pop栈清空，然后将push栈出栈，入栈到pop栈，此时相当于push栈中元素顺序颠倒，此时pop栈进行pop或者peer操作，即为队首元素
4.题意中设定，假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作），所以pop或者peer操作时不需要判断栈是否为空

解题遇到的问题

无

后续需要总结学习的知识点

1.用liist或者deque去实现？
2.deque源码如何实现的？

##解法
import java.util.Stack;

class MyQueue {
    Stack<Integer> pushStack = null;
    Stack<Integer> popStack = null;

    /** Initialize your data structure here. */
    public MyQueue() {
        pushStack = new Stack<Integer>();
        popStack = new Stack<Integer>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        pushStack.push(x);
        popStack.clear();
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        popStack.clear();

        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }

        int resunt = popStack.pop();
        while (!popStack.isEmpty()) {
            pushStack.push(popStack.pop());
        }
        return resunt;
    }

    /** Get the front element. */
    public int peek() {
        popStack.clear();
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
        int resunt = popStack.peek();
        while (!popStack.isEmpty()) {
            pushStack.push(popStack.pop());
        }

        return resunt;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return pushStack.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */