iT邦幫忙

2021 iThome 鐵人賽

DAY 5
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 5

【第五天 - Queue 題目分析】

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

  • 題目敘述
  • 如何利用兩個 stack 完成 Queue 的概念?
  • 邏輯很簡單,如下:
    1. 先準備兩個 stack 的盒子 ( 下方封死,只能由上方放入和取出 )
      • 兩個stack
    2. 假設有三個馬克杯,分別為小明、小美、小雅,依序放入 stack 1,當你要根據 Queue 也就是先進先出的順序,拿出最早放入的杯子(小明的杯子),此時,把stack 1 內的杯子逐一放到 stack 2,他就會從上到下依照 小明→小美→小雅的順序排放,接著再拿 stack 2 的杯子,就會得到小明的杯子了
      • stack1倒到stack2
  • 在 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

上一篇
【第四天 - Queue 介紹】
下一篇
【第六天 - Bubble Sort 介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言