队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

• 用数组实现队列

function Queue () {
  let items = []
  //向队列尾部添加一个元素
  this.enquene = function (item) {
    items.push(item)
  }
  //删除队列第一个元素
  this.dequeue = function () {
    return items.shift()
  }
  //获取队列头部元素
  this.head = function () {
    return items[0]
  }
  //获取队列尾部元素
  this.tail = function () {
    return items[items.length - 1]
  }
  //获取队列长度
  this.size = function () {
    return items.length
  }
  //判断队列是否为空
  this.isEmpty = function () {
    return items.length === 0
  }
  //清空队列
  this.clear = function () {
    items = []
  }
  this.get = function () {
    return items
  }
}

• 用队列实现约瑟夫环

let queue = new Queue()
for (let i = 0; i < 100; i++) {
  queue.enquene(i)
}
function josephRing () {
  let index = 0
  while (queue.size() !== 1) {
    index++
    const popItem = queue.dequeue()
    if (index % 3 !== 0) {
      queue.enquene(popItem)
    }
  }
  return queue.head()
}

console.log(josephRing()) //90

• 斐波那契序列

//斐波那契序列 fn = f(n-1) + f(n-2) n>=2
function fibonacci (n) {
  if (n === 0) return 0
  let queue = new Queue()
  let index = 0
  //先把起始值加入队列
  queue.enquene(1)
  queue.enquene(1)
  while (index < n - 2) {
    //弹出队列第一个元素
    const deleteItem = queue.dequeue()
    //获取队列第一个元素
    const headItem = queue.head()
    const nextItem = deleteItem + headItem
    queue.enquene(nextItem)
    index++
  }
  //最后剩两个数，第二个就是最终的结果
  return queue.tail()
}
console.log(fibonacci(0)) // 0
console.log(fibonacci(1)) // 1
console.log(fibonacci(2)) // 1
console.log(fibonacci(3)) //2
console.log(fibonacci(4)) //3
console.log(fibonacci(5)) //5
console.log(fibonacci(6)) //8

• 用队列实现栈

function Stack() {
  let queue1 = new Queue()
  let queue2 = new Queue()
  let data_queue = null
  let empty_queue = null
  //始终让有数据的队列指向data_queue
  const init_queue = function() {
    if (!queue1.isEmpty() && queue2.isEmpty()) {
      data_queue = queue1
      empty_queue = queue2
    } else if (queue1.isEmpty() && !queue2.isEmpty()) {
      data_queue = queue2
      empty_queue = queue1
    } else {
      data_queue = queue1
      empty_queue = queue2
    }
  }
  this.push = function(item) {
    init_queue()
    data_queue.enqueue(item)
  }
  this.pop = function() {
    init_queue()
    //因为队列是先进先出  利用这点 将data_queue队列的数据依次删除并添加到empty_queue中，直到data_queue剩下一个时，就可以直接删除并返回了
    while (data_queue.size() > 1) {
      empty_queue.enqueue(data_queue.dequeue())
    }
    return data_queue.dequeue()
  }
  this.top = function() {
    init_queue()
    return data_queue.tail()
  }
  this.size = function() {
    init_queue()
    return data_queue.size()
  }
  this.get = function() {
    init_queue()
    return data_queue.get()
  }
}
let stack = new Stack()
stack.push(3)
stack.push(2)
stack.push(5)
console.log(stack.get()) // [3, 2, 5]
stack.pop()
console.log(stack.get()) //[3, 2]

• 杨辉三角

function yanghui(n) {
  let line = ''
  let queue = new Queue()
  queue.enqueue(1)
  queue.enqueue(0) //用0来分割每一层的数据
  for (let i = 1; i < n; i++) {
    let prev = 0
    while (true) {
      const currnet = queue.dequeue()
      if (currnet === 0) {
        queue.enqueue(1)
        queue.enqueue(0)
        line += '\r\n'
        break
      } else {
        let newCount = prev + currnet
        prev = currnet
        queue.enqueue(newCount)
        line += ' ' + currnet
      }
    }
  }
  //因为是计算下一行的数据并将其放入队列中  所以n行的数据还在队列
  const items = queue.get()
  while (queue.size() !== 1) {
    const currnet = queue.dequeue()
    line += ' ' + currnet
  }
  //清空队列
  queue.clear()
  return line
}
console.log(yanghui(12))
/* 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
*/