隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

• 用數(shù)組實(shí)現(xiàn)隊(duì)列

function Queue () {
  let items = []
  //向隊(duì)列尾部添加一個(gè)元素
  this.enquene = function (item) {
    items.push(item)
  }
  //刪除隊(duì)列第一個(gè)元素
  this.dequeue = function () {
    return items.shift()
  }
  //獲取隊(duì)列頭部元素
  this.head = function () {
    return items[0]
  }
  //獲取隊(duì)列尾部元素
  this.tail = function () {
    return items[items.length - 1]
  }
  //獲取隊(duì)列長(zhǎng)度
  this.size = function () {
    return items.length
  }
  //判斷隊(duì)列是否為空
  this.isEmpty = function () {
    return items.length === 0
  }
  //清空隊(duì)列
  this.clear = function () {
    items = []
  }
  this.get = function () {
    return items
  }
}

• 用隊(duì)列實(shí)現(xiàn)約瑟夫環(huán)

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
  //先把起始值加入隊(duì)列
  queue.enquene(1)
  queue.enquene(1)
  while (index < n - 2) {
    //彈出隊(duì)列第一個(gè)元素
    const deleteItem = queue.dequeue()
    //獲取隊(duì)列第一個(gè)元素
    const headItem = queue.head()
    const nextItem = deleteItem + headItem
    queue.enquene(nextItem)
    index++
  }
  //最后剩兩個(gè)數(shù)，第二個(gè)就是最終的結(jié)果
  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

• 用隊(duì)列實(shí)現(xiàn)棧

function Stack() {
  let queue1 = new Queue()
  let queue2 = new Queue()
  let data_queue = null
  let empty_queue = null
  //始終讓有數(shù)據(jù)的隊(duì)列指向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()
    //因?yàn)殛?duì)列是先進(jìn)先出  利用這點(diǎn) 將data_queue隊(duì)列的數(shù)據(jù)依次刪除并添加到empty_queue中，直到data_queue剩下一個(gè)時(shí)，就可以直接刪除并返回了
    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來(lái)分割每一層的數(shù)據(jù)
  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
      }
    }
  }
  //因?yàn)槭怯?jì)算下一行的數(shù)據(jù)并將其放入隊(duì)列中  所以n行的數(shù)據(jù)還在隊(duì)列
  const items = queue.get()
  while (queue.size() !== 1) {
    const currnet = queue.dequeue()
    line += ' ' + currnet
  }
  //清空隊(duì)列
  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
*/