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

標簽（空格分隔）： 未分類

棧：一種遵從先進后出 (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
    }
}

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

class Queue {
  constructor(items) {
    this.items = items || []
  }
  // 普通隊列
  enqueue(element) {
    this.items.push(element)
  }
  // 優先隊列的構造方法
  // 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
  }
}
// 循環隊列,要點在于index的計算
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
    }
}

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

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
  }
}

集合：由一組無序且唯一（即不能重復）的項組成；這個數據結構使用了與有限集合相同的數學概念，但應用在計算機科學的數據結構中。ES6 中已內置了 Set 類型,實現的要點在于查找是否已存在.

字典：以 [鍵，值]對為數據形態的數據結構，其中鍵名用來查詢特定元素，類似于 Javascript 中的Object。

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

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

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

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

class HashTable {
 constructor() {
     this.table = []
   }
   // 散列函數
 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）個有限節點組成一個具有層次關系的集合；把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，基本呈一對多關系，樹也可以看做是圖的特殊形式。

節點

根節點

內部節點：非根節點、且有子節點的節點

外部節點/頁節點：無子節點的節點

子樹：就是大大小小節點組成的樹

深度：節點到根節點的節點數量

高度：樹的高度取決于所有節點深度中的最大值

層級：也可以按照節點級別來分層

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

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)
        }
    }
}

圖：圖是網絡結構的抽象模型；圖是一組由邊連接的節點（頂點）；任何二元關系都可以用圖來表示，常見的比如：道路圖、關系圖，呈多對多關系。

排序算法

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

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

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

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

快速排序：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行上述遞歸排序，以此達到整個數據變成有序序列，時間復雜度為 O(n log n)。
搜索算法

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

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

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

動態規劃：在對問題求解時，由以求出的局部最優解來推導全局最優解。

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

參考:
數據結構
前端數據結構