Stack and Queue

前言

紀錄 Stack 與 Queue 的特性和實現方式

Stack

Last in first out (LIFO)

Blanced Brackets Example

經典問題 : Balanced Brackets，判斷括號是否有對稱

"([])[]()"    Balanced
"((([])))()"  Balanced
"([]]()"      Unbalanced
"]["          Unbalanced
"("           Unbalanced

1. 先把左括號放進 Stack (, [
2. 如果碰到右括號，判斷是哪種右括號 ), ]，是否跟目前 Stack 最上面存的左括號有 match
3. 沒有 match 則此字串非 balanced，直接結束檢查

IsBalanced (str)
Stack stack
for char in str:
  if char in ['(', '[']:
    stack.Push(char)
  else:
    if stack.Empty():   // 字串第一個就是右括號
      return false  

    top ← stack.Pop()   // 把stack最上面的左括號拿出來比對

    if (top  = '[' and char != ']') or (top = '(' and char != ')'):  // 左括右括不match
      return false

  return stack.Empty()   
  // 如果左括號數量 > 右括號數量, 迴圈結束stack不會是空的, 所以可直接看stack是否為空來判斷

實作 Stack 的方式

Array

用一個數值不斷紀錄最後一個放的元素其index的位置

• 每push一次，top++
• Pop的位置就是top目前存的index，每pop一次，top–
• Pop前需檢查top是否為0

Array 每次新增元素都只能從後面新增

可以把 Array 左右倒過來看，變成從右到左是index 0n，ea 對應到 index 0~4

所以 top 就是紀錄 Array 不為空的長度

用 Array 實作 Stack 的缺點大概就是大小一開始是固定的
但如果是 C++ 或 JAVA 這類函式庫強大的語言，其陣列型態就能用動態增加的方式 (C++: vector, JAVA: ArrayList)

Linked List

Linked List的實作方式我覺得寫起來相對容易

就是PushFront()和PopFront()，每次都從head的地方新增與刪除

Queue

First in First out (FIFO)

實作 Queue 的方式

Array

循環即可

用 read 紀錄前面的 index，write 紀錄下一個要被填的 index

• 當Dequeue的時候，read++
• 當Enqueue的時候，write++
• write > Array size的時候，就讓wirte從index 0重新開始

如果 write++ == read 時，不能 Enqueue，因為這種情況下不能確定 Queue 是空的

判斷 Queue是否為空 -> read == write 時

Linked List

使用 Linked List 實作 Queue 也比 Array 來得容易些

除了讓 head 指向第一筆資料，再用 tail 指向最後一筆資料，不斷紀錄著 List 的頭尾

• 每次都從後面新增資料，PushBack()
• 每次都從前面移除資料，PopFront()