數(shù)據(jù)結(jié)構(gòu)和算法是一位優(yōu)秀的程序員的基本功洞拨。在面試時(shí)這兩點(diǎn)也是考察的重點(diǎn)，本文參考《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》一書巍耗，總結(jié)了常見的數(shù)據(jù)結(jié)構(gòu)令哟。

目錄：
一、數(shù)組
二屈暗、棧和隊(duì)列
三拆讯、鏈表
四、集合
五养叛、字典和散列表
六种呐、樹
七、圖

內(nèi)容較多弃甥，先介紹前三種數(shù)據(jù)結(jié)構(gòu)爽室。

一、數(shù)組：
幾乎所有的編程語言都原生支持?jǐn)?shù)組類型淆攻，因?yàn)閿?shù)組是最簡單的內(nèi)存數(shù)據(jù)結(jié)構(gòu)阔墩。與其他語言相比嘿架，JavaScript數(shù)組長度和元素類型都是不固定的。并且啸箫，數(shù)組在內(nèi)存空間中也可以不連續(xù)存在耸彪。

1 創(chuàng)建和初始化數(shù)組
JavaScript創(chuàng)建數(shù)組有兩種基本方式：第一種是使用Array構(gòu)造函數(shù)，如下面代碼所示：

var colors = new Array();
var colors = new Array(10);  //  創(chuàng)建長度為10的數(shù)組
var colors = new Array('red', 'blue', 'green'); //創(chuàng)建包含'red','blue','green'三個(gè)值的數(shù)組

在使用Array構(gòu)造函數(shù)時(shí)忘苛，可以省略new操作符蝉娜。
第二種是使用數(shù)組字面量表示法，如下代碼所示：

var colors = []; //創(chuàng)建一個(gè)空數(shù)組
var colors = ['red','blue','green]; //創(chuàng)建一個(gè)包含3個(gè)字符串的數(shù)組

2 添加和刪除元素
添加元素到數(shù)組末尾：

var colors = ['red','blue','green'];
colors.push('yellow');
console.log(colors);  //  ["red", "blue", "green", "yellow"]

添加元素到數(shù)組頭部：

var colors = ['red', 'blue', 'green'];
colors.unshift('yellow');
console.log(colors);  //  ["yellow", "red", "blue", "green"]

刪除數(shù)組末尾元素：

var colors = ['red', 'blue', 'green'];
colors.pop();
console.log(colors);  // ["red", "blue"]

刪除數(shù)組頭部元素：

var colors = ['red', 'blue', 'green'];
colors.shift();
console.log(colors);  // ["blue", "green"]

刪除任意位置的元素：
通過數(shù)組提供的splice方法扎唾，可以刪除任意位置的元素召川，如下所示：

var colors = ['red', 'blue', 'green'];
colors.splice(1,1);
console.log(colors);  // ["red", "green"]

3 JavaScript中數(shù)組方法：
JavaScript中數(shù)組有很多很強(qiáng)大的方法，大家可以參閱
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array

二胸遇、棧和隊(duì)列：
棧和隊(duì)列也是比較常見的數(shù)據(jù)結(jié)構(gòu)荧呐，棧是一種遵從后進(jìn)先出（LIFO）原則的有序列表，只能對(duì)棧頂元素進(jìn)行添加或刪除操作狐榔。隊(duì)列是一種遵從先進(jìn)先出（FIFO）原則的有序列表坛增，只能在尾部添加元素，從頭部移除元素薄腻。我們可以通過數(shù)組來實(shí)現(xiàn)棧和隊(duì)列。
1 棧：

棧.PNG

棧需要聲明的方法：
push(element(s)): 添加一個(gè)（或幾個(gè)）新元素到棧頂
pop(): 移除棧頂?shù)脑亟彀福瑫r(shí)返回被移除的元素
peek(): 返回棧頂元素
isEmpty(): 棧中是否有元素
clear(): 移除棧中所有元素
size(): 返回棧包含的元素個(gè)數(shù)
下面是棧的實(shí)現(xiàn)方式（構(gòu)造函數(shù)）:

function Stack() {
  var items = [];
  this.push= function(element) {
    items.push(element);
  };
  this.pop= function() {
    return items.shift();
  };
  this.peek= function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length == 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size= function() {
    return items.length;
  };
}

至此庵楷，便可以通過var newStack = new Stack()的方式聲明一個(gè)棧。
2 隊(duì)列：

隊(duì)列.PNG

隊(duì)列需要聲明的方法：
enqueue(element(s)): 向隊(duì)列尾部添加一個(gè)（或多個(gè)）元素
dequeue(): 移除隊(duì)列中的第一個(gè)元素楣颠，并返回該元素
front(): 返回隊(duì)列中的第一個(gè)元素
isEmpty(): 隊(duì)列中是否有元素
clear(): 移除隊(duì)列中所有元素
size(): 返回隊(duì)列包含的元素個(gè)數(shù)
下面是隊(duì)列的實(shí)現(xiàn)方式（構(gòu)造函數(shù)）：

function Queue() {
  var items = [];
  this.enqueue = function(element) {
    items.push(element);
  };
  this.dequeue = function() {
    return items.shift();
  };
  this.front = function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length == 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size= function() {
    return items.length;
  };
}

同樣尽纽，通過var newQueue = new Queue()的方式聲明一個(gè)隊(duì)列。

三童漩、鏈表：
雖然JavaScript中數(shù)組是動(dòng)態(tài)的弄贿，并且可以在任意位置添加和刪除元素。但其添加和刪除元素的成本仍很高矫膨，需要移除元素差凹。
鏈表中的元素在內(nèi)存中不是連續(xù)放置的。每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成侧馅。鏈表危尿，仿佛一列火車，一個(gè)元素對(duì)應(yīng)火車的一節(jié)車廂馁痴，元素的指針就像車廂間的連接谊娇。

鏈表.jpg

var Node = function (element) {
  this.element = element;
  thie.next = null;
}

鏈表需要聲明的方法：
append(element): 向鏈表尾部添加一個(gè)新的項(xiàng)

  this.append = function(element) {
    var node = new Node(element),
        current;
    if (head === null) { // 判斷鏈表是否為空
      head = node;
    } else {
        current = head;
        while(current.next) { // 遍歷鏈表挖胃，直到最后一個(gè)元素
          current = current.next;
        }
        current.next = node; // 找到最后一個(gè)元素杂靶，將其next設(shè)為node
    }
    length++; // 更新鏈表長度
  };

insert(position, element): 向鏈表的特定位置插入一個(gè)新的項(xiàng)

this.insert = function(position, element) {
  if (position > -1 && position <= length) {
    var node = new Node(element),
        current = head,
        previous,
        index = 0;
    if (position === 0) { //在第一個(gè)位置添加
      node.next = current;
      head = node;
    } else {
        while (index++ < position) {
           previous = current;
           current = current.next;
        }
        node.next = current;
        previous.next = node;
    }
    length++; // 更新鏈表長度
    return true;
  } else {
    return false;
  }
};

removeAt(position): 從鏈表的特定位置移除一項(xiàng)

this.removeAt = function(position) {
// 檢查是否越界
  if (position > -1 && position < length) {
    var current = head,
        previous,
        index = 0;
// 移除第一項(xiàng)
    if (position === 0) {
        head = current.next;
    } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        // 將previous與current的下一項(xiàng)連接起來
        previous.next = current.next;
      }
    length--;
    return current.element;
} else {
    return null;
  }
};

indexOf(element): 返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回-1

this.indexOf = function(element) {
  var current = head,
      index = 0;
  while (current) {
    if (element === current.element) {
      return index;
    }
    index++;
    current = current.next;
  }
  return -1;
};

remove(element): 從鏈表中移除一項(xiàng)

this.remove = function(element) {
  var index = this.indexOf(element);
   return this.removeAt(index);
};

isEmpty(): 鏈表是否為空

this.isEmpty = function () {
  return length === 0;
};

size(): 鏈表中包含元素的個(gè)數(shù)

this.size = function () {
  return length;
};

鏈表有多種不同的類型酱鸭，這邊介紹兩種常見的: 雙向鏈表和循環(huán)鏈表
雙向鏈表：雙向鏈表與普通鏈表的區(qū)別在于吗垮，雙向鏈表的鏈接是雙向的：一個(gè)鏈向下一個(gè)元素，另一個(gè)鏈向前一個(gè)元素凹髓，如下圖所示：

雙向鏈表.jpg

循環(huán)鏈表.jpg

至此蔚舀，數(shù)組饵沧、隊(duì)列、棧和鏈表介紹完畢赌躺。剩下的四個(gè)數(shù)據(jù)結(jié)構(gòu)下回分曉~