作為一名前端開發工程師，你可能有時會問：學習數據結構或者算法對於前端工程師有用麼？

總的來說，這些基礎學科在短期內收效確實甚微，但是我們首先不要將自己侷限在前端工程師這點上，當我們把視野放到編程這個角度去說，數據結構算法一定是有用的，並且也是你未來的一個天花板。可以不花費集中的時間去學習這些內容，但是一定需要時常去學習一點，因為這些技能可以實實在在提升你寫代碼的能力。

這一篇文章的內容信息量會很大，代碼也比較多，為了方便大家閱讀，有些代碼我會轉成圖片。

時間複雜度

在進入正題之前，我們先來了解下什麼是時間複雜度。

通常使用最差的時間複雜度來衡量一個算法的好壞。

常數時間 O(1) 代表這個操作和數據量沒關係，是一個固定時間的操作，比如說四則運算。

對於一個算法來說，可能會計算出操作次數為 aN + 1，N 代表數據量。那麼該算法的時間複雜度就是 O(N)。因為我們在計算時間複雜度的時候，數據量通常是非常大的，這時候低階項和常數項可以忽略不計。

當然可能會出現兩個算法都是 O(N) 的時間複雜度，那麼對比兩個算法的好壞就要通過對比低階項和常數項了。

棧

概念

棧是一個線性結構，在計算機中是一個相當常見的數據結構。

棧的特點是隻能在某一端添加或刪除數據，遵循先進後出的原則

實現

每種數據結構都可以用很多種方式來實現，其實可以把棧看成是數組的一個子集，所以這裡使用數組來實現

class Stack {
 constructor() {
 this.stack = []
 }
 push(item) {
 this.stack.push(item)
 }
 pop() {
 this.stack.pop()
 }
 peek() {
 return this.stack[this.getCount() - 1]
 }
 getCount() {
 return this.stack.length
 }
 isEmpty() {
 return this.getCount() === 0
 }
}

應用

題意是匹配括號，可以通過棧的特性來完成這道題目

var isValid = function (s) {
 let map = {
 '(': -1,
 ')': 1,
 '[': -2,
 ']': 2,
 '{': -3,
 '}': 3
 }
 let stack = []
 for (let i = 0; i < s.length; i++) {
 if (map[s[i]] < 0) {
 stack.push(s[i])
 } else {
 let last = stack.pop()
 if (map[last] + map[s[i]] != 0) return false
 }
 }
 if (stack.length > 0) return false
 return true
};

其實在 Vue 中關於模板解析的代碼，就有應用到匹配尖括號的內容。

隊列

概念

隊列是一個線性結構，特點是在某一端添加數據，在另一端刪除數據，遵循先進先出的原則。

實現

這裡會講解兩種實現隊列的方式，分別是單鏈隊列和循環隊列。

單鏈隊列

class Queue {
 constructor() {
 this.queue = []
 }
 enQueue(item) {
 this.queue.push(item)
 }
 deQueue() {
 return this.queue.shift()
 }
 getHeader() {
 return this.queue[0]
 }
 getLength() {
 return this.queue.length
 }
 isEmpty() {
 return this.getLength() === 0
 }
}

因為單鏈隊列在出隊操作的時候需要 O(n) 的時間複雜度，所以引入了循環隊列。循環隊列的出隊操作平均是 O(1) 的時間複雜度。

循環隊列

我們直接看代碼：

鏈表

概念

鏈表是一個線性結構，同時也是一個天然的遞歸結構。鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。

實現

下面我們主要以單向鏈表為例。

單向鏈表

樹

二叉樹

樹擁有很多種結構，二叉樹是樹中最常用的結構，同時也是一個天然的遞歸結構。

二叉樹擁有一個根節點，每個節點至多擁有兩個子節點，分別為：左節點和右節點。樹的最底部節點稱之為葉節點，當一顆樹的葉數量數量為滿時，該樹可以稱之為滿二叉樹。

二分搜索樹

二分搜索樹也是二叉樹，擁有二叉樹的特性。但是區別在於二分搜索樹每個節點的值都比他的左子樹的值大，比右子樹的值小。

這種存儲方式很適合於數據搜索。如下圖所示，當需要查找 6 的時候，因為需要查找的值比根節點的值大，所以只需要在根節點的右子樹上尋找，大大提高了搜索效率。

實現

以上是最基本的二分搜索樹實現，接下來實現樹的遍歷。

對於樹的遍歷來說，有三種遍歷方法，分別是先序遍歷、中序遍歷、後序遍歷。三種遍歷的區別在於何時訪問節點。在遍歷樹的過程中，每個節點都會遍歷三次，分別是遍歷到自己，遍歷左子樹和遍歷右子樹。如果需要實現先序遍歷，那麼只需要第一次遍歷到節點時進行操作即可。

以上的這幾種遍歷都可以稱之為深度遍歷，對應的還有種遍歷叫做廣度遍歷，也就是一層層地遍歷樹。對於廣度遍歷來說，我們需要利用之前講過的隊列結構來完成。

接下來先介紹如何在樹中尋找最小值或最大數。因為二分搜索樹的特性，所以最小值一定在根節點的最左邊，最大值相反

向上取整和向下取整，這兩個操作是相反的，所以代碼也是類似的，這裡只介紹如何向下取整。既然是向下取整，那麼根據二分搜索樹的特性，值一定在根節點的左側。只需要一直遍歷左子樹直到當前節點的值不再大於等於需要的值，然後判斷節點是否還擁有右子樹。如果有的話，繼續上面的遞歸判斷。

排名，這是用於獲取給定值的排名或者排名第幾的節點的值，這兩個操作也是相反的，所以這個只介紹如何獲取排名第幾的節點的值。對於這個操作而言，我們需要略微的改造點代碼，讓每個節點擁有一個 size 屬性。該屬性表示該節點下有多少子節點（包含自身）。

接下來講解的是二分搜索樹中最難實現的部分：刪除節點。因為對於刪除節點來說，會存在以下幾種情況

• 需要刪除的節點沒有子樹
• 需要刪除的節點只有一條子樹
• 需要刪除的節點有左右兩條樹

對於前兩種情況很好解決，但是第三種情況就有難度了，所以先來實現相對簡單的操作：刪除最小節點，對於刪除最小節點來說，是不存在第三種情況的，刪除最大節點操作是和刪除最小節點相反的，所以這裡也就不再贅述。

最後講解的就是如何刪除任意節點了。對於這個操作，T.Hibbard 在 1962 年提出瞭解決這個難題的辦法，也就是如何解決第三種情況。

當遇到這種情況時，需要取出當前節點的後繼節點（也就是當前節點右子樹的最小節點）來替換需要刪除的節點。然後將需要刪除節點的左子樹賦值給後繼結點，右子樹刪除後繼結點後賦值給他。

你如果對於這個解決辦法有疑問的話，可以這樣考慮。因為二分搜索樹的特性，父節點一定比所有左子節點大，比所有右子節點小。那麼當需要刪除父節點時，勢必需要拿出一個比父節點大的節點來替換父節點。這個節點肯定不存在於左子樹，必然存在於右子樹。然後又需要保持父節點都是比右子節點小的，那麼就可以取出右子樹中最小的那個節點來替換父節點。

AVL 樹

概念

二分搜索樹實際在業務中是受到限制的，因為並不是嚴格的 O(logN)，在極端情況下會退化成鏈表，比如加入一組升序的數字就會造成這種情況。

AVL 樹改進了二分搜索樹，在 AVL 樹中任意節點的左右子樹的高度差都不大於 1，這樣保證了時間複雜度是嚴格的 O(logN)。基於此，對 AVL 樹增加或刪除節點時可能需要旋轉樹來達到高度的平衡。

實現

因為 AVL 樹是改進了二分搜索樹，所以部分代碼是於二分搜索樹重複的，對於重複內容不作再次解析。

對於 AVL 樹來說，添加節點會有四種情況

對於左左情況來說，新增加的節點位於節點 2 的左側，這時樹已經不平衡，需要旋轉。因為搜索樹的特性，節點比左節點大，比右節點小，所以旋轉以後也要實現這個特性。

旋轉之前：new < 2 < C < 3 < B < 5 < A，右旋之後節點 3 為根節點，這時候需要將節點 3 的右節點加到節點 5 的左邊，最後還需要更新節點的高度。

對於右右情況來說，相反於左左情況，所以不再贅述。

對於左右情況來說，新增加的節點位於節點 4 的右側。對於這種情況，需要通過兩次旋轉來達到目的。

首先對節點的左節點左旋，這時樹滿足左左的情況，再對節點進行一次右旋就可以達到目的。

Trie

概念

在計算機科學，trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。

簡單點來說，這個結構的作用大多是為了方便搜索字符串，該樹有以下幾個特點

• 根節點代表空字符串，每個節點都有 N（假如搜索英文字符，就有 26 條） 條鏈接，每條鏈接代表一個字符
• 節點不存儲字符，只有路徑才存儲，這點和其他的樹結構不同
• 從根節點開始到任意一個節點，將沿途經過的字符連接起來就是該節點對應的字符串

實現

總得來說 Trie 的實現相比別的樹結構來說簡單的很多，實現就以搜索英文字符為例。

並查集

概念

並查集是一種特殊的樹結構，用於處理一些不交集的合併及查詢問題。該結構中每個節點都有一個父節點，如果只有當前一個節點，那麼該節點的父節點指向自己。

這個結構中有兩個重要的操作，分別是：

• Find：確定元素屬於哪一個子集。它可以被用來確定兩個元素是否屬於同一子集。
• Union：將兩個子集合併成同一個集合。

實現

堆

概念

堆通常是一個可以被看做一棵樹的數組對象。

堆的實現通過構造二叉堆，實為二叉樹的一種。這種數據結構具有以下性質。

• 任意節點小於（或大於）它的所有子節點
• 堆總是一棵完全樹。即除了最底層，其他層的節點都被元素填滿，且最底層從左到右填入。

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。

優先隊列也完全可以用堆來實現，操作是一模一樣的。

實現大根堆

堆的每個節點的左邊子節點索引是 i * 2 + 1，右邊是 i * 2 + 2，父節點是 (i - 1) /2。

堆有兩個核心的操作，分別是 shiftUp 和 shiftDown 。前者用於添加元素，後者用於刪除根節點。

shiftUp 的核心思路是一路將節點與父節點對比大小，如果比父節點大，就和父節點交換位置。

shiftDown 的核心思路是先將根節點和末尾交換位置，然後移除末尾元素。接下來循環判斷父節點和兩個子節點的大小，如果子節點大，就把最大的子節點和父節點交換。

下面是代碼實現方案

小結

這一篇主要介紹了一些比較常見的數據結構，當然還有其他更難的數據結構，這次沒有放進來，是因為小編覺得如果能夠掌握這些常見的內容已經足夠解決大部分的問題了。當然你如果還想繼續深入學習數據結構，可以閱讀《算法第四版》以及在 leetcode 中去實踐。