数据结构与算法学习

书： 《数据结构与算法JavaScript描述》--Michael McMillan

1.JavaScript的编程环境和模型

（1）JavaScript 拥有的是函数作用域，其含义是 JavaScript 中没有块级作用域，这一点有别于其他很多现代编程语言。

2. 数组

数组的标准定义是：一个存储元素的线性集合（collection），元素可以通过索引来任意存取。

2.4.3 从数组中间位置添加和删除元素

两种操作都需要将数组中的剩余元素向前或向后移，然而 splice() 方法可以帮助我们执行其中任何一种操作

var nums = [1,2,3,7,8,9];
var newElements = [4,5,6];
nums.splice(3,0,newElements);
print(nums); // 1,2,3,4,5,6,7,8,9

var nums = [1,2,3,100,200,300,400,4,5];
nums.splice(3,4);
print(nums); // 1,2,3,4,5

2.4.4 为数组排序

1. reverse()
2. sort

var names = ["David","Mike","Cynthia","Clayton","Bryan","Raymond"];
names.sort();
print(names); // Bryan,Clayton,Cynthia,David,Mike,Raymond

var nums = [3,1,2,100,4,200];
nums.sort();
print(nums); // 1,100,2,200,3,4

sort() 方法是按照顺序对元素进行排序的，因此它假定元素都是字符串类型，在上一
个例子中，即使元素是数字类型，也被认为是字符串类型。为了让 sort() 方法也能排序数
字类型的元素，可以在调用方法时传入一个大小比较函数，排序时，sort() 方法将会根据
该函数比较数组中两个元素的大小，从而决定整个数组的顺序

function compare(num1, num2) {
return num1 - num2;
}
var nums = [3,1,2,100,4,200];
nums.sort(compare);
print(nums); // 1,2,3,4,100,200

sort() 函数使用了 compare() 函数对数组按照数字大小进行排序，而不是按照字典顺序

2. 二维数组

2.6.2 处理二维数组的元素

4. 栈

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。
后进先出，咖啡厅内的一摞盘子是现实世界中常见的栈的例子

// 实现一个栈
export function Stack() {
  this.dataStore = []
  this.top = 0
  this.push = push
  this.pop = pop
  this.peek = peek
  this.clear = clear
  this.length = length
}

function push(element) {
  this.dataStore[this.top++] = element
}

function pop() {
  return this.dataStore[--this.top]
}

function peek() {
  return this.dataStore[this.top - 1]
}

function clear() {
  this.top = 0
}

function length() {
  return this.top
}

    var s = new Stack()
    s.push('David-1')
    s.push('David-2')
    console.log('peek', s.peek())
    console.log('top:', s.top)
    s.pop()
    console.log('peek', s.peek())

应用：
利用栈将一个数字从一种数制转换成另一种数制

    mulBase(num, base) {
      const s = new Stack()
      do {
        s.push(num % base)
        num = Math.floor(num /= base)
      } while (num > 0)

      let converted = ""
      while(s.length() > 0) {
        converted += s.pop()
      }
      return converted
    }

    const newNum = this.mulBase(32, 2)
    console.log('32 convert to 二进制', newNum) // 32 convert to 二进制 100000