今日題目

題目連結：225. Implement Stack using Queues
題目主題：Stack, Design, Queue

瞭解完Stack跟Queue的概念後，最後再複習一題，上一題是用Stack實作Queue，這次題目是用Queue來實作Stack，這樣應該足夠對這兩種資料結構有更深的瞭解。

簡單說說 Follow-up

這次不講演算法資料結構，Stack跟Queue在前兩篇都提過了，在這邊多提一下關於LeetCode上面，平常如果有力氣時可以多做的事情Follow-up。

有些題目會有這一個項目，是給解題者額外更難的挑戰。以這題為例的話，原本題目解釋的目標是說，請用兩個Queue來實作Stack，但最後給你一個Follow-up問說，你可以用一個Queue來實作出Stack嗎？

本文最後會分享的是兩個Queue來實作的Stack，如果各位夥伴有空的話，可以再挑戰看看這一題的Follow-up，這題的挑戰其實並不難，建議可以玩玩看。

題目解說

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

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

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

約束：

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

範例1：

輸入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

輸出:
[null, null, null, 2, 2, false]

解釋:
輸入的第一個陣列會是幾個指令，第二個陣列是輸入的參數。
輸出就是使用指令後得到回應。
範例輸入的指令過程會像是下方這一段。
MyStack myStack = new MyStack();
myStack.push(1); // stack is: [1]
myStack.push(2); // stack is: [1, 2]
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

解題的想像

文字描述

1. 初始化時，宣告兩個Queue，分別為queue跟tmp_queue。
2. queue 可直接針對以下使用：
   • empty 檢查是否為空
   • push 直接放一筆資料進去
   • top 直接看拿最後一筆資料回傳
3. tmp_queue是暫存用的，在pop時才會使用到，每次pop時：
   • 將queue所有值一個一個放到tmp_queue中，直到剩一個值
   • 剩下的一個值，直接當pop回傳值，不用在放進暫存區
   • tmp_queue現有所有值再放回queue並清空
   • tmp_queue使用完後永遠保持空的狀態

圖解過程

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

2. push(self, x: int) -> None
   假設 push 了三次資料，分別是1, 2, 3。
   

3. top(self) -> int
   繼續上面的狀態，queue = [1, 2, 3]
   top，只需要顯示不需要取出，因此直接拿最後一筆當回傳值即可。
   

4. pop(self) -> int
   繼續上面的狀態，queue = [1, 2, 3]
   pop這邊分為三步驟來完成，如下圖。
   

   1. 會先把資料一筆一筆放進tmp_queue，直到剩一筆
   2. 最後這一筆是pop要回傳的資料
   3. 再從tmp_queue放回queue中，tmp_queue保持空的
   4. 最後回傳的值就是pop_value

5. empty(self) -> bool
   繼續上面的狀態，因拿出一筆資料，現在queue = [1, 2]
   因為tmp_queue永遠保持空的，檢查queue是否為空即可，此範例的結果會回False。
   

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

程式碼撰寫

from collections import deque

class MyStack:
    # 初始化 需要兩個Queue
    def __init__(self):
        self.queue = deque()
        self.tmp_queue = deque()
        
    # 直接用 queue 來新增資料
    def push(self, x: int) -> None:
        self.queue.append(x)

    # tmp_queue 是暫存用的
    # Queue是只能從最先進去的資料取得，因此把資料一個一個取出存到tmp_queue
    # 直到剩一個資料才是stack的pop要取出來的資料，stack要取得是最後一個進去的資料
    # 最後把tmp_queue的資料放回queue中，讓tmp_queue永遠保持空的
    def pop(self) -> int:
        while len(self.queue) >= 2:
            self.tmp_queue.append(self.queue.popleft())
        pop_value = self.queue.popleft()
        self.queue = deque(self.tmp_queue)
        self.tmp_queue.clear()
        return pop_value

    # 直接取得 queue 的最後一筆資料即可
    def top(self) -> int:
        return self.queue[-1]

     # 直接檢查 queue 是否為空即可，因為tmp_queue會確保保持空的
    def empty(self) -> bool:
        return not self.queue

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

1. Follow-up的挑戰
2. 更熟悉Queue及Stack用法
3. 225. Implement Stack using Queues 解題方法

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

Next：506. Relative Ranks