Stack & Queue

tags: 演算法 資料結構
HackMD Error: 404 error

課堂

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

擷取至: 老師的PPT

為什麼要有 Stack?

  • 編譯器(word、sublime)的 undo 。
  • 網頁瀏覽器中回到上一頁功能。
  • 任何遞迴(recursion)形式的演算法都可以用 Stack 改寫,例如 Depth-First Search(DFS,深度優先搜尋)

Stack 必須有的功能

  • Push(Data): 把資料放到最上面(最新)。
  • Pop: 把資料從最上面(最新)移除。
  • Top: 回傳最上面(最新)的資料。
  • IsEmpty: 確認stack 裡面是否有資料。
  • getSize: 回傳stack 裡的資料個數。

為什麼要有 Queue

  • 應用在其他演算法:
    • Bread-First Search | 廣度優先搜尋
    • Tree 的 Level-Order Traversal | 二元樹走訪
  • 作業係統被多個程式共享資源時(例如CPU、應表機、網站伺服器),一次只能執行一個需求,所以需要用 Queue 來安排執行順序。

Queue 必須有的功能

  • Push(Data): 把資料放到 Queue 的後面,並更新成新的 back。
  • Pop(dequeue): 把 front 所指向的資料從 Queue 中移除,並更新front。
  • getFront: 回傳 front 所指向的資資料。
  • getBack: 回傳 Back 所指向的資資料。
  • IsEmpty: 確認 Queue 裡是否有資料。
  • getSize: 確認 Queue 裡的資料個數。

外部資料

Queue

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

簡單來講就是 先插入的先刪除(First in first out | FIFO), 可用來實現 廣度優先搜尋(Breadth-first search | BFS).

  • Additions (又稱: Enqueues) always add to the back of the line
  • Removals (又稱: Dequeues) always remove from the front of the line

用 list 實現基本的 queue 功能

q = [] q.insert(0,v) #在頭的位置插入 q.pop() #刪除最後一個(先插入的)element

Stack:

後(新)插入的先刪除 (Last in first out | LIFO),可用在 深度優先搜尋(DFS | Depth-First Search)

用 list 實現基本的 stack 功能

stack = [] stack.append(v) #在最後面插入 stack.pop() #刪除最後一個(新插入的)element

參考

練習

Min Stack

題目: Leetcode | Min Stack

key point

  • 高清楚頭尾,要怎麼對應 linked-List 的head 和方向。
  • 主要的是 getMin()的實現,需要想一下。

Implement Queue using Stacks

題目: Leetcode | Implement Queue using Stacks

key point

  • 搞清楚題目要那些功能。