摘要：棧被稱為一種后入先出的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。這些操作需要求助于其他數(shù)據(jù)結(jié)構(gòu)，比如下面介紹的二叉查找樹。

在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務(wù)器端編程。鑒于JavaScript語言已經(jīng)走出了瀏覽器，程序員發(fā)現(xiàn)他們需要更多傳統(tǒng)語言（比如C++和Java）提供的工具。這些工具包括傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)（如鏈表，棧，隊(duì)列，圖等），也包括傳統(tǒng)的排序和查找算法。本文主要是總結(jié)什么情況下使用何種數(shù)據(jù)結(jié)構(gòu)較好，并沒有細(xì)講里面的原理和實(shí)現(xiàn)方式，僅僅提供給閱讀過《數(shù)據(jù)結(jié)構(gòu)和算法》的同學(xué)作為總結(jié)和參考筆記，如果未細(xì)究過數(shù)據(jù)結(jié)構(gòu)和算法的同學(xué)，本文也可以作為一個(gè)方向，希望能引導(dǎo)你去深究數(shù)據(jù)結(jié)構(gòu)和算法。

數(shù)據(jù)結(jié)構(gòu)和算法對于很多前端工程師來說，一直覺得是可有可無的，但其實(shí)不然，個(gè)人覺得，前端工程師其實(shí)是最需要重視數(shù)據(jù)結(jié)構(gòu)和算法的人，因?yàn)榍岸怂龅臇|西是用戶訪問網(wǎng)站第一眼看到的東西，特別在移動(dòng)浪潮到來之后，對用戶體驗(yàn)越來越高，對前端提出了更高的要求，面對越來越復(fù)雜的產(chǎn)品，需要堅(jiān)實(shí)的數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)才能駕馭。
如果沒有學(xué)習(xí)過計(jì)算機(jī)科學(xué)的程序員，當(dāng)我們在處理一些問題時(shí)，比較熟悉的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，數(shù)組無疑是一個(gè)很好的選擇。但很多時(shí)候，對于很多復(fù)雜的問題，數(shù)組就顯得太過簡陋了，當(dāng)學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)和算法之后，對于很多編程問題，當(dāng)想到一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)后，設(shè)計(jì)、實(shí)現(xiàn)和解決這些問題的算法就手到擒來。

相關(guān)講解細(xì)分：
數(shù)據(jù)結(jié)構(gòu)：列表、棧、隊(duì)列、鏈表、字典、散列、圖和二叉查找樹
排序算法：冒泡排序、選擇排序、插入排序、希爾排序、歸并排序和快速排序
查找算法：順序查找和二分查找

在日常生活中，人們經(jīng)常使用列表：待辦事項(xiàng)列表、購物清單、最佳十名榜單等等。而計(jì)算機(jī)程序也在使用列表，在下面的條件下，選擇列表作為數(shù)據(jù)結(jié)構(gòu)就顯得尤為有用：

數(shù)據(jù)結(jié)構(gòu)較為簡單

不需要在一個(gè)長序列中查找元素，或者對其進(jìn)行排序

反之，如果數(shù)據(jù)結(jié)構(gòu)非常復(fù)雜，列表的作用就沒有那么大了。

棧是一種特殊的列表，棧內(nèi)的元素只能通過列表的一端訪問，這一端稱為棧頂。想象一下，我們平常在飯館見到的一摞盤子就是現(xiàn)實(shí)世界常見的棧的例子，只能從最上面取盤子，盤子洗干凈后，也只能放在最上面。棧被稱為一種后入先出的數(shù)據(jù)結(jié)構(gòu)。是一種高效的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閿?shù)據(jù)只能在棧頂添加或刪除，所以這樣的操作很快。
使用條件：

只要數(shù)據(jù)的保存滿足后入先出或先進(jìn)后出的原理，都優(yōu)先考慮使用棧

隊(duì)列也是一種列表，不同的是隊(duì)列只能在隊(duì)尾插入元素，在隊(duì)首刪除元素。想象一下，我們在銀行排隊(duì)，排在最前面的人第一個(gè)辦理業(yè)務(wù)，而后面來的人只能排在隊(duì)伍的后面，直到輪到他們?yōu)橹埂?br>使用條件：

只要數(shù)據(jù)的保存滿足先進(jìn)先出、后入后出的原理，都優(yōu)先考慮使用隊(duì)列

常見應(yīng)用場景：

隊(duì)列主要用在和時(shí)間有關(guān)的地方，特別是操作系統(tǒng)中，隊(duì)列是實(shí)現(xiàn)多任務(wù)的重要機(jī)制

消息機(jī)制可以通過隊(duì)列來實(shí)現(xiàn)，進(jìn)程調(diào)度也是使用隊(duì)列來實(shí)現(xiàn)

鏈表也是一種列表，為什么需要出現(xiàn)鏈表，JavaScript中數(shù)組的主要問題時(shí)，它們被實(shí)現(xiàn)成了對象，與其他語言（比如C++和Java）的數(shù)組相對，效率很低。如果你發(fā)現(xiàn)數(shù)組在實(shí)際使用時(shí)很慢，就可以考慮使用鏈表來代替它。
使用條件：

鏈表幾乎可以用在任何可以使用一維數(shù)組的情況中。如果需要隨機(jī)訪問，數(shù)組仍然是更好的選擇。

字典是一種以鍵-值對行駛存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，JavaScript中的Object類就是以字典的形式設(shè)計(jì)的。JavaScript可以通過實(shí)現(xiàn)字典類，讓這種字典類型的對象使用起來更加簡單，字典可以實(shí)現(xiàn)對象擁有的常見功能，并相應(yīng)拓展自己想要的功能，而對象在JavaScript編寫中隨處可見，所以字典的作用也異常明顯了。

散列（也稱為哈希表）是一種的常用的數(shù)組存儲技術(shù)，散列后的數(shù)組可以快速地插入或取用。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。在散列表上插入、刪除和取用數(shù)據(jù)都非常快，但對于查找操作來說卻效率低下，比如查找一組數(shù)組中的最大值和最小值。這些操作需要求助于其他數(shù)據(jù)結(jié)構(gòu)，比如下面介紹的二叉查找樹。

散列表在JavaScript中可以基于數(shù)組去進(jìn)行設(shè)計(jì)。數(shù)組的長度是預(yù)先設(shè)定的，所有元素根據(jù)和該元素對應(yīng)的鍵，保存在數(shù)組的特定位置，這里的鍵和對象的鍵是類似的概念。使用散列表存儲數(shù)組時(shí)，通過一個(gè)散列函數(shù)將鍵映射為一個(gè)數(shù)字，這個(gè)數(shù)字的范圍是0到散列表的長度。

但是即使使用一個(gè)高效的散列函數(shù)，依然存在將兩個(gè)鍵映射為同一個(gè)值的可能，這種現(xiàn)象叫做碰撞。常見碰撞的處理方法有：開鏈法和線性探測法（具體概念有興趣的可以網(wǎng)上自信了解）

使用條件：

可以用于數(shù)據(jù)的插入、刪除和取用，不適用于查找數(shù)據(jù)

圖由邊的集合及頂點(diǎn)的集合組成。地圖是我們身邊很常見的現(xiàn)實(shí)場景，比如每兩個(gè)城鎮(zhèn)都由某種道路相連。上面的每個(gè)城鎮(zhèn)可以看作一個(gè)頂點(diǎn)，連接城鎮(zhèn)的道路便是邊。邊由頂點(diǎn)對（v1, v2）定義，v1和v2分別是圖中的兩個(gè)頂點(diǎn)。頂點(diǎn)也有權(quán)重，也成為成本。如果一個(gè)圖的頂點(diǎn)對是有序的，則稱之為有向圖（例如常見的流程圖），反之，稱之為無序圖。
使用場景（用圖對現(xiàn)實(shí)中的系統(tǒng)建模）：

交通系統(tǒng)，可以用頂點(diǎn)表示街道的十字路口，邊可以表示街道。加權(quán)的邊可以表示限速或者車道的數(shù)量。可以用該系統(tǒng)判斷最佳路線及最有可能堵車的街道。

任何運(yùn)輸系統(tǒng)都可以用圖來建模。比如，航空公司可以用圖來為其飛行系統(tǒng)建模。將每個(gè)機(jī)場看成頂點(diǎn)，將經(jīng)過兩個(gè)頂點(diǎn)的每條航線看作一條邊。加權(quán)的邊可以表示從一個(gè)機(jī)場到另一個(gè)機(jī)場的航班成本，或兩個(gè)機(jī)場間的距離，這取決于建模的對象是什么。

搜索圖的算法主要有兩種： 深度優(yōu)先搜索和廣度優(yōu)先搜索。

樹是計(jì)算機(jī)科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu)。樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲數(shù)據(jù)。
二叉樹每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)不允許超過兩個(gè)。一個(gè)父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)，通過將子節(jié)點(diǎn)的個(gè)數(shù)限定為2，可以寫出高效的程序在樹中插入、查找和刪除數(shù)據(jù)。
二叉查找樹（BST）是一種特殊的二叉樹，相對較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中。這一特性使得查找的效率很高，對于數(shù)值型和非數(shù)值型的數(shù)據(jù)，比如單詞和字符串，都是如此。
二叉查找樹實(shí)現(xiàn)方法

function Node(data, left, right) { // 創(chuàng)建節(jié)點(diǎn)
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}

function show () { // 顯示樹的數(shù)據(jù)
  return this.data
}

function BST () { // 二叉查找樹類
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍歷BST的方式
}

function insert (data) { // 向樹中插入數(shù)據(jù)
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
      parent = current
      if (data < current.data) {
        current = current.left;
        if (current == null) {
          parent.left = n;
          break;
        }
      } else {
        current = current.right;
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}

遍歷BST的方式有三種：中序遍歷（以升序訪問樹中所有節(jié)點(diǎn)，先訪問左節(jié)點(diǎn)，再訪問根節(jié)點(diǎn)，最后訪問右節(jié)點(diǎn)）【10 22 30 56 77 81 92】、先序遍歷（先訪問根節(jié)點(diǎn)，再以同樣的方式訪問左節(jié)點(diǎn)和右節(jié)點(diǎn)）【56 22 10 30 81 77 92】、后序遍歷（先訪問葉子節(jié)點(diǎn)，從左子樹到右子樹，再到根節(jié)點(diǎn)）【10 30 22 77 92 81 56】

基本排序算法，其核心思想是指對一組數(shù)組按照一定的順序重新排列。重新排列時(shí)用到的技術(shù)是一組嵌套的for循環(huán)。其中外循環(huán)會遍歷數(shù)組的每一項(xiàng)，內(nèi)循環(huán)則用于比較元素。

冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端。

function bubbleSort (arr) {
    var i = arr.length;
    while (i > 0) {
        var pos = 0
        for (var j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]){
                pos = j
                var temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
        i = pos
    }
    return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

function selectionSort (arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len-1; i++) {
        minIndex = i;
        for (var j = i+1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
    }
    return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

function insertSort (arr) {
    var len = arr.length
    for (i = 1; i < len; i++) {
        var key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j]
            j--;
        }
        arr[j+1] = key
    }
    return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

高級數(shù)據(jù)排序算法，通常用于處理大型數(shù)據(jù)集的最高效排序算法，它們處理的數(shù)據(jù)集可以達(dá)到上百萬個(gè)元素，而不僅僅是幾百個(gè)或者幾千個(gè)，下面我們將介紹希爾排序、歸并排序和快速排序。

1959年Shell發(fā)明，第一個(gè)突破O(n^2)的排序算法；是簡單插入排序的改進(jìn)版；它與插入排序的不同之處在于，它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。
希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。

function shellSort (arr) {
    var len = arr.length;
    var temp, gap = 1;
    while (gap < len /3 ) {
        gap = gap * 3 + 1
    }
    while (gap >= 1) {
        for (var i = gap; i < len; i++) {
            temp = arr[i]
            for (var j = i - gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j]
            }
            arr[j+gap] = temp
        }
        gap = (gap - 1) / 3
    }
    return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。

function mergeSort (arr) {
    var len = arr.length
    if (len < 2) {
        return arr
    }
    var middle = Math.floor(len / 2)
    var left = arr.slice(0, middle)
    var right = arr.slice(middle)
    return merge (mergeSort(left), mergeSort(right));
}
function merge (left, right) {
    var result = []
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    while (left.length) {
        result.push(left.shift())
    }
    while (right.length) {
        result.push(right.shift())
    }
    return result
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

快速排序是處理 大數(shù)據(jù)集最快的排序算法之一。它是一種分而治之的算法，通過遞歸的方法將數(shù)據(jù)依次分解為包含較小元素和較大元素的不同子序列。該算法不斷重復(fù)這個(gè)步驟知道所有數(shù)據(jù)都是有序的。
這個(gè)算法首先要在列表中選擇一個(gè)元素作為基準(zhǔn)值。數(shù)據(jù)排序圍繞基準(zhǔn)值進(jìn)行，將列表中小于基準(zhǔn)值的元素移到數(shù)組的底部，將大于基準(zhǔn)值的元素移到數(shù)組的頂部。

function qSort (arr) {
    if (arr.length == 0) {
        return []
    }
    var left = []
    var right = []
    var pivot = arr[0]
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return qSort(left).concat(pivot, qSort(right))
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(qSort(arr));

在列表中查找數(shù)據(jù)有兩種方式：順序查找和二分查找。順序查找適用于元素隨機(jī)排列的列表；二分查找適用于元素已排序的列表。二分查找效率更高，但是必須在進(jìn)行查找之前花費(fèi)額外的時(shí)間將列表中的元素排序。

對于查找數(shù)據(jù)，最簡單的方法就是從列表的第一個(gè)元素開始對列表元素逐個(gè)進(jìn)行判斷，直到找到了想要的結(jié)果，或者直到列表結(jié)尾也沒有找到。這種方法稱為順序查找，有時(shí)也被稱為線性查找。

function seqSearch (arr, data) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == data) {
      return i;
    }
  }
  return -1;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(seqSearch(arr, 15))

二分法查找，也稱折半查找，是一種在有序數(shù)組中查找特定元素的搜索算法。查找過程可以分為以下步驟：

首先，從有序數(shù)組的中間的元素開始搜索，如果該元素正好是目標(biāo)元素（即要查找的元素），則搜索過程結(jié)束，否則進(jìn)行下一步。

如果目標(biāo)元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半?yún)^(qū)域查找，然后重復(fù)第一步的操作。

如果某一步數(shù)組為空，則表示找不到目標(biāo)元素。

function binSearch (arr, data) {
    var low = 0;
    var high = arr.length - 1
    while (low <= high) {
        var middle = Math.floor((low + high) / 2)
        if (arr[middle] < data) {
            low = middle + 1
        } else if (arr[middle] > data) {
            high = middle - 1
        } else {
            return middle
        }
    }
    return -1
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binSearch(arr, 15))

非常謝謝觀看，看到這里相信很不容易，畢竟相對枯燥的知識點(diǎn)很多，但卻是必不可少的。希望這篇文章能讓你對數(shù)據(jù)結(jié)構(gòu)和算法有一個(gè)新的認(rèn)識，或者產(chǎn)生一些新的想法，那么寫這篇文章的意義就達(dá)到了，當(dāng)然發(fā)現(xiàn)文章寫得有問題的，也非常歡迎指出，一起共同成長。

歡迎關(guān)注我的github----https://github.com/zoro-web/blog，你的關(guān)注是我整理知識的更大動(dòng)力，我的博客會定期整理發(fā)布一些文章。