現(xiàn)在我們創(chuàng)建兩個棧，分別是 out 和 in，用作處理「輸出」和「輸入」兩個操作。

其實就是兩個棧來回的「倒騰」

而對于「何時倒騰」決定了是 O(n) 解法 還是 均攤 O(1) 解法。

1 先來說 O(n) 解法

我們創(chuàng)建兩個棧，分別是 out 和 in：

• in 用作處理輸入操作 push()，使用 in 時需確保 out 為空
• out 用作處理輸出操作 pop() 和 peek()，使用 out 時需確保 in 為空

class MyQueue {
    Deque<Integer> out, in;
    public MyQueue() {
        in = new ArrayDeque<>();
        out = new ArrayDeque<>();
    }
    
    public void push(int x) {
        while (!out.isEmpty()) in.addLast(out.pollLast());
        in.addLast(x);
    }
    
    public int pop() {
        while (!in.isEmpty()) out.addLast(in.pollLast());
        return out.pollLast();
    }
    
    public int peek() {
        while (!in.isEmpty()) out.addLast(in.pollLast());
        return out.peekLast();
    }
    
    public boolean empty() {
        return out.isEmpty() && in.isEmpty();
    }
}

• 時間復雜度：O(n)
• 空間復雜度：O(n)

2 再來說均攤 O(1) 解法

事實上，我們不需要在每次的「入?！购汀赋鰲！共僮髦卸歼M行「倒騰」。

我們只需要保證，輸入的元素總是跟在前面的輸入元素的后面就行啦，而輸出元素總是最早輸入的那個元素即可。

我們可以通過調整「倒騰」的時機來確保滿足上述要求，但又不需要發(fā)生在每一次操作中：

• 即只有在「輸出棧」為空的時候，才發(fā)生一次性的「倒騰」

//java的版本
class MyQueue {
    Deque<Integer> out, in;
    public MyQueue() {
        in = new ArrayDeque<>();
        out = new ArrayDeque<>();
    }
    
    public void push(int x) {
        in.addLast(x);
    }
    
    public int pop() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.addLast(in.pollLast());
        }
        return out.pollLast();
    }
    
    public int peek() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.addLast(in.pollLast());
        }
        return out.peekLast();
    }
    
    public boolean empty() {
        return out.isEmpty() && in.isEmpty();
    }
}

• 時間復雜度：pop() 和 peek()兩個操作都是均攤，所以是O(1)
• 空間復雜度：O(n)

你可能沒聽過均攤復雜度

3 我說明下

我們可以用另外一個例子來理解「均攤復雜度」，你就明白了，大家都知道「哈希表」的底層是通過數(shù)組來實現(xiàn)的。

正常情況下，我們要算元素在哈希桶的位置，然后放入哈希桶里面，復雜度為 O(1)，我們可以通過簡單的“拉鏈法”搭配「頭插法」方式來解決哈希沖突的問題。

但是當某次元素插入后，「哈希表」能達到擴容的閾值，那么需要對底層所使用的數(shù)組進行擴容，這個復雜度是 O(n)

很顯然「擴容」操作不會發(fā)生在每一次的元素插入中，擴容的 O(n) 都會伴隨著 n 次的 O(1)，換句話說 O(n) 的復雜度會被均攤到每一次插入當中去，所以哈希表插入仍然還是 O(1) 的。

同樣的道理，我們的「倒騰」也不是發(fā)生在每一次的「輸出操作」中，而是集中發(fā)生在一次「輸出棧為空」的這個時候，所以 pop 和 peek 都是均攤復雜度為 O(1) 的操作。

由于本題的調用次數(shù)它只有 100 次，所以鐵定是一個人均 100% 的算法（也就是花費 0 ms）?? ??

但是我們需要對操作進行復雜度分析進行判斷，而不是看時間來判斷自己是不是均攤 O(1) 哈 ~