Atrist

# 什么是队列

队列也称先进先出(FIFO), 它一般使用数组来实现， 有如下的规定

  1. 只能从队尾插入
  2. 只能从队头删除

# 代码的实现

在JavaScript中实现队列还是比较简单的，借助 Array的shift (opens new window), push (opens new window)两个方法就可以实现。

# 入队

Array.push

# 出队

Array.shift

# 应用

在 树 的 层序遍历中，一般会使用队列来记录, 同一层级的节点

function dfs(tree){
  let queue = [tree]
  while(queue.length){
    let node = queue.shift()
    // 层序遍历
    console.log(node.val)
    node.left && queue.push(node.left)
    node.right && queue.push(node.right)
  }
}

# 手动实现

在这里可以使用标记队头位置和队尾位置的方式， 进行手动实现一个效率较高的队列

class queue {
  constructor(){
    this.array = []
    this.head = 0
  }
  push(val){
    this.array.push(val)
  }
  shift(){
    if(this.head <= this.array.length){
      return this.array[this.head++]
    }else{
      return null
    }
  }
}

# leetcode 题目

641，406，899

← 链表 →