面闭 —— 数据结构

知识点

时间复杂度

通常使用最差的时间复杂度来衡量一个算法的好坏。

常数时间 O(1) 代表这个操作和数据量没有关系，是一个固定时间的操作，比如说四则运算。

对于一个算法来说，可能会计算出操作次数为 aN + 1，N 代表数据量。那么该算法的时间复杂度就是 O(N)。因为在计算时间复杂度的时候，数据量通常是非常大的，这时候低阶项和常数项可以忽略不计。

当出现两个算法都是 O(N) 的时间复杂度，那么对比两个算法的好坏就要通过低阶项和常数项了。

栈

栈是一个线性结构。
栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则。

class Stack {
  constructor() {
    this.stack = []
  }
  // 进
  push(item) {
    this.stack.push(item)
  }
  // 出
  pop() {
    this.stack.pop()  // 删除并返回数组第一个
  }
  // 查看
  peek() {
    return this.stack[this.getCount() - 1] // 查看最后一个
  }
  // 获取长度
  getCount() {
    return this.stack.length
  }
  // 清空
  isEmpty() {
    return this.getCount() === 0
  }
}

队列

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

单链队列

class Queue {
  constructor() {
    this.queue = []
  }
  // 进
  enQueue(item) {
    this.queue.push(item)
  }
  // 出
  deQueue() {
    return this.queue.shift() // 删除并返回数组最后一个
  }
  getHeader() {
    return this.queue[0]
  }
  getLength() {
    return this.queue.length
  }
  isEmpty() {
    return this.getLength() === 0
  }
}

因为单链队列在出队操作的时候需要 O(n) 的时间复杂度，所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。

数组越界
比如数组定义时有十个元素，那么a[0] – a[9] 分别对应相应的元素，在程序中如果使用了a[10]那么就超出了原来的数组定义的范围，这就是数组下标越界。

循环队列？

链表

面试题

---

相关资料

前端面试之道
数组越界的意思