今日題目

題目連結：232. Implement Queue using Stacks
題目主題：Stack, Design, Queue

此題目主要是來了解Queue，在瞭解了Stack的運作方式以後，接下來要分享的是Queue的運作方式。

簡單說說 Queue

Queue（隊列）是一種先進先出 ( FIFO ) 的資料結構，最新的資料永遠都是最後才被取出，也就是先進去的資料會被優先拿出來，使用的方式及過程如下圖。

可以想像 Queue 是一個圓角方形空間，從上圖中範例有新的資料進去時，會從前面進去一筆新的資料，每次取出資料都會從後面取得最新的資料，因此 3 雖然是最新進去的，但是一直到最後才會輪到他被取出。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目的目標是用兩個Stack來實現Queue的功能，需實現的功能分別為：

1. push：新增一筆資料。
2. pop：取得一筆資料，並且將此資料移除。
3. peek：取得一筆資料。
4. empty：確認是否為空。

約束：

• 1 <= x <= 9
• 最多執行100次方法（push、pop、peek、empty）
• 使用 pop 和 peek 會是有效的狀態下執行

範例1：

輸入:
["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]
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 在初始化時宣告 stack1 跟 stack2 兩個Stack
2. stack1 是用來push資料
   • 每次使用時，會先把 stack2 倒過來放進 stack1 中
   • 確定 stack2 空了以後，再放入新資料
3. stack2 是用來pop資料
   • 每次使用時，會先把 stack1 倒過來放進 stack2 中
   • 確定 stack1 空了以後，在從stack2取出資料
4. peek最新資料時
   • 若資料在stack1，取得最前面的資料
   • 若資料在stack2，取得最後面的資料
5. empty 需檢查 stack1 跟 stack2 是否為空

圖解過程

1. __init__(self) 初始化時，宣告兩個Stack
   

2. push(self, x: int) -> None
   假設資料在 stack2 = [3, 5, 4, 2]
   現在要放入 x = 1，使用stack1來新增資料。
   
   如上圖，因為 Queue 是 FIFO，所以不能直接放在 stack2 中 2 的後面，要放在 3 的前面，所以才會把它倒過來放到 stack1 後再放進 x 資料，綠色方塊資料是從 stack2 倒過來後放進 stack1 的資料，之後在把新的 x 紅色方塊資料放進 stack1 中。

3. pop(self) -> int
   從上步驟繼續 stack1 = [2, 4, 5, 3, 1]
   使用stack2來取得資料，並移除取出來的資料。
   1 是最後進去的，Queue 是 FIFO 所以現在要取得的是最先進去的 2。
   
   如上圖，綠色方塊資料是從 stack1 倒過來後放進 stack2 的資料，之後在把最先放進來的 2 取出來。

4. peek(self) -> int
   從上步驟繼續 stack2 = [1, 3, 5, 4]
   這邊只是要知道 接下來pop要取得的資料是什麼，因此現在應該會是顯示 4 。
   （ 下圖我們把 stack1 跟 stack2 的狀況都標出來，實際上絕對不會有兩個stack都有資料的狀況存在 ）
   

5. empty(self) -> bool
   需要檢查兩個stack都是空的，才是真的空。
   以下圖範例來說，這樣的狀態會回傳True。
   

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class MyQueue:
    # 初始化 需要兩個Stack
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    # stack1 是用來新增資料用的
    # 使用前會先把 stack2 倒過來到 stack1 在新增
    def push(self, x: int) -> None:
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        self.stack1.append(x)
        
    # stack2 是用來取得資料用
    # 使用前會先把 stack1 倒過來到 stack2 在取得資料
    def pop(self) -> int:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    # 看目前資料在 stack1 還是 stack2 中
    # 若在 stack1 中，會從最前面取得資料
    # 若在 stack2 中，會從最後面取得資料
    def peek(self) -> int:
        return self.stack1[0] if self.stack1 else self.stack2[-1]
    
    # stack1 跟 stack2 都是空的才是真的空
    def empty(self) -> bool:
        return not self.stack1 and not self.stack2

希望您今天能瞭解到...

1. Queue基礎概念
2. 232.Implement Queue using Stacks 解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：225. Implement Stack using Queues