用两个栈实现队列：下述代码的时间复杂度为O(1)还是O(N)？

我用两个栈实现了队列，请问下述代码的时间复杂度是O(1)还是O(N)？这是一道LeetCode题目。

class MyQueue {

    Stack<Integer> input;
    Stack<Integer> output;
    
    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }
    
    public void push(int x) {
        input.push(x);
    }
    
    public int pop() {
        int val = peek();
        output.pop();
        return val;
    }
    
    public int peek() {
        if(output.isEmpty()){
            while(!input.isEmpty())
                output.push(input.pop());
        }
        return output.peek();
    }
    
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

时间复杂度分析 #

• push操作：直接向input栈压入元素，单次操作时间复杂度为O(1)。
• empty操作：仅判断两个栈的空状态，时间复杂度为O(1)。
• peek和pop操作：需要区分单次最坏情况与摊还时间复杂度：
  • 单次最坏情况：当output栈为空时，需将input栈内所有元素转移至output栈，此时时间复杂度为O(N)（N为当前队列元素总数）。
  • 摊还时间复杂度：每个元素只会被从input栈转移到output栈一次，后续的peek或pop操作均直接操作output栈，耗时O(1)。将转移的总耗时平摊到每个元素的操作上，每个操作的摊还时间复杂度为O(1)。

综上，这个实现的所有操作摊还时间复杂度均为O(1)，这也是LeetCode第232题「用栈实现队列」的标准最优解法。

内容的提问来源于stack exchange，提问作者user2494912