[数据结构与算法]重学数据结构与算法（一）

重学数据结构与算法（一）

· 栈：一种受限制的线性表，遵循后进先出（LIFO）原则

/* 栈Stack */

// 利用js中的Array实例和方法实现一个Stack类
class Stack {
  constructor () {
    this.item = []
  }
  // 压栈
  push (val) {
    this.item.push(val)
  }
  // 出栈
  pop () {
    return this.item.pop()
  }
  // 取栈顶元素
  peek () {
    return this.item[this.item.length - 1]
  }
  // 栈中元素的个数
  size () {
    return this.item.length
  }
  // 判断栈是否为空
  isEmpty () {
    return this.item.length === 0
  }
  // 清空栈
  clear () {
    this.item = []
  }
}
/* 
扩展：清空数组的方法
  1. 赋值为空数组 this.item = []
  2. 将数据的length = 0 
  3. 用splice方法 this.item.splice(0, this.item.length)
*/
const stack = new Stack()
stack.push(1)
stack.push(2)
console.log(stack.size()) // 2

·栈的应用：进制转换

// 将十进制转为二进制
const toBinary = function (num) {
  // 实例化一个栈
  const stack = new Stack()
  let str = ''
  // 除二取余
  while (num > 0) {
    stack.push(num % 2)
    num = Math.floor(num / 2)
  }
  // 出栈
  while (!stack.isEmpty()) {
    str += stack.pop()
  }
  return str
}
console.log(toBinary(100)) // 1100100

· JS中栈的应用

• JS调用栈

  1. js调用栈： 用来存储所有执行上下文的执行栈
  2. 执行上下文： 全局执行上下文、函数执行上下文、eval执行上下文
  3. 执行机制： js引擎先创建全局执行上下文，将全局执行上下文压入执行栈底，当一个函数被调用时，js引擎会创建函数执行上下文，把函数执行上下文压入栈顶，当函数执行完毕，函数执行上下文会弹出并销毁，将执行下一位于栈顶的执行上下文

• 递归

  /* 
  递归的优化：尾递归
  	顾名思义，尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。
  */
  // 普通递归实现Fibonacci函数
  function fiboncci (n) {
    if (n <= 2) {
      return 1
    }
    return fiboncci(n-1) + fiboncci(n-2)
  }
  // 尾递归实现Fibonacci函数
  function _fiboncci (n, ac1 = 1, ac2 = 1) {
    if (n <= 2) {
      return ac2
    }
    return _fiboncci(n-1, ac2, ac1 + ac2)
  }