隊列實現(xiàn)棧（leetcode225）

題目描述：請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通隊列的全部四種操作（push、top、pop 和 empty）。

實現(xiàn) MyStack 類：

• void push(int x) 將元素 x 壓入棧頂。
• int pop() 移除并返回棧頂元素。
• int top() 返回棧頂元素。
• boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

注意：

• 你只能使用隊列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作。
  你所使用的語言也許不支持隊列。 你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列 , 只要是標(biāo)準(zhǔn)的隊列操作即可。

示例：

輸入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 2, 2, false]

解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

思路：

• 定義兩個隊列，一個主隊列，一個輔助隊列，模擬棧后進(jìn)先出。
• 當(dāng)入棧操作時，先將該數(shù)據(jù)入隊輔助隊列，然后主隊列內(nèi)容導(dǎo)入輔助隊列（while循環(huán)），最后將將主隊列和輔助隊列進(jìn)行交換。
• 其實，了解了上述思路（將當(dāng)前加入元素加到已經(jīng)按照棧排好的元素最前邊），我們只需要一個隊列即可。

復(fù)雜度分析

• 時間復(fù)雜度：入棧操作 O(n)，其余操作都是 O(1)。

  入棧操作需要將queue 1中的 n個元素出隊，并入隊 n+1 個元素到queue 2 ，共有 2n+1 次操作，每次出隊和入隊操作的時間復(fù)雜度都是 O(1)，因此入棧操作的時間復(fù)雜度是 O(n)。

  出棧操作和獲取棧頂元素對應(yīng)將 queue 1的前端元素出隊，時間復(fù)雜度是 O(1)。

  判斷棧是否為空操作只需要判斷queue 1是否為空，時間復(fù)雜度是 O(1)。

• 空間復(fù)雜度：O(n)，其中 n 是棧內(nèi)的元素。需要使用兩個隊列存儲棧內(nèi)的元素。

代碼實現(xiàn)：

class MyStack {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        queue2.offer(x);
        // 特別注意，while循環(huán)
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

使用一個隊列實現(xiàn)（將當(dāng)前加入的元素放在已經(jīng)是棧順序序列的最前邊，實現(xiàn)后進(jìn)先出原則而）

class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.offer(x);
        int cnt = queue.size();
        while (cnt-- > 1) {
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

棧實現(xiàn)隊列（leetcode232）

問題描述：請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應(yīng)當(dāng)支持一般隊列支持的所有操作（push、pop、peek、empty）：實現(xiàn) MyQueue 類：

• void push(int x) 將元素 x 推到隊列的末尾
• int pop() 從隊列的開頭移除并返回元素
• int peek() 返回隊列開頭的元素
• boolean empty() 如果隊列為空，返回 true ；否則，返回 false

說明：

• 你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標(biāo)準(zhǔn)的棧操作即可。

要求：

• 你能否實現(xiàn)每個操作均攤時間復(fù)雜度為 O(1) 的隊列？換句話說，執(zhí)行 n 個操作的總時間復(fù)雜度為 O(n) ，即使其中一個操作可能花費較長時間。

示例：

輸入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 1, 1, false]

解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路：

• 定義兩個棧用于數(shù)據(jù)的輸入和輸出。
• 當(dāng)進(jìn)行pop和poll操作時，如果輸出棧為空，那么將輸入棧數(shù)據(jù)全部移到輸出棧。所以，當(dāng)移到輸出棧中然后進(jìn)行輸出的時候（出隊列），就滿足先進(jìn)先出的結(jié)構(gòu)。

復(fù)雜度分析：

• 時間復(fù)雜度：push 和empty 為 O(1)，pop 和 peek 為均攤 O(1)。對于每個元素，至多入棧和出棧各兩次，故均攤復(fù)雜度為 O(1)。
• 空間復(fù)雜度：O(n)O(n)。其中 n是操作總數(shù)。對于有 n 次 push 操作的情況，隊列中會有 n 個元素，故空間復(fù)雜度為 O(n)。

代碼實現(xiàn)：

class MyQueue {

    private Deque<Integer> inStack;
    private Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<>();
        outStack = new LinkedList<>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    // 獲取棧中的元素時，需要檢查輸出棧是否為空
    public int pop() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    
    // 將輸入棧中的元素移到輸出棧
    private void inToOut() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

對于均攤復(fù)雜度的說明：參考@宮水三葉

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

• 正常情況下，計算元素在哈希桶的位置，然后放入哈希桶，即插入操作復(fù)雜度為 O(1)，假定是通過簡單的“拉鏈法”搭配「頭插法」方式來解決哈希沖突。
• 但當(dāng)某次元素插入后，「哈希表」達(dá)到擴(kuò)容閾值，則需要對底層所使用的數(shù)組進(jìn)行擴(kuò)容，這個復(fù)雜度是 O(n)
• 顯然「擴(kuò)容」操作不會發(fā)生在每一次的元素插入中，因此擴(kuò)容的 O(n) 都會伴隨著 n 次的 O(1)，也就是 O(n) 的復(fù)雜度會被均攤到每一次插入當(dāng)中，因此哈希表插入仍然是 O(1)的。

同理，我們不是發(fā)生在每一次的「輸出操作」中，而是集中發(fā)生在一次「輸出棧為空」的時候，因此 pop 和 peek 都是均攤復(fù)雜度為 O(1)的操作。

補(bǔ)充：Queue接口分析：add和offer區(qū)別，remove和poll方法到底啥區(qū)別

這些方法的主要區(qū)別在于，如果執(zhí)行失敗，是拋出異常還是返回值。

• queue的增加元素方法add和offer的區(qū)別在于，add方法在隊列滿的情況下將選擇拋異常的方法來表示隊列已經(jīng)滿了，而offer方法通過返回false表示隊列已經(jīng)滿了；在有限隊列的情況，使用offer方法優(yōu)于add方法；
• remove方法和poll方法都是刪除隊列的頭元素，remove方法在隊列為空的情況下將拋異常，而poll方法將返回null；
• element和peek方法都是返回隊列的頭元素，但是不刪除頭元素，區(qū)別在與element方法在隊列為空的情況下，將拋異常，而peek方法將返回null

總結(jié)：我們一般希望拋出返回值，優(yōu)先使用offer，poll和peek方法。