常見數(shù)據(jù)結(jié)構(gòu)和算法的應用系列示例分析

數(shù)據(jù)結(jié)構(gòu)是指：一種數(shù)據(jù)組織、管理和存儲的格式，它可以幫助我們實現(xiàn)對數(shù)據(jù)高效的訪問和修改。

數(shù)據(jù)結(jié)構(gòu) = 數(shù)據(jù)元素 + 元素之間的結(jié)構(gòu)。

如果說數(shù)據(jù)結(jié)構(gòu)是造大樓的骨架，算法就是具體的造樓流程。流程不同，效率資源不同。我會兩者結(jié)合簡單探討下他們的特點和應用。

常見的數(shù)據(jù)結(jié)構(gòu)可分為：線性結(jié)構(gòu)、樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu)。

常見的算法有：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法等。

下面從 線性數(shù)據(jù)結(jié)構(gòu)、遞歸 和 排序算法 談起。

線性結(jié)構(gòu)

線性結(jié)構(gòu)：是指數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個元素結(jié)點最多對應一個前驅(qū)結(jié)點和一個后繼結(jié)點。如數(shù)組, 鏈表，棧 ，隊列等。

數(shù)組

數(shù)組是是由相同類型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來存儲。利用元素的下標位置可以計算出該元素對應的存儲地址。

 

優(yōu)點：
分配基于連續(xù)內(nèi)存，是一種天生的索引結(jié)構(gòu)，查詢修改元素的效率O(1)。同時可以借助 CPU 的緩存機制，預讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高。

缺點：
數(shù)組的索引優(yōu)點也是它的缺點，因為它的索引是基于一塊連續(xù)內(nèi)存元素存儲的位置下標決定的，增刪arr[i]時間復雜度O(n)，需要整體移動數(shù)組arr[i-n-1]的位置。此外，分配大數(shù)組會占用較大的內(nèi)存。

可通過以下方式避免元素拷貝和占用大的開銷：

1.懶刪除：刪除時只標記元素被刪除，并不真正的執(zhí)行刪除。當數(shù)組整體內(nèi)存不夠用時，再執(zhí)行真正的刪除。
2.分塊思想：將一大塊內(nèi)存分為n個小塊，以 小塊 為單位進行數(shù)組內(nèi)存的拷貝。如Mysql的InnoDB引擎中每個Buffer Pool實例由若干個chunk組成，實際內(nèi)存申請操作以chunk為單位。
3.縮容：曾經(jīng)面試阿里時，就讓設(shè)計了一個縮容版的HashMap。浪費可恥，節(jié)約光榮。
4.鏈表。

鏈表

鏈表的存在就是為了解決數(shù)組的增刪復雜耗時，內(nèi)存占用較大的問題。它并不需要一塊連續(xù)的內(nèi)存空間，它通過 指針 將一組零散的內(nèi)存塊串聯(lián)起來。根據(jù)指針的不同，有單鏈表，雙向鏈表，循環(huán)鏈表之分。

 

優(yōu)點：
增刪arr[i]時間復雜度O(1)，使用鏈表本身沒有大小的限制，天然地支持動態(tài)擴容。

缺點：
沒有“索引”，查詢時間復雜度O(n)。需要維護指針，更占內(nèi)存。同時內(nèi)存不連續(xù)，容易造成內(nèi)存碎片。

可以看出：數(shù)組和鏈表是相互補充的一對數(shù)據(jù)結(jié)構(gòu)。那怎么彌補鏈表的不足呢？

內(nèi)存這塊是不好解決，這是由 指針 決定的。

關(guān)于索引，沒索引就幫它建索引好了：

1.結(jié)合hash表，記錄鏈表每個結(jié)點的位置。
2.鏈表長度拉的過長時，考慮跳表，紅黑樹這類數(shù)據(jù)結(jié)構(gòu)。（別慌，后面會講～）

應用場景：
數(shù)組和鏈表的運用很廣泛，他們是構(gòu)成 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。如棧，隊列，集合等等。

棧

棧是一種受限制的線性數(shù)據(jù)結(jié)構(gòu)。元素只可以在棧頂被訪問。符合先進后出的First-In-Last-Out的訪問方式。

 

用數(shù)組實現(xiàn)的叫順序棧，用鏈表實現(xiàn)的叫鏈式棧。

可能有人會有疑問：我用數(shù)組鏈表在頭尾兩端可伸可縮，為毛要用只能在頭部操作的棧結(jié)構(gòu)呢？

這種FILO的結(jié)構(gòu)當然是只適用于FILO的場景。如果我們將數(shù)組/鏈表這種結(jié)構(gòu)封裝為棧，就可以只使用其pop/push的API，屏蔽掉實現(xiàn)細節(jié)。

應用場景：
1.編輯器的redo/undo操作。
2.瀏覽器的前進/后退操作。
3.編譯器的括號匹配校驗
4.數(shù)學計算中的表達式求值
5.函數(shù)調(diào)用
6.遞歸
7.字符串反轉(zhuǎn)…

隊列

隊列也是一種受限制的線性數(shù)據(jù)結(jié)構(gòu)。符合先進先出的First-In-First-Out 的訪問方式。同樣，用數(shù)組實現(xiàn)的隊列叫作順序隊列，用鏈表實現(xiàn)的隊列叫作鏈式隊列。

 

根據(jù)頭尾指針和操作的不同，隊列又可分為雙端隊列，循環(huán)隊列，阻塞隊列，并發(fā)隊列。

• 雙端隊列：頭尾均可以進行插入，刪除，訪問元素，更為實用。不存在FIFO這種限制。
  

     

• 循環(huán)隊列：把隊列的頭尾相連接并且使用順序存儲結(jié)構(gòu)進行數(shù)據(jù)存儲的隊列。
  

     

存在并發(fā)的場景下，隊列存取元素的臨界區(qū)為 enqueue、dequeue操作。保證并發(fā)下的隊列存取安全的隊列為阻塞隊列 和 并發(fā)隊列。兩者的區(qū)別在于 同步資源的粒度不同。

• 阻塞隊列：通過 互斥鎖 保證enqueue、dequeue的安全，鎖粒度較大。如Java JUC包中的阻塞隊列。

• 并發(fā)隊列：基于數(shù)組的循環(huán)隊列，利用 CAS 原子操作保證enqueue、dequeue的安全。
  其實就是通過：多次volatile讀 + CAS操作 這種樂觀思想 修改頭尾指針的位置，保證enqueue、dequeue的安全。CAS的同步代價小較小，所以稱為：無鎖并發(fā)隊列。如Disruptor框架中Ring Buffer就運用了這點。

PS: 很多框架對線程池的需求都替換成了Disruptor來實現(xiàn)，如Log4j2、Canal等。

應用場景：
隊列的作用其實就是現(xiàn)實中的排隊。當資源不足時，通過“隊列” 這種結(jié)構(gòu)來實現(xiàn)排隊的效果。用于：
1.任務調(diào)度存在的地方：CPU/磁盤/線程池/任務調(diào)度框架…
2.兩個進程中數(shù)據(jù)的傳遞：如pipe/file IO/IO Buffer…
3.生產(chǎn)者消費者場景中..

遞歸實現(xiàn)

遞歸 是一種算法求解的編碼實現(xiàn)。應用于如深度優(yōu)先搜索、前中后序二叉樹遍歷（挖坑后面講～）等。因為接下來的排序算法如：歸并/快排 可通過遞歸來實現(xiàn)，所以我們先看一下書寫遞歸的步驟。熟悉了遞歸的思想，它其實是一種書寫簡單的編碼方式。

只要問題滿足以下三點，均可使用遞歸來進行求解：

1.一個問題的解可以分解為幾個子問題的解
2.問題和子問題之間，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
3.存在遞歸終止條件

寫遞歸代碼的關(guān)鍵在于：找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再敲定終止條件，最后將遞推公式和終止條件翻譯成代碼。

因為人并不擅長處理這種程序，所以在寫遞歸代碼的時候，我們可以自動屏蔽掉遞歸的執(zhí)行過程。我們只需要告訴程序：遞推公式 和 終止條件 是什么，事情就會變Easy~

使用時的注意項：

1.stackoverflow: 實際函數(shù)調(diào)用層次太深，就會有系統(tǒng)?；蛘咛摂M機棧空間溢出的風險。

2.子問題的重復計算：前面文章我有講 動態(tài)規(guī)劃通過避免子問題的重復計算能夠降低時間復雜度。一種方式就是通過 遞歸 + 備忘錄（子問題的解保存起來）來解決。

排序算法

233醬學習的第一個算法就是冒泡排序算法，我想不少碼農(nóng)都經(jīng)歷過被 “幾大排序算法” 支配的恐懼。

排序是我們在項目工程中經(jīng)常遇到的一個場景，如TopK，中位數(shù)問題等。有序 和 無序 的數(shù)據(jù)集合之間的差別在于 前者  “逆序?qū)Α?/strong>  為0.

小貼士：如果i < j，且a[i] > a[j], 就稱為一個逆序?qū)Γ?1，7，3，5 中的 <7，5>
反之則為有序?qū)?，?lt;1,3>

不同的排序算法消滅逆序?qū)Φ姆绞讲灰粯樱w現(xiàn)在時空復雜度，排序方式，穩(wěn)定性，適用場景等方面不同。

我先放一張網(wǎng)上排序算法的圖：

 

選擇排序算法時，我們應該考慮算法的執(zhí)行效率，內(nèi)存消耗，穩(wěn)定性等這些因素。

PS：以下內(nèi)容主要引用極客時間王爭大佬的《數(shù)據(jù)結(jié)構(gòu)和算法之美》課程，233能力有限，默默給大佬打廣告&點贊。