题目描述

• 经典题了，貌似现在面试也有点喜欢问，今天补补题！
• 要实现均摊时间复杂度O(1)噢
  

思路 & 代码

• 用两个栈来实现：输出栈 & 输入栈
• 输出栈 out：负责 pop、peek
• 输入栈 in：负责 push
• 关键点：in.size() + out.size() == MyQueue.size()，也就是队列元素分布在两个栈中
• peek & pop：会有一个倒栈处理，把 in 的内容全倒入 out 中。

/**
    * 要点：in.size() + out.size() == MyQueue.size()
*/

class MyQueue {
    Stack<Integer> in;
    Stack<Integer> out;

    /** Initialize your data structure here. */
    public MyQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        in.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        // 出栈空，入栈导入
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
        return out.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
        return out.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return in.isEmpty() && out.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();
 */

更新版

• 换成 ArrayDeque()

class MyQueue {
    ArrayDeque<Integer> in;
    ArrayDeque<Integer> out;

    public MyQueue() {
        in = new ArrayDeque<>();
        out = new ArrayDeque<>();
    }
    
    public void push(int x) {
        in.push(x);
    }
    
    public int pop() {
        if(out.isEmpty()) {
            while(!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.pop();
    }
    
    public int peek() {
        if(out.isEmpty()) {
            while(!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.peek();
    }
    
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}