10.2 Python 常用資料結構

類似於 C++ STL，Python 也提供了許多資料結構（實際底層實作細節可能因編譯器而異）：

1. 順序容器：維持順序的容器。

   1. list：動態陣列，是我們最常用的資料結構之一，適合用於 $O(1)$ 的隨機存取。由於大多數演算法的時間複雜度會大於 $O(n)$，我們經常建立 list 來儲存各種資料或中間結果。因為尾部的新增或移除操作有 $O(1)$ 的複雜度，我們也可以將其當作堆疊（stack）使用。
   2. tuple：不可變的陣列，無法更改其中的元素或總長度。
   3. collections.deque：雙端佇列，是一種功能強大的資料結構，支援 $O(1)$ 的隨機存取，也支援 $O(1)$ 時間的頭尾新增或移除操作（因此可作為堆疊或佇列使用）。但它有些額外開銷，也可用來模擬雙向鏈結串列。

2. 容器適配器：基於其他容器實作的容器。

   1. heapq：最小堆（最小值優先的資料結構），基於 list 實作的堆結構。它支援在 $O(n \log n)$ 時間內排序陣列，$O(\log n)$ 時間插入任意值，$O(1)$ 時間獲取最小值，$O(\log n)$ 時間移除最小值。heapq 常用於維持資料結構並快速獲取最小值，但不支援自定義比較函式。因此，通常需要預先計算自定義值，並將 (自定義值, 索引) 的 tuple 儲存於 heapq 中，進行比較時會優先比較自定義值，若相同則比較插入順序。

3. 有序關聯容器：

   1. collections.OrderedDict：順序映射或順序表，注意這裡的 Ordered 與 C++ 中 map 的按大小排序不同，而是按照插入的先後順序排序。OrderedDict 非常適合用來實現 LRU（最近最少使用）。

4. 無序關聯容器：

   1. set：雜湊集合，可以在 $O(1)$ 的時間內快速插入、查詢和刪除元素，常用於快速查詢某個元素是否存在於容器中。
   2. dict：雜湊映射或雜湊表，在 set 的基礎上增加了鍵值對的映射關係，可以對每個鍵（key）儲存對應的值（value）。在某些情況下，如果鍵的範圍已知且較小，我們也可以用 list 代替 dict，用索引位置表示鍵，用每個位置的值表示對應的值。
   3. collections.Counter：計數器，是 dict 的一種特殊版本，可以直接傳入一個 list，並對其中的每個元素進行計數統計，鍵為元素值，值為該元素出現的頻次。可以用來作為多重集合。

同樣地，因為這並不是一本講解 Python 原理的書，更多的資料結構細節請讀者自行搜索。只有理解這些資料結構的原理和使用方法，才能夠更加游刃有餘地解決算法和資料結構問題。