資料結構-堆疊&佇列

考研相關文章參考資料為 wjungle 大神提供的筆記

Stack

• 具有 LIFO 性質之有序串列，插入元素之操作為 push，刪除元素之操作為 push，且兩者發生於同一端，稱為頂端 (top)

Stack Permutation

• 給予 $n$ 個資料依序 push 進入 stack，並且在過程中可以進行任意合法的 pop 將資料輸出，在此模式下所產生的所有輸出之排列組合
  • ex: $a,b,c$ 之 Stack Permutation:
    • abc, acb, bac, bca, cab, cba
    • 共 5 種
• $n$ 個資料之 Stack Permutation 個數:
  • $\frac{1}{n + 1}C_{n}^{2n}$
• 與下列問題之個數相同 (卡塔蘭數):
  • $n$ 個 nodes 可以形成的不同二元樹個數
  • $n$ 組 “(” 及 “)” 之合法配對個數
  • $(n + 1)$ 個 matrix 相乘之所有乘法組合個數

Infix, Postfix, Prefix 轉換

計算題型作法

• 括號法

  • Infix 轉 Postfix (Prefix)
  • 對 Infix 加上完整的括號配對
  • 用 Operator 取代最近的左 (右) 括號
  • 刪除左 (右) 括號

• Operator 之優先權高低 (由高到低)

Operator	結合性	Binary/Unary
“(”, “)”
- (負號)		Unary
$\uparrow$, **, $, ^	右結合	Binary
*, /	左結合	Binary
+, -	左結合	Binary
$>,<,\geq,\leq,==,\neq$ (關係)	左結合	Binary
~ (否定)		Unary
AND, OR	左結合	Binary
= (Assign)	右結合

Queue

• 具有 FIFO 性質之有序串列，插入元素在尾端 (rear) 之操作為 enqueue，刪除元素在 前端 (front) 之操作為 dequeue，且兩者發生於同一端，稱為頂端 (top)

分類

• FIFO Queue
• Priority Queue
  • 不一定遵守 FIFO 性質，但是支持:
    • 插入任意權值元素
    • 刪除最大 (or 小) 權值之元素
  • 資料結構: Heap
• Double-ended Queue
  • Queue 的任意兩端皆可插入與刪除元素
• Double-ended Priority Queue
  • 支持:
    • 插入任意權值元素
    • 刪除最大權值之元素
    • 刪除最小權值之元素
  • 資料結構: min-max Heap, Deap, SMMH