一、什么叫数据结构

数据结构是计算机存储、组织数据的方式。指的是相互之间存在一种或多种特定关系的数据元素的集合。-- 百度百科

• 比喻成一个企业的组织结构，组织结构其实就是部门与部门之间的关系结构。
• 数据结构就是用来描述数据与数据之间的关系
  线性和非线性数据结构

二、常见的数据结构

• 按逻辑结构分类
  线性结构：数据元素之间一对一的关系

   const arr = ['1', '2', '3'];
  

  非线性结构：数据元素之间一对多的关系

• 按储存方式分类

• 顺序存储：Set、Array

• 散列存储：Map、Object

• 链式存储：链表

• 索引储存：SQL
  
  

三、线性数据结构——栈

• 栈是一种遵从先进后出 (LIFO) 原则的有序集合

• 栈的特点：只能在某一端（只有一个口子）添加或删除数据，遵循先进后出的原则

• 插入操作在栈中被称作入栈（push）

• 删除操作栈中被称作退栈（pop）

• 使用场景：方法调用，作用域
  

• js模拟栈

class Stack {
  constructor () {
    this.stack = []
  }
  // 新增数据
  push (item) {
    return this.stack.push(item)
  }
  // 删除数据
  pop () {
    return this.stack.pop()
  }
  // 修改数据（栈中不能直接修改数据，需将数据取出后修改，再放回栈中）
  // 查 栈中只能读取最外层数据
  peek () {
    return this.stack[this.getSize() - 1]
  }
  // 获取栈内有多少条数据
  getSize () {
    return this.stack.length
  }
  // 检测栈内数据是否为空
  isEmpty () {
    return this.getSize() === 0
  }
  
}

• 栈的应用：

有效的括号（力扣）

给定一个只包括’(’，’)’，’{’，’}’，’[’，’]'的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

• 解题思路

1. 用栈模拟括号的顺序
2. 可以创建一个对象，建立左右括号的对应关系，key 为左括号，value 为右括号
3. 遍历字符串的每一个字符
4. 如果是左括号，入栈
5. 如果是右括号，判断栈顶的第一个元素与当前右括号是否对应？如果不对应，就返回 false
6. 遍历完之后保证栈内为空

class Stack {
  constructor () {
    this.stack = []
  }
  // 新增数据
  push (item) {
    return this.stack.push(item)
  }
  // 删除数据
  pop () {
    return this.stack.pop()
  }
  // 修改数据（栈中不能直接修改数据，需将数据取出后修改，再放回栈中）
  // 查 栈中只能读取最外层数据
  peek () {
    return this.stack[this.getSize() - 1]
  }
  // 获取栈内有多少条数据
  getSize () {
    return this.stack.length
  }
  // 检测栈内数据是否为空
  isEmpty () {
    return this.getSize() === 0
  }
  
}

/**
* @description:
* @param {string} str
* @return: boolean
*/
let isValid = function (str) {
  // 创建一个对象，建立左右括号的对应关系，key 为左括号，value 为右括号
  const Map = {
    '{' : '}',
    '(' : ')',
    '[' : ']'
  }
  const myStack =  new Stack()
  for (item of str) {
    // 判断是否为左括号
    if (Map[item]) {
      myStack.push(item)
    } else {
      const last = myStack.pop()
      // 判断是是与之对应的右括号
      if (item !== Map[last]) return false
    }
  }
  // 保证栈内为空
  return myStack.getSize() === 0
}

// isValid('()') // true
isValid('(]){}') // false

四、线性数据结构——队列

• 队列是一种遵从先进先出 (FIFO) 原则的有序集合

• 队列一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。

• 插入（insert）操作也称作入队（enqueue）

• 删除（delete）操作也被称为出队（dequeue)

• js模拟队列

class Queue {
  constructor () {
    this.queue = []
  }
  // 入队（增）
  enQueue (item) {
    return this.queue.push(item)
  }
  // 出队（删）
  deQueue () {
    return this.queue.shift()
  }
  // 要修改队列中的数据也是需要将数局先取出来修改然后在将其放回
  // 获得队列中第一个数据
  getHeader () {
    return this.queue[0]
  }
  // 获取队列的大小
  getSize () {
    return this.queue.length
  }
  // 判断队列是否为空吗
  isEmpty () {
    return this.getSize() === 0
  }
}

• 队列的应用

数据流中的移动平均值（力扣）

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

示例:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

• 解题思路

1. 使用队列添加整数
2. 创建成员变量来保存计算的值
3. 新增整数，进行入队操作
4. 累加整数并保存
5. 如果队列大小超出窗口大小，进行出队操作，并对成员变量进行减法。
6. 返回平均值

class Queue {
  constructor () {
    this.queue = []
  }
  // 入队（增）
  enQueue (item) {
    return this.queue.push(item)
  }
  // 出队（删）
  deQueue () {
    return this.queue.shift()
  }
  // 要修改队列中的数据也是需要将数局先取出来修改然后在将其放回
  // 获得队列中第一个数据
  getHeader () {
    return this.queue[0]
  }
  // 获取队列的大小
  getSize () {
    return this.queue.length
  }
  // 判断队列是否为空吗
  isEmpty () {
    return this.getSize() === 0
  }
}

let MovingAverage = function(size) {
  this.windowSize = size
  this.myQueue = new Queue()
  this.sum = 0
  console.log('0000')
}
/**
* @description:
* @param {number} val
* @return: {number}
*/
MovingAverage.prototype.next = function(val) {
  // 超出窗口大小就让第一个元素出队，累加和减去这个值
  if (this.myQueue.getSize() >= this.windowSize) {
    this.sum -= this.myQueue.getHeader()
    this.myQueue.deQueue()
  }
  this.myQueue.enQueue(val)
  this.sum += val
  console.log('sum', sum)
  return this.sum / this.myQueue.getSize()
}