Eisen 筆記

#232. Implement Queue using Stacks

題目描述

使用2個堆疊(Stack)實作一個先進先出(FIFO)的佇列(Queue)。 實作出的佇列需要滿足一個基本的佇列所具備的功能(push、peek、pop、empty)。

實作MyQueue類別。

  • void push(int x) 從佇列尾端放入一個元素x。
  • int pop() 移除佇列前端的元素並且回傳它。
  • int peek() 回傳佇列前端的元素。
  • boolean empty() 如果佇列沒有任何元素在內，回傳true，反之則回傳false。

備註：

  • 你只能使用堆疊的基本功能，也就是只能使用push、peek、pop、size以及empty等功能。
  • 根據你使用的程式語言，堆疊可能不會在基礎函式庫中提供，你可以使用列表(list)或者雙端佇列(deque)，用來模擬推疊的基本功能。

限制條件

  1. 1 <= x <= 9
  2. 單次測試的函式調用最多100次。
  3. 每個pop和peek的呼叫都必須是可行的。

解題思路

這一題的限制條件3的意思是當pop和peek被呼叫時，都必須有元素可以讓他們呼叫，也就是不能在佇列為0的時候呼叫。

平均O(n)

Stack的特性是先進後出，Queue的特性是先進先出，要達成先出的順序的話，Stack內的元素順序必須要反過來，2個Stack剛好可以做到這一點。

public class MyQueue {
    Stack main;
    Stack reverse;

    public MyQueue() {
        main = new Stack();
        reverse = new Stack();
    }
    
    public void Push(int x) {
        while(main.Count!=0){
            reverse.Push(main.Pop());
        }
        reverse.Push(x);
        while(reverse.Count!=0){
            main.Push(reverse.Pop());
        }
    }
    
    public int Pop() {
        return (int)main.Pop();
    }
    
    public int Peek() {
        return (int)main.Peek();
    }
    
    public bool Empty() {
        return main.Count==0;
    }
}

複雜度分析：

  • 時間複雜度：
    • Stack的多數情況下Push是O(1)，而在實作Push時，需要將元素從main搬移到reverse，總共會搬移n個元素，因此時間複雜度是O(n)。
    • Stack的Pop為O(1)，因此實作出Pop是O(1)。
    • Stack的Peek是O(1)，因此實作出Peek是O(1)。
    • Stack的Count是O(1)，因此實作出的Empty是O(1)。
  • 空間複雜度：等於放入的元素數量，所以是O(n)。

Follow-up

你可以讓實作出來的佇列的攤銷後的時間複雜度為O(1)嗎？ 換句話說，就算其中有個函式運算花費的時間特別長，調用n次函式後的總時間仍然會是O(n)。

攤銷 O(1)

攤銷(Amortized)的意思是將昂貴的時間成本用多次的行為操作來平均，避免集中到某一次而讓最壞的效能產生的情況。 舉例來說，如果我們要一次創建一個可以容納n個元素的陣列，那將會花費掉O(n)的時間。
但是如果我們改成使用動態陣列，最開始只需要創建一個最小的陣列，當插入的時間超過當前陣列的大小時，我們創造一個新的陣列，通常為當前陣列的2倍大，接著將原先陣列中的元素搬移到這個新陣列中，最後再放入後面的元素，這個策略可以讓創造容納n個元素的陣列所花費掉的O(n)的時間，分攤到每一個動態增加陣列的操作上，當把n個元素都放入陣列後，O(n)則會被平均成O(1)。

如果覺得很複雜的話，可以想像成0利率分期付款，比起一次付一大比錢，不如分期付款，讓負債平均分配到每個月上，降低一次性的負擔。

從上個例子來看，由於每呼叫一次Push就需要透過搬移來調整元素順序，因此時間成本會集中在Push身上，每一次Push都會花到O(n)的時間。

使用攤銷的概念，把搬移的動作放到Peek上，當呼叫Peek時，如果output是空的，就把input的元素搬移過去，如果output不是空的，就直接取得output的元素回傳。 這樣的調整讓Push的時間複雜度變成O(1)，而Peek的時間複雜度則是在需要搬移的時候為O(n)，不需要搬移的時候為O(1)，則所有Peek的成本平均下來是O(n)/n次，所以攤銷後為O(1)。

public class MyQueue {
    Stack input;
    Stack ouput;

    public MyQueue() {
        input = new Stack();
        ouput = new Stack();
    }
    
    public void Push(int x) {
        input.Push(x);
    }
    
    public int Pop() {
        Peek();
        return (int)ouput.Pop();
    }
    
    public int Peek() {
        if(ouput.Count==0){
            while(input.Count!=0){
                ouput.Push(input.Pop());
            }
        }
        if(ouput.Count!=0) return (int)ouput.Peek();
        return 0;
    }
    
    public bool Empty() {
        return input.Count==0 && ouput.Count==0;
    }
}

複雜度分析：

  • 時間複雜度：
    • Stack的多數情況下Push是O(1)，因此時間複雜度是O(1)。
    • Stack的Pop為O(1)，實作時會呼叫Peek()，Peek攤銷後的時間複雜度為O(1)，因此實作出Pop是O(1)。
    • Stack的Peek是O(1)，實作出的Peek，平常是O(1)，搬移時會花費O(n)，因此平均攤銷後是O(1)。
    • Stack的Count是O(1)，因此實作出的Empty是O(1)。
  • 空間複雜度：等於放入的元素數量，所以是O(n)。

學習重點

  • Queue的特性。
  • Stack的特性。
  • 攤銷(Amortized)的概念。
Last Updated:
Contributors: eisen