ADT (Abstract Data Type)

介紹

ADT 是抽象化過的資料型別， 定義的是型別的操作方式， 不限定實做方法， 藉此使用者只要知道操作界面即可， 不需要了解到實做細節， 當實做改變時也不會受影響而需要重新撰寫程式。

Stack (LIFO)

Stack 保證的是 LIFO （Last In, First Out）， 也就是後進先出， 需要有以下操作：

  • push：放入新資料

  • pop：移除最新的資料並回傳

其他可能的擴充：

  • top：查看最新的資料

  • empty：回傳是否為空的

可能的實做方式：

  • Array

  • Singly Linked List

Queue (FIFO)

Queue 保證的是 FIFO （First In, First Out）， 也就是先進先出， 需要有以下操作：

  • enqueue：放入新資料

  • dequeue：移除最舊的資料並回傳

其他可能的擴充：

  • front：查看最舊的資料

  • empty：回傳是否為空的

可能的實做方式：

  • Linked List

    • Doublely Linked List

    • Singly Linked List （額外紀錄頭尾的指標來增加效率）

  • Circular Buffer

  • Deque （把 Queue 當成 Deque 的特例）

Deque (Double-ended Queue)

Deque 是比 Queue 更有彈性的結構， 可以從頭或尾加入或刪除， 需要有以下操作：

  • insert_front：從開頭插入新資料

  • insert_back：從結尾插入新資料

  • remove_front：從開頭刪除資料

  • remove_back：從結尾刪除資料

其他可能的擴充：

  • front：查看結尾的資料

  • back：查看開頭的資料

  • empty：回傳是否為空的

可能的實做方式：

  • Doubly Linked List

  • Dynamic Array （Array Deque）

List

List 是用來表示有限的資料（無限的資料會用 Steam 表示）， 而且資料的插入順序會被保存並且可以重複， 需要有以下操作：

  • append：在尾端插入新資料

  • prepend：在開頭插入新資料

  • head：回傳第一筆資料

  • tail：回傳除了第一筆資料外的剩餘資料

其他可能的擴充：

  • empty：回傳是否為空的

可能的實做方式：

  • Linked List

  • Array

  • Self-balancing Binary Search Tree

Set

Set 是用來表示有限的資料， 而且資料的插入順序 不會 被保存並且 不會 重複， 需要有以下操作：

  • add

  • remove

  • is_element_of

其他可能的擴充：

  • union

  • intersection

  • difference

  • subset

  • is_empty

  • size/cardinality

  • iterate

  • enumerate

  • pop

  • pick

  • map

  • filter

  • fold

  • clear

  • equal

  • hash

  • sum

  • collapse

  • flatten

  • nearest

  • min

  • max

可能的實做方式：

  • List （比較沒效率）

  • Hash Table

  • Self-balancing Binary Search Tree

    • Red-Black Tree

  • Trie

Multiset

MultiSet 類似 Set， 但是允許重複的資料， 依照需求可能會把相同的值視為同一個資料， 並另外用計數器做紀錄， 或是視為相同值但不同的資料， 一樣把資料存進去， 而 MultiSet 儲存資料的順序可以是有序也可以是無序的。

Map (Dictionary) (Associative Array)

Map 是用來表示一連串 (key, value) pairs， 需要有以下操作：

  • add：

  • remove

  • modify

  • lookup

其他可能的擴充：

  • iterate

  • iterate_values

  • iterate_keys

可能的實做方式：

  • Hash Table

  • Search Tree

    • Self-balancing Binary Search Tree

    • Unbalanced Binary Search Tree

  • Sequential Container

Multimap

Multimap 是用來表示一連串 (key, value) pairs， 跟 Map 的差別在於一個 key 可以對應到多個 value， 需要有以下操作：

  • add：

  • remove

  • modify

  • lookup

其他可能的擴充：

  • iterate

  • iterate_values

  • iterate_keys

可能的實做方式：

  • Map with List

  • Set as Map value

Priority Queue

Priority Queue 類似一般的 Stack 或 Queue， 但是額外加了 Priority 的性質， Priority 比較高的資料會排比較前面， 以 Stack 來說就是越晚加入的資料 Priority 越高， 以 Queue 來說就是越早加入的資料 Priority 越高， 但是 Priority Queue 則是可以客製化 Priority 的決定方式， 需要有以下操作：

  • insert_with_priority

  • pull_highest_priority_element

其他可能的擴充：

  • peek

  • pull_lowest_priority_element

可能的實做方式：

  • Unordered Array （沒效率）

  • Heap

  • Self-balancing Binary Search Tree

另外 Priority Queue 也可以用於排序上面， 把資料放入 Priority Queue 後再取出來， 就會依照順序排好， 對照：

Sorting

Priority Queue

Best

Average

Worst

Heapsort

Heap

n log(n)

n log(n)

n log(n)

Smoothsort

Leonardo Heap

n

n log(n)

n log(n)

Selection Sort

Unordered Array

n^2

n^2

n^2

Insertion Sort

Ordered Array

n

n^2

n^2

Tree Sort

Self-balancing Binary Search Tree

n log(n)

n log(n)

n log(n)

DEPQ (Double-ended Priority Queue) (Double-ended Heap)

DEPQ 類似 Priority Queue， 但是額外提供有效率的方式可以移除最大或最小的值， 不像 Priority Queue 只有一邊是有效率的，

需要有以下操作：

  • insert

  • get_min

  • get_max

  • remove_min

  • remove_max

其他可能的擴充：

  • size

  • is_empty

可能的實做方式：

  • Heap

    • Min-Max Heap

    • Pairing Heap

  • Self-balancing Binary Search Tree

應用：

  • External Sorting

Graph

Graph 是一種實做了數學中的有向圖或無向圖的 ADT， 儲存了許多節點和路徑， 需要有以下操作：

  • adjacent

  • neighbors

  • add_vertex

  • remove_vertex

  • add_edge

  • remove_edge

  • get_vertex_value

  • set_vertex_value

其他可能的擴充：

  • get_edge_value

  • set_edge_value

可能的實做方式：

  • Adjacency List

  • Adjacency Matrix

  • Incidence Matrix

參考