232.用栈实现队列

代码

class MyQueue {
    //定义两个栈实现队列
    Stack<Integer> stack1;
    Stack<Integer> stack2;  

    //初始化（在堆里）
    public MyQueue() {
        stack1 = new Stack<>();//负责入队
        stack2 = new Stack<>();//负责出队
    }
    
    //将元素 x 推到队列的末尾，即x入栈
    public void push(int x) {
        stack1.push(x);
    }
    
    //从队列的开头移除并返回元素
    public int pop() {
        //如果stack2有元素，就直接弹出，否则需要将stack1的元素转移到stack2之后再弹出
        dumpStack1();
        return stack2.pop();
    }
    //返回队列开头的元素
    public int peek() {
        dumpStack1();
        return stack2.peek();
    }
    
    //boolean empty() 如果队列为空，返回 true ；否则，返回 false
    public boolean empty() {
        //两个栈都为空，队列才为空
        return stack1.isEmpty() && stack2.isEmpty();
    }

    //如果stack2为空，那么将stack1中的元素全部放到stack2中
    private void dumpStack1(){
        if(stack2.isEmpty()){//如果stack2为空
            while(!stack1.isEmpty()){//stack1不为空时
                stack2.push(stack1.pop());
            }
        }
    }
}

/**
 * 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();
 */

元素出队列的时候，如果输出栈没有元素，就应该把输入栈中的全部元素导入到输出栈，再进行出栈。
刚开始没看出pop()和peak()两个差在哪里，好像都一样，不过用下面C++代码来看应该就清楚一些：

 /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
        if (stOut.empty()) {
            // 从stIn导入数据直到stIn为空
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    /** Get the front element. */
    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
        return res;
    }