先簡單回顧一下，今天預計分析的題目：

• 
• 如何利用兩個 stack 完成 Queue 的概念?
• 邏輯很簡單，如下：
  1. 先準備兩個 stack 的盒子 ( 下方封死，只能由上方放入和取出 )
     • 
  2. 假設有三個馬克杯，分別為小明、小美、小雅，依序放入 stack 1，當你要根據 Queue 也就是先進先出的順序，拿出最早放入的杯子(小明的杯子)，此時，把stack 1 內的杯子逐一放到 stack 2，他就會從上到下依照 小明→小美→小雅的順序排放，接著再拿 stack 2 的杯子，就會得到小明的杯子了
     • 
• 在 python 的程式中，就會這樣實作幾個 function

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
#       分別宣告兩個 stack，命名為 stack1 與 stack2
#       stack1 放存進來的值
#       stack2 是把 stack1 的值逐一放入stack2，變成 Queue 的形式(最早放的會在最上面)
        self.stack1 = []
        self.stack2 = []


    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
#       呼叫 push function 時，會把變數 x 放進 stack1 中
        self.stack1.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
#       呼叫 pop function 時，要拿出最早放入的值，所以先看看 stack2 有沒有值 ( stack2 是已經變成 Queue 排列的順序)
#       stack2 若是空的，就把 stack1 的值逐一放入 stack2
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
#       回傳 stack2 最上面的值
        return self.stack2.pop()
        

    def peek(self) -> int:
        """
        Get the front element.
        """
#       跟上面 pop function 一樣，判斷stack2 是不是空的，若是空的，就把 stack1 的值逐一放入 stack2
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
#       由於是 peek，只會看最前面是什麼，不會把值拿出來，所以拿出來後還要儲存回去        
        top = self.stack2.pop()
        self.stack2.append(top)
        return top

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
#       檢查 stack1 跟 stack2 是不是空的
        if self.stack1 or self.stack2:
            return False
        else:
            return True
       

• 其中幾個 function 有更為簡潔/不同的寫法

    def peek(self) -> int:
#       判斷 stack2 是否為空，若不為空，則回傳 stack中 最後一個值 (也就是最上面的)
#       若 stack2 為空，則回傳 stack1 最底下的值 (最先放的值)

        if self.stack2:
            return self.stack2[-1]
        else:
            return self.stack1[0]


    def empty(self) -> bool:
#       看 stack 的長度，若為 0 則代表 stack 為空
        if len(self.stack1)==0 and len(self.stack2)==0:
            return True
        return False

• 此題若不按照題目要求，使用兩個 stack，也可以只使用一個 python list 的結構完成 (我們之前都是使用 list 結構，來模擬 stack 的概念)
• 由於 python 有些內建的 function pop，並且可以指定要拿出哪一個位置的資料，所以我們可以利用一個 list 結構模擬 stack 與 Queue，但是其他語言不一定有如此方便的功能，所以建議大家還是要學好 stack 與 queue 的概念，以便能夠在不同語言也能夠自己實作

class MyQueue:

    def __init__(self):
        self.stack3 = []

    def push(self, x: int) -> None:
        self.stack3.append(x)

    def pop(self) -> int:
        return self.stack3.pop(0)
        
    def peek(self) -> int:
        return self.stack3[0]

    def empty(self) -> bool:
        if self.stack3:
            return False
        return True

• 順帶一提，python 有 Queue 的 library，只要 import queue 就可以使用
  • 可以參考：https://docs.python.org/zh-cn/3/library/queue.html