数据结构与算法

概述

程序 = 数据结构 + 算法，数据结构和算法与语言无关，数据结构是管理和存储数据的方法，算法是解决问题的方法。

常用数据结构

• 数组
• 栈
• 队列
• 堆
• 链表
• 散列表（hash）
• 树

1.数组

数组是一种很灵活的数据结构，可以从数组头部shift、unshift，也可以从数组尾部push、pop，从数组的任意位置插入元素array[index] = a,可以删除任意位置的元素，array.splice(index, 1) 并且操作过程中，数组会自动维护元素的索引以及自身的长度。比如下图，删除元素2，那么2后面的元素3、4、5会自动更新索引，数组的长度也会自动更新为4.（这也是为什么数组头部删除元素（unshift）比数组尾部删除元素（pop）性能要差不少的原因。unshift操作的开销更大）

数组.png

2.栈

栈相对于数组而言就是一种限制性比较强的数据结构。只能从栈顶入栈和出栈，并且要遵循后进先出（LIFO）的原则，如下图无法直接删除元素3，必须先删除元素4才能删除元素3.因为4比3先入栈，根据LIFO原则，4必须必3出栈。

栈.png

下面我们使用数组来实现一个简单的栈模型

class Stack {
  constructor () {
    this._items = []
  }
  // 入栈
  push (item) {
    this._items.push(item)
  }
  // 出栈
  pop () {
    return this._items.pop()
  }
  // 取栈顶元素
  peek () {
    return this._items[this._items.length - 1]
  }
  // 判断是否为空
  isEmpty () {
    return this._items.length === 0
  }
  // 得到栈的大小
  getSize () {
    return this._items.length
  }
}

然后我们利用这个栈模型做一个小小的实践，把10进制的数据转成2进制。原理就是除2取余把结果拼到一起然后倒序。比如把57转为2进制
57 / 2 = 28 余 1
28 / 2 = 19 余 0
19 / 2 = 9 余 1
9 / 2 = 4 余 1
4 / 2 = 2 余 0
2 / 2 = 1 余 0
1 / 2 = 0 余 1
结果拼起来1011001，倒序之后拿到最终结果为1001101，下面使用代码来实现

function decimalToBinary （decimal）{
  let stack = new Stack()
  let str = ''
  while (decimal > 0) {
    let redecimal = decimal % 2
    stack.push(redecimal)
    decimal = Math.floor(decimal / 2)
  }
  while (!stack.isEmpty()) {
     str += stack.pop()
  }
  return str
}
// 调用
decimalToBinary(57) // 1001101

3.队列

队列跟栈的不同在于队列是元素从队尾入栈，从队首出栈。先入先出（FIFO）如下图

队列.png

                                   **未完待续**