关于前端:算法入门及简单练习队列

队列

什么是队列

队列是一种非凡的线性表，只容许在队列的头部删除节点，在开端增加新的元素。

在咱们现实生活中，超市排队结账就是一个典型的例子。
第一个排队的结账后，从队列头部来到。想要结账的须要在队尾进来期待。

常见的办法

• enqueue 从队列尾部增加一个元素（我也结账了，过去排队）
• dequeue 从队列头部删除一个元素（我结账好了，来到队伍）
• head 返回头部元素（我看看谁排在了最后面）
• size 返回队列的大小（有多少集体在排队呢？）
• clear 清空队列（11 点啦，够钟关门了。全副人来到队伍）
• isEmpty 判断队列是否为空（我看看有没有人在排队）
• tail 返回队尾元素（我看看当初谁在最初面）

实现队列的逻辑

function Queue() {const items = []

  this.enqueue = 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.clear = function () {items.length = 0}

  this.isEmpty = function () {return items.length === 0}
}

简略练习

1、约瑟夫环

题目要求

一个数组 a[100] 寄存 0~99。要求每隔两个数删掉一个数，到开端时循环值结尾持续进行，求最初一个被删掉的数。

思路

咱们剖析一下，每隔两个删除一个元素，即删除第三个元素。
因为题意循环完结后，需从头再来过。
由此咱们能够借用队列的模式，将数据全副存到队列中。
通过循环该队列，并定义 index 记录以后的地位。当 index 为 3 的倍数的时候，咱们删除该元素，否则咱们将该元素从新加到队头。以此循环上来，直至队列中只剩下一个元素为止。
最初咱们返回队头的元素，就是咱们最初的后果。

代码实现

const test1 = [5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]
const test2 = []
for (let i = 0; i < 100; i++) test2.push(i)

function delRing(arrList) {const queue = new Queue()
  for (let i = 0; i < arrList.length; i++) queue.enqueue(arrList[i])
  let index = 0
  while (queue.size() !== 1) {
    index++
    const takeItem = queue.dequeue()
    if (index % 3 !== 0) queue.enqueue(takeItem)
  }
  return queue.head()}

console.log(delRing(test1))
console.log(delRing(test2))

2、斐波那契数列

题目要求

该数列由 0 和 1 开始，前面的每一项数字都是后面两项数字的和。求第 n 个时的后果。

思路

该题有很多总解法，这里为了主题，所以采纳队列的形式进行解题。
因为咱们已知前两个是 0 和 1 开始。
咱们从 2 开始进行计算，因为咱们晓得 2 是 0 + 1 = 1。
所以咱们间接往队列外面增加两个 1，队头示意地位 1 的值，队尾示意地位 2 的值。
接着咱们依据参数循环，因为咱们疏忽了 0 和 1 所以循环次数为 n – 2。并且定义 index 用于记录以后循环的次数。
每次循环咱们取出队头的值，在与队列中剩下的值进行相加，得出下一位的值。再将该值从新增加到队尾。
以此循环，直到循环完结后，咱们的队列中会有两个值，队尾的值就是咱们最终的后果。
将队尾的数值返回即可。

代码实现

function fibonacci(n) {if (n < 2) return n
  const queue = new Queue()
  queue.enqueue(1)
  queue.enqueue(1)
  let index = 0
  while (index < n - 2) {const delQueue = queue.dequeue()
    queue.enqueue(delQueue + queue.head())
    index++
  }
  return queue.tail()}

3、用队列实现栈

通过应用队列实现栈的 3 个基本操作，push、pop、top。

思路

咱们定义两个队列 queue1 和 queue2，并定义两个变量 dataQueue 和 emptyQueue。
定义 initQueue 办法，能够将空队列保留到 emptyQueue 变量中。将存放数据的队列保留到 dataQueue 中。
当咱们 push、pop、top 的时候都须要执行一遍 initQueue 办法。
push 的时候，咱们就是往 dataQueue 中增加咱们的数据即可。
pop 的时候，咱们须要有将队尾的元素删除，然而队列只能从队头进来。咱们能够先把 dataQueue 中的数据顺次 dequeue 并增加到 emptyQueue 中，直到 dataQueue 的 size 为 1 时，就阐明达到了队尾。此时咱们在 dequeue 这个元素即可。删除后，dataQueue 为空。在下次 initQueue 后，dataQueue 本来的地址将指向 emptyQueue，反之。

代码实现

function QueueStack() {const queue1 = new Queue()
  const queue2 = new Queue()
  let dataQueue = null
  let emptyQueue = null
  
  function initQueue() {if (queue1.isEmpty() && queue2.isEmpty() || queue2.isEmpty()) {
      dataQueue = queue1
      emptyQueue = queue2
    } else {
      dataQueue = queue2
      emptyQueue = queue1
    }
  }
  
  this.push = function(item) {initQueue()
    dataQueue.enqueue(item)
  }
  
  this.pop = function() {initQueue()
    while (dataQueue.size > 1) {emptyQueue.enqueue(dataQueue.dequeue())
    }
    return dataQueue.dequeue()}
  
  this.top = function() {initQueue()
    return dataQueue.tail()}
}

4、杨辉三角形

思路

咱们定义一个队列，用于寄存 n – 1 行的元素，以及第 n 行的元素。
例如当初循环到第二行，咱们队列中应该有 [1, 1, 1]。
再循环的时候，咱们察看可得，每一行的个数等于其行数。
所以这里咱们能够通过 for 语句管制输入后果个数为以后循环的行数，只输入 n -1 行的数据。剩下以后 n 行的数据保留，用于下次计算。
每次只输入上一行的数据。
然而因为咱们每一行计算，最初一个元素是漏了的，所以咱们间接在开端增加一个 1 即可。

代码实现

function printYangHui(n) {const queue = new Queue()
  queue.enqueue(1)
  for (let i = 1; i <= n; i++) {
    let output = ""
    let preValue = 0
    for (let j = 0; j < i; j++) {const cur = queue.dequeue()
      output += cur + " "
      const next = cur + preValue
      preValue = cur
      queue.enqueue(next)
    }
    queue.enqueue(1)
    console.log(output)
  }
}

另一种实现形式根本一样，能够通过标记进行辨别。遇到 0 的时候则终止输入。

function printYangHui(n) {const queue = new Queue()
  queue.enqueue(1)
  queue.enqueue(0)
  for (let i = 1; i <= n; i++) {
    let output = ''
    let preValue = 0
    while (true) {const cur = queue.dequeue()
      if (cur === 0) {queue.enqueue(1)
        queue.enqueue(0)
        break
      } else {
        output += cur + " "
        queue.enqueue(cur + preValue)
        preValue = cur
      }
    }
    console.log(output)
  }
}