摘要：數(shù)據(jù)結(jié)構(gòu)和算法之魂標(biāo)簽空格分隔未分類數(shù)據(jù)結(jié)構(gòu)棧一種遵從先進(jìn)后出原則的有序集合新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端為棧底。

標(biāo)簽（空格分隔）： 未分類

棧：一種遵從先進(jìn)后出 (LIFO) 原則的有序集合；新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端為棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

class Stack {
    constructor() {
        this.items = []
    }
    push(element) {
         this.items.push(element)
    }
    pop() {
        return this.items.pop()
    }
    clear() {
        this.items = []
    }
    print() {
        console.log(this.items.toString())
    }
    // 屬性
    get peek() {
        return this.items[this.items.length - 1]
    }
    get size() {
        return this.items.length
    }
}

隊(duì)列：與上相反，一種遵循先進(jìn)先出 (FIFO / First In First Out) 原則的一組有序的項(xiàng)；隊(duì)列在尾部添加新元素，并從頭部移除元素。最新添加的元素必須排在隊(duì)列的末尾。

class Queue {
  constructor(items) {
    this.items = items || []
  }
  // 普通隊(duì)列
  enqueue(element) {
    this.items.push(element)
  }
  // 優(yōu)先隊(duì)列的構(gòu)造方法
  // enqueue(element, priority) {
  //   const queueElement = { element, priority }
  //   if (this.isEmpty) {
  //     this.items.push(queueElement)
  //   } else {
  //     const preIndex = this.items.findIndex((item) => queueElement.priority < item.priority)
  //     if (preIndex > -1) {
  //       this.items.splice(preIndex, 0, queueElement)
  //     } else {
  //       this.items.push(queueElement)
  //     }
  //   }
  // }
  dequeue() {
    return this.items.shift()
  }
  front() {
    return this.items[0]
  }
  clear() {
    this.items = []
  }
  print() {
    console.log(this.items.toString())
  }
  get size() {
    return this.items.length
  }
  get isEmpty() {
    return !this.items.length
  }
}
// 循環(huán)隊(duì)列,要點(diǎn)在于index的計(jì)算
class LoopQueue extends Queue {
    constructor(items) {
        super(items)
    }
    getIndex(index) {
        const length = this.items.length
        return index > length ? (index % length) : index
    }
    find(index) {
        return !this.isEmpty ? this.items[this.getIndex(index)] : null
    }
}

鏈表：存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的；每個元素由一個存儲元素本身的節(jié)點(diǎn)和一個指向下一個元素的引用（指針/鏈接）組成。

class linkNode {
  constructor(ele) {
    this.element = ele;
    this.next = null;
  }
}
class singLinkList {
  constructor() {
    this.item = [];
    this.head = null;
    this.length = 0;
  }
  append(ele) {
    const node = new linkNode(ele);
    let current = null;
    if (this.head) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      };
      current.next = node;
    }
    this.length++;
  }
  insert(pos, ele) {
    if (pos > 0 && pos <= this.length) {
      const node = new linkNode(ele);
      let current = this.head;
      let previous = null;
      let index = 0;
      if (pos === 0) {
        this.head = node;
      } else {
        while (index < pos) {
          index++;
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      this.length++;
    }
  }
  removeAt(pos) {
    if (pos > -1 && pos < this.length) {
      let current = this.head
      let previous = null
      let index = 0
      if (pos === 0) {
        this.head = current.next
      } else {
        while (index++ < pos) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      this.length--;
      return current.element
    }
  }
  findIndex(element) {
    let current = this.head
    let index = -1
    while (current) {
      if (element === current.element) {
        return index + 1
      }
      index++
      current = current.next
    }
    return -1
  }
  remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }
  size() {
    return this.length
  }
}

集合：由一組無序且唯一（即不能重復(fù)）的項(xiàng)組成；這個數(shù)據(jù)結(jié)構(gòu)使用了與有限集合相同的數(shù)學(xué)概念，但應(yīng)用在計(jì)算機(jī)科學(xué)的數(shù)據(jù)結(jié)構(gòu)中。ES6 中已內(nèi)置了 Set 類型,實(shí)現(xiàn)的要點(diǎn)在于查找是否已存在.

字典：以 [鍵，值]對為數(shù)據(jù)形態(tài)的數(shù)據(jù)結(jié)構(gòu)，其中鍵名用來查詢特定元素，類似于 Javascript 中的Object。

散列：根據(jù)關(guān)鍵碼值（Key,value）直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)；它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度；這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

處理散列表中的沖突:分離鏈接、線性探查和雙散列法。

分離鏈接法包括為散列表的每一個位置創(chuàng)建一個鏈表并將元素存儲在里面。它是解決沖突的 最簡單的方法，但是它在 HashTable 實(shí)例之外還需要額外的存儲空間。

線性探查:當(dāng)想向表中某個位置加人一個新元素的時候，如果索引為 index 的位置已經(jīng)被占據(jù)了，就嘗試 index+1的位置。如果index+1 的位置也被占據(jù)了，就嘗試 index+2 的位置，以此類推。

class HashTable {
 constructor() {
     this.table = []
   }
   // 散列函數(shù)
 static loseloseHashCode(key) {
   let hash = 0
   for (let codePoint of key) {
     hash += codePoint.charCodeAt()
   }
   return hash % 37
 }
 // 使用鏈表處理沖突
 put(key, value) {
   const position = HashTable.loseloseHashCode(key)
   if (this.table[position] === undefined) {
     this.table[position] = new LinkedList()
   }
   this.table[position].append({ key, value })
 }
 get(key) {
   const position = HashTable.loseloseHashCode(key)
   if (this.table[position] === undefined) return undefined
   const getElementValue = node => {
     if (!node && !node.element) return undefined
     if (Object.is(node.element.key, key)) {
       return node.element.value
     } else {
       return getElementValue(node.next)
     }
   }
   return getElementValue(this.table[position].head)
 }
 remove(key) {
   const position = HashTable.loseloseHashCode(key)
   if (this.table[position] === undefined) return undefined
   const getElementValue = node => {
     if (!node && !node.element) return false
     if (Object.is(node.element.key, key)) {
       this.table[position].remove(node.element)
       if (this.table[position].isEmpty) {
         this.table[position] = undefined
       }
       return true
     } else {
       return getElementValue(node.next)
     }
   }
   return getElementValue(this.table[position].head)
 }
 
   // // 使用線性探查
 // put(key, value) {
 //   const position = HashTable.loseloseHashCode(key)
 //   if (this.table[position] === undefined) {
 //     this.table[position] = { key, value }
 //   } else {
 //     let index = position+1;
 //     while (this.table[index] !== undefined) {
 //       index++
 //     }
 //     this.table[index] = { key, value }
 //   }
 // }

 // get(key) {
 //   const position = HashTable.loseloseHashCode(key)
 //   const getElementValue = index => {
 //     if (this.table[index] === undefined) return undefined
 //     if (Object.is(this.table[index].key, key)) {
 //       return this.table[index].value
 //     } else {
 //       return getElementValue(index + 1)
 //     }
 //   }
 //   return getElementValue(position)
 // }
}

樹：由 n（n>=1）個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合；把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的，基本呈一對多關(guān)系，樹也可以看做是圖的特殊形式。

節(jié)點(diǎn)

根節(jié)點(diǎn)

內(nèi)部節(jié)點(diǎn)：非根節(jié)點(diǎn)、且有子節(jié)點(diǎn)的節(jié)點(diǎn)

外部節(jié)點(diǎn)/頁節(jié)點(diǎn)：無子節(jié)點(diǎn)的節(jié)點(diǎn)

子樹：就是大大小小節(jié)點(diǎn)組成的樹

深度：節(jié)點(diǎn)到根節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量

高度：樹的高度取決于所有節(jié)點(diǎn)深度中的最大值

層級：也可以按照節(jié)點(diǎn)級別來分層

二叉樹中的節(jié)點(diǎn)最多只能有兩個子節(jié)點(diǎn)：一個是左側(cè)子節(jié)點(diǎn)，另一個是右側(cè)子節(jié)點(diǎn)。這些定 義有助于我們寫出更高效的向/從樹中插人、查找和刪除節(jié)點(diǎn)的算法。二叉樹在計(jì)算機(jī)科學(xué)中的 應(yīng)用非常廣泛。
二叉搜索樹（BST）是二叉樹的一種，但是它只允許你在左側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）小的值， 在右側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）大（或者等于）的值。

class binNode {
    constructor(key) {
        this.key = key
        this.left = null
        this.right = null
    }
}
class BinarySearchTree {
    constructor() {
        this.root = null
    }
    insert(key) {
        const newNode = new binNode(key)
        const insertNode = (node, newNode) => {
            if (newNode.key < node.key) {
                if (node.left === null) {
                    node.left = newNode
                } else {
                    insertNode(node.left, newNode)
                }
            } else {
                if (node.right === null) {
                    node.right = newNode
                } else {
                    insertNode(node.right, newNode)
                }
            }
        }
        if (!this.root) {
            this.root = newNode
        } else {
            insertNode(this.root, newNode)
        }
    }
}

圖：圖是網(wǎng)絡(luò)結(jié)構(gòu)的抽象模型；圖是一組由邊連接的節(jié)點(diǎn)（頂點(diǎn)）；任何二元關(guān)系都可以用圖來表示，常見的比如：道路圖、關(guān)系圖，呈多對多關(guān)系。

排序算法

冒泡排序：比較任何兩個相鄰的項(xiàng)，如果第一個比第二個大，則交換它們；元素項(xiàng)向上移動至正確的順序，好似氣泡上升至表面一般，因此得名。

選擇排序：每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，以此循環(huán)，直至排序完畢。

插入排序：將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，此算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為 O(n^2)。

歸并排序：將原始序列切分成較小的序列，只到每個小序列無法再切分，然后執(zhí)行合并，即將小序列歸并成大的序列，合并過程進(jìn)行比較排序，只到最后只有一個排序完畢的大序列，時間復(fù)雜度為 O(n log n)。

快速排序：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行上述遞歸排序，以此達(dá)到整個數(shù)據(jù)變成有序序列，時間復(fù)雜度為 O(n log n)。
搜索算法

順序搜索：讓目標(biāo)元素與列表中的每一個元素逐個比較，直到找出與給定元素相同的元素為止，缺點(diǎn)是效率低下。

二分搜索：在一個有序列表，以中間值為基準(zhǔn)拆分為兩個子列表，拿目標(biāo)元素與中間值作比較從而再在目標(biāo)的子列表中遞歸此方法，直至找到目標(biāo)元素。

貪心算法：在對問題求解時，不考慮全局，總是做出局部最優(yōu)解的方法。

動態(tài)規(guī)劃：在對問題求解時，由以求出的局部最優(yōu)解來推導(dǎo)全局最優(yōu)解。

復(fù)雜度概念：一個方法在執(zhí)行的整個生命周期，所需要占用的資源，主要包括：時間資源、空間資源。

參考:
數(shù)據(jù)結(jié)構(gòu)
前端數(shù)據(jù)結(jié)構(gòu)