数据结构与算法

为什么要学习数据结构与算法

1.数据结构+算法=程序
2.代码化繁为简
3.提高代码性能
4.提高面试通过率

栈

栈的概念

1. 栈是一种遵从后进先出原则的有序集合
2. 添加新元素的一端称为栈顶，另一端称为栈底
3. 操作栈的元素时，只能从栈顶操作（添加、移除或取值）

栈的实现

1. push（）入栈方法
2. pop（）出栈方法
3. top（）获取栈顶值
4. size（）获取栈的元素个数
5. clear（）清空栈

class Stack {
  constructor () {
    // 存储栈的数据
    this.data = {}
    // 记录栈的数据个数（相当于数组的 length）
    this.count = 0
  }
  // push() 入栈方法
  push (item) {
    // 方式1：数组方法 push 添加
    // this.data.push(item)
    // 方式2：利用数组长度
    // this.data[this.data.length] = item
    // 方式3：计数方式
    this.data[this.count] = item
    // 入栈后，count 自增
    this.count++
  }
  // pop() 出栈方法
  pop () {
    // 出栈的前提是栈中存在元素，应先行检测
    if (this.isEmpty()) {
      console.log('栈为空！')
      return
    }
    // 移除栈顶数据
    // 方式1：数组方法 pop 移除
    // return this.data.pop()
    // 方式2：计数方式
    const temp = this.data[this.count - 1]
    delete this.data[--this.count]
    return temp
  }
  // isEmpty() 检测栈是否为空
  isEmpty () {
    return this.count === 0
  }
  // top() 用于获取栈顶值
  top () {
    if (this.isEmpty()) {
      console.log('栈为空！')
      return
    }
    return this.data[this.count - 1]
  }
  // size() 获取元素个数
  size () {
    return this.count
  }
  // clear() 清空栈
  clear () {
    this.data = []
    this.count = 0
  }
}


const s = new Stack()
s.push('a')
s.push('b')
s.push('c')

每日温度（LeetCode精选题目）

/**
 * @param {number[]} T 每日温度数组 [73, 74, 75, 71, 69, 72, 76, 73]
 * @return {number[]} 等待天数列表 [1, 1, 4, 2, 1, 1, 0, 0]
 */
var dailyTemperatures = function(T) {
  // 创建单调栈用于记录（存储索引值，用于记录天数）
  const stack = [0]
  let count = 1

  // 创建结果数组（默认将结果数组使用 0 填充）
  const len = T.length
  const arr = new Array(len).fill(0)

  // 遍历 T
  for (let i = 1; i < len; i++) {
    let temp = T[i]
    // 使用 temp 比较栈顶值，如果栈顶值小，出栈（计算日期差，并存储），并重复操作
    //  - stack[count - 1] 代表栈顶值
    while (count && temp > T[stack[count - 1]]) {
      // 出栈
      let index = stack.pop()
      count--
      // 计算 index 与 i 的差，作为 index 位置的升温日期的天数使用 
      arr[index] = i - index
    }
    // 处理完毕，当前温度入栈（等待找到后续的更大温度）
    stack.push(i)
    count++
  }
  return arr
}

队列

队列的概念

1. 队列是一种遵从先进先出原则的有序集合
2. 添加新元素的一端称为队尾，另一端称为队首

队列的实现

1. enqueue（）入队方法
2. dequeue（）出队方法
3. top（）获取队首值
4. size（）获取队列的元素个数
5. clear（）清空队列

class Queue {
  constructor () {
    // 用于存储队列数据
    this.queue = []
    this.count = 0
  }
  // 入队方法
  enQueue (item) {
    this.queue[this.count++] = item
  }
  // 出队方法
  deQueue () {
    if (this.isEmpty()) {
      return
    }
    // 删除 queue 的第一个元素
    // delete this.queue[0]
    // 利用 shift() 移除数组的第一个元素
    this.count--
    return this.queue.shift()
  }
  isEmpty () {
    return this.count === 0
  }
  // 获取队首元素值
  top () {
    if (this.isEmpty()) {
      return
    }
    return this.queue[0]
  }
  size () {
    return this.count
  }
  clear () {
    // this.queue = []
    this.length = 0
    this.count = 0
  }
}

const q = new Queue()

双端队列

双端队列指的是允许同时从队尾和队首两端进行存取操作的队列，操作更加灵活
双端队列与JavaScript中的数组操作十分相似，只是不允许在数组两端以外的位置进行存取操作

双端队列实现

6. addFront/addBack
7. removeFront/removeBack
8. frontTop/backTop

class Deque {
  constructor () {
    this.queue = {}
    this.count = 0
    this.head = 0
  }
  // 队首添加
  addFront (item) {
    this.queue[--this.head] = item
  }
  // 队尾添加
  addBack (item) {
    this.queue[this.count++] = item
  }
  // 队首删除
  removeFront () {
    if (this.isEmpty()) {
      return
    }
    const headData = this.queue[this.head]
    delete this.queue[this.head++]
    return headData
  }
  // 队尾删除
  removeBack () {
    if (this.isEmpty()) {
      return
    }
    const backData = this.queue[this.count - 1]
    delete this.queue[--this.count]
    // this.count-- 与 上一步 this.count - 1 合并
    return backData
  }
  // 获取队首值
  frontTop () {
    if (this.isEmpty()) {
      return
    }
    return this.queue[this.head]
  }
  // 获取队尾值
  backTop () {
    if (this.isEmpty()) {
      return
    }
    return this.queue[this.count - 1]
  }
  isEmpty () {
    return this.size() === 0
  }
  size () {
    return this.count - this.head
  }
}

const deq = new Deque()

队列的最大值（LeetCode精选题目）

var MaxQueue = function() {
  // 存储队列数据
  this.queue = {}
  // 双端队列维护最大值（每个阶段的最大值）
  this.deque = {}
  // 准备队列相关的数据
  this.countQ = this.countD = this.headQ = this.headD = 0
};

/** 队尾入队
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
  // 数据在 queue 入队
  this.queue[this.countQ++] = value
  // 检测是否可以将数据添加到双端队列
  //   - 队列不能为空
  //   - value 大于队尾值
  while (!this.isEmptyDeque() && value > this.deque[this.countD - 1]) {
    // 删除当前队尾值
    delete this.deque[--this.countD]
  }
  // 将 value 入队
  this.deque[this.countD++] = value
};

/** 队首出队
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
  if (this.isEmptyQueue()) {
    return - 1
  }
  // 比较 deque 与 queue 的队首值，如果相同，deque 出队，否则 deque 不操作
  if (this.queue[this.headQ] === this.deque[this.headD]) {
    delete this.deque[this.headD++]
  }
  // 给 queue 出队，并返回
  const frontData = this.queue[this.headQ]
  delete this.queue[this.headQ++]
  return frontData
};

/** 获取队列最大值
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
  if (this.isEmptyDeque()) {
    return -1
  }
  // 返回 deque 队首值即可
  return this.deque[this.headD]
};

/** 检测队列 deque 是否为空
 * 
 */
MaxQueue.prototype.isEmptyDeque = function () {
  return !(this.countD - this.headD)
};

/** 检测队列 Queue 是否为空
 * 
 */
MaxQueue.prototype.isEmptyQueue = function () {
  return !(this.countQ - this.headQ)
};

滑动窗口的最大值（LeetCode精选题目）

/**
 * @param {number[]} nums 传入数组
 * @param {number} k 滑动窗口宽度
 * @return {number[]} 
 */
var maxSlidingWindow = function(nums, k) {
  if (k <= 1) {
    return nums
  }
  const result = []
  const deque = []
  // 1 将窗口第一个位置的数据添加到 deque 中，保持递减
  deque.push(nums[0])
  let i = 1
  for (; i < k; i++) {
    // - 存在数据
    // - 当前数据大于队尾值
    //   - 出队，再重复比较
    while (deque.length && nums[i] > deque[deque.length - 1]) {
      deque.pop()
    }
    deque.push(nums[i])
  }
  // 将第一个位置的最大值添加到 result
  result.push(deque[0])

  // 2 遍历后续的数据
  const len = nums.length
  for (; i < len; i++) {
    // 同上进行比较
    while (deque.length && nums[i] > deque[deque.length - 1]) {
      deque.pop()
    }
    deque.push(nums[i])
    // 检测当前最大值是否位于窗口外
    if (deque[0] === nums[i - k]) {
      deque.shift()
    }
    // 添加最大值到 result
    result.push(deque[0])
  }

  return result
};