資料結構筆記-Array, Vector(List), Stack, Queue, Set(HashSet), Map(Dictionary)用法

       最近面試時被面試官提到資料結構的使用需要加強，於是開始惡補資料結構的知識，相信許多人都有在資訊相關的學系學到基礎的概念，但其中也有不少人大概不知道怎麼去使用吧，於是，經過一天的查找去研究C++中的Standard Template Library (STL)和C#的System.Collections.Generic中的各種資料儲存結構的使用方式及其原理。

       在C++ STL和C# Generic中，由於名詞有些不一樣(但架構大同小異)，因此在正式解說前必須先釐清和分類當中的結構，以簡單的方式來對應一下：

C++ STL	C# Generic
Vector	List
Stack	Stack
Queue	Queue
Set	HashSet
Map	Dictionary

當然，最少不了的是Array的儲存架構，以下說明依序由Array開始，接著是Vector (List)、Stack、Queue、Set及Map (Dictionary)。

       陣列的用法相信大家再熟悉不過了，C++和C#也沒有太大的差異，主要的方式就是在記憶體中建立一連串的空間，宣告時必須有固定的長度，其查找的方式是以陣列開頭的記憶體位址開始，根據每個元素的長度乘上相對應的編號( 如array[i] )，因此在查詢的時間複雜度是O(1)；但缺點也不少，首先，宣告陣列時，其長度必須一開始就設定好，因此無法彈性擴充；其次，若是需要在一連串的資料中從任意位置插入一筆資料時，該位置之後(含該位置)的資料都必須向後移動，因此在時間複雜度上面是O(n)，更別說往後移動時還必須判斷資料有沒有超過陣列長度；Array的使用時機適合用在少修改、多查找的資料。

陣列插入新元素示意圖

       在大學時期聽說過Linked List嗎?沒錯，這其實就是Linked List的實作方式，Linked List不像Array需要事先設定好長度來配置記憶體空間，所有元素可以隨機配置在記憶體的任何位置，儲存元素的資料前，我們會先以節點(Node)的方式去包裝元素，並且在該節點中設有另一個節點的位址，我們先稱為Next，在C++中通常使用指標，在C#中則是因為大部分的資料傳遞都是Pass by reference，因此雖然沒有指標，但還是能找到該下一個節點，如此一來，我們可以將所有的節點串起來，在查找時，我們可以透過第一個節點去尋找下一個節點，又可以利用下一個節點去找到下下個節點，以此類推，當我們需要尋找第 i 個節點的資料時，就必須從第一個節點找起，因此時間複雜度為O(n)；雖然查找的能力差，但在擴充性上卻是Array所沒有的，現在我們假設我們要將一筆資料從任意一個位置中插入怎麼做？首先，找到該位置的上一個節點，將他的Next修改成我們要加入的節點，接著再將新插入的節點的Next修改成被往後挪的節點，即大功告成！那若要刪除呢？一樣簡單，把該節點的上一個節點的Next修改成下一個節點即可，時間複雜度亦是O(n)；因此Vector (List)的使用時機適合經常使用加入、插入及刪除的資料結構。

Linked List刪除示意圖

       Stack可以最大的特點就是先進後出的特性，舉例來說，我們在吃到飽的餐廳中，常常會看到好幾疊的盤子，一般在拿盤子時，我們都會先拿最上面的盤子，而服務生要補充盤子時，也是從最上面先放著，而Stack的特性即是如此，Stack的實作可以有兩種，第一種是使用Array的方式，但簡化Array的操作，每次加入及取得都必須從最後一筆資料開始，但同Array，這種方式會受限於資料數量的擴充；另一種做法則是以Linked List的型態來實現，Vector (List)在搜尋時會從首節點開始搜尋；換個角度想，我們亦可以紀錄末節點，每次加入及取出資料都從末節點開始，Stack的使用時機通常用於需要遞迴的資料或可能回朔的情形，例如棋盤棋子的悔棋。

       相較於Stack的先進後出，Queue則是先進先出，相信有修過網路概論等課程的各位並不陌生，最常被舉例的就是排隊買票，其結構與Stack類似，可使用Array的方式或Linked List的方式來實作，Array的實作方式是可以額外給予兩個指標分別去決定最前面的元素及最後面的元素，每提取資料時，提取最前面的元素並刪除(或賦予Null)，並將指標往後移動，同理標示最後的指標也是這麼做，但必須小心兩個指標都標示在同一個元素時的問題，必須再作額外的判斷；以Linked List為基本結構的方式則是紀錄兩頭與尾，每次提取資料時取第一個節點，放入時接在最後一個節點，Queue的使用時機適合用在具有時間性及順序性的資料，例如要讓程式模仿使用者操作的方法，可以將使用者的操作以資料的形式儲存並放入Queue，到時就能夠以這個順序進行模擬。

       Set (HashSet)的實作主要以二元樹(Binary Tree)為主，更精確地來說是紅黑樹(RB Tree)，相對於前面的方法並不是那麼容易理解且原理及應用非常的廣泛，因此在此只提及其特性和使用時機，其餘有興趣亦可去閱讀補充資料，在Set (HashSet)的概念中，每一筆資料都不能重複，因此每一筆資料都會有個Key值，而這令我們可以利用二元樹的相關演算法快速進行插入、搜尋及刪除，其時間複雜度皆為O(log n)，在C++被稱作Set，而在C#被稱作HashSet的理由在於C++具有指標這種強烈單一性的索引值，因此它的Key值可以用指標來代替；C#卻沒有指標的概念，必須使用雜湊(Hash)來確立Key值的單一性，但無法加入與其中一個元素完全相同的資料，而Set也可用於作集合的運算，例如聯集、交集、差集等，使用Set (HashSet)的優點在於插入、搜尋、刪除的複雜度低，執行會更有效率，缺點是每次插入或搜尋都會進行一次樹的平衡(複雜度O(1))，因此不適合隨機取樣的情境，且由於單一性的限制，可能重複的資料也不適合使用Set (HashSet)。

       結構與Set (HashSet)相同，都是紅黑樹作為基礎的儲存結構，與Set (HashSet)應用上最大的不同就是Map (Dictionary)的Key值可以由使用者定義，且不限定變數型態，當然，Key值必須具有唯一性，且Key的類別可自定義比較類別，某種程度上可加速資料的搜尋，其使用時機與Set (HashSet)相同，不過Value值不再受到單一性的限制。

以上內容如有錯誤請不吝告知。