队列

算法入门及简单练习——队列 - 图1

什么是队列

队列是一种特殊的线性表，只允许在队列的头部删除节点，在末尾添加新的元素。

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

常见的方法

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

实现队列的逻辑

  1. function Queue() {
  2.   const items = []
  4.   this.enqueue = function (item) {
  5.     items.push(item)
  6.   }
  8.   this.dequeue = function () {
  9.     return items.shift()
  10.   }
  12.   this.head = function () {
  13.     return items[0]
  14.   }
  16.   this.tail = function () {
  17.     return items[items.length - 1]
  18.   }
  20.   this.size = function () {
  21.     return items.length
  22.   }
  24.   this.clear = function () {
  25.     items.length = 0
  26.   }
  28.   this.isEmpty = function () {
  29.     return items.length === 0
  30.   }
  31. }

简单练习

1、约瑟夫环

题目要求

一个数组a[100]存放0~99。要求每隔两个数删掉一个数，到末尾时循环值开头继续进行，求最后一个被删掉的数。

思路

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

代码实现
  1. const test1 = [5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]
  2. const test2 = []
  3. for (let i = 0; i < 100; i++) test2.push(i)
  5. function delRing(arrList) {
  6.   const queue = new Queue()
  7.   for (let i = 0; i < arrList.length; i++) queue.enqueue(arrList[i])
  8.   let index = 0
  9.   while (queue.size() !== 1) {
  10.     index++
  11.     const takeItem = queue.dequeue()
  12.     if (index % 3 !== 0) queue.enqueue(takeItem)
  13.   }
  14.   return queue.head()
  15. }
  17. console.log(delRing(test1))
  18. console.log(delRing(test2))

2、斐波那契数列

算法入门及简单练习——队列 - 图2

题目要求

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

思路

该题有很多总解法，这里为了主题，所以采用队列的方式进行解题。
因为我们已知前两个是 0 和 1 开始。
我们从2开始进行计算，因为我们知道2是0 + 1 = 1。
所以我们直接往队列里面添加两个 1，队头表示位置 1 的值，队尾表示位置 2 的值。
接着我们根据参数循环，因为我们忽略了 0 和 1 所以循环次数为 n - 2。并且定义 index 用于记录当前循环的次数。
每次循环我们取出队头的值，在与队列中剩下的值进行相加，得出下一位的值。再将该值重新添加到队尾。
以此循环，直到循环结束后，我们的队列中会有两个值，队尾的值就是我们最终的结果。
将队尾的数值返回即可。

代码实现
  1. function fibonacci(n) {
  2.   if (n < 2) return n
  3.   const queue = new Queue()
  4.   queue.enqueue(1)
  5.   queue.enqueue(1)
  6.   let index = 0
  7.   while (index < n - 2) {
  8.     const delQueue = queue.dequeue()
  9.     queue.enqueue(delQueue + queue.head())
  10.     index++
  11.   }
  12.   return queue.tail()
  13. }

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，反之。

代码实现
  1. function QueueStack() {
  2.   const queue1 = new Queue()
  3.   const queue2 = new Queue()
  4.   let dataQueue = null
  5.   let emptyQueue = null
  7.   function initQueue() {
  8.     if (queue1.isEmpty() && queue2.isEmpty() || queue2.isEmpty()) {
  9.       dataQueue = queue1
  10.       emptyQueue = queue2
  11.     } else {
  12.       dataQueue = queue2
  13.       emptyQueue = queue1
  14.     }
  15.   }
  17.   this.push = function(item) {
  18.     initQueue()
  19.     dataQueue.enqueue(item)
  20.   }
  22.   this.pop = function() {
  23.     initQueue()
  24.     while (dataQueue.size > 1) {
  25.       emptyQueue.enqueue(dataQueue.dequeue())
  26.     }
  27.     return dataQueue.dequeue()
  28.   }
  30.   this.top = function() {
  31.     initQueue()
  32.     return dataQueue.tail()
  33.   }
  34. }

4、杨辉三角形

算法入门及简单练习——队列 - 图3

思路

我们定义一个队列，用于存放 n - 1 行的元素，以及第 n 行的元素。
例如现在循环到第二行，我们队列中应该有 [1, 1, 1]。
再循环的时候，我们观察可得，每一行的个数等于其行数。
所以这里我们可以通过 for 语句控制输出结果个数为当前循环的行数，只输出 n -1 行的数据。剩下当前 n 行的数据保留，用于下次计算。
每次只输出上一行的数据。
但是因为我们每一行计算，最后一个元素是漏了的，所以我们直接在末尾添加一个 1 即可。

代码实现
  1. function printYangHui(n) {
  2.   const queue = new Queue()
  3.   queue.enqueue(1)
  4.   for (let i = 1; i <= n; i++) {
  5.     let output = ""
  6.     let preValue = 0
  7.     for (let j = 0; j < i; j++) {
  8.       const cur = queue.dequeue()
  9.       output += cur + " "
  10.       const next = cur + preValue
  11.       preValue = cur
  12.       queue.enqueue(next)
  13.     }
  14.     queue.enqueue(1)
  15.     console.log(output)
  16.   }
  17. }

另一种实现方式基本一样，可以通过标记进行区分。遇到 0 的时候则终止输出。

  1. function printYangHui(n) {
  2.   const queue = new Queue()
  3.   queue.enqueue(1)
  4.   queue.enqueue(0)
  5.   for (let i = 1; i <= n; i++) {
  6.     let output = ''
  7.     let preValue = 0
  8.     while (true) {
  9.       const cur = queue.dequeue()
  10.       if (cur === 0) {
  11.         queue.enqueue(1)
  12.         queue.enqueue(0)
  13.         break
  14.       } else {
  15.         output += cur + " "
  16.         queue.enqueue(cur + preValue)
  17.         preValue = cur
  18.       }
  19.     }
  20.     console.log(output)
  21.   }
  22. }