数据结构学习之队列

1、什么是队列？

队列和栈有着明显的区别，队列是一种特殊的线性表有着先进先出的特点。它只允许在表头进行删除操作，在表尾进行添加操作。

入队列示意图

出队列示意图

队列有许多的应用，比如javascript的事件循环机制，就是通过事件队列来存储异步操作的回调函数。

比如逐层打印一颗树上的节点。像kafka，rabbitmq这类消息队列，其形式就是一种队列，消息生产者把消息放入队列中（尾部），消费者从队列里取出消息进行处理（头部），只不过背后的实现更为复杂。

如果你了解一点socket，那么你应该知道当大量客户端向服务端发起连接，而服务端忙不过来的时候，就会把这些请求放入到队列中，先来的先处理，后来的后处理，队列满时，新来的请求直接抛弃掉。

数据结构在系统设计中的应用非常广泛，只是我们水平达不到那个级别，知道的太少，但如果能理解并掌握这些数据结构，那么就有机会在工作中使用它们并解决一些具体的问题，当我们手里除了锤子还有电锯时，那么我们的眼里就不只是钉子，解决问题的思路也会更加开阔

2、队列的实现

首先先定义一些常用的方法：

• enqueue 从队列尾部添加一个元素
• dequeue 从队列头部删除一个元素
• head 返回头部的元素，注意，不是删除
• size 返回队列大小
• clear 清空队列
• isEmpty 判断队列是否为空
• tail 返回队列尾节点

然后我们逐一实现

let Queue = (function () {
  let items = new WeakMap() 
  // WeakMap结构与Map结构基本类似。区别是它只接受对象作为键名，
  // 不接受其他类型的值作为键名。键名是对象的弱引用，当对象被回收后，
  // WeakMap自动移除对应的键值对，WeakMap结构有助于防止内存泄漏。 
  class Queue {
    constructor() {
      items.set(this, [])
    }
    // 入队列
    enqueue(item) {
      let queue = items.get(this)
      queue.push(item)
    }
    // 出队列
    dequeue() {
      return items.get(this).shift()
    }
    // 返回队列头
    head() {
      let queue = items.get(this)
      return queue[0]
    }
    // 返回队列大小
    size() {
      let queue = items.get(this)
      return queue.length
    }
    // 清空队列
    clear() {
      items.set(this, [])
    }
    // 判断队列是否为空
    isEmpty() {
      let queue = items.get(this)
      return queue.length === 0
    }
    // 返回队尾
    tail() {
      let queue = items.get(this)
      return queue[queue.length - 1]
    }
  }
  return Queue
})
复制代码

3、队列常见的应用

3.1、约瑟夫环

有一个数组a[100]存放0--99;要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数。比如：前10个数是 0 1 2 3 4 5 6 7 8 9 10，所谓每隔两个数删掉一个数，其实就是把 2 5 8 删除掉。

思路分析

• 从队列头部删除一个元素，index+1
• 如果index%3 == 0,就说明这个元素是需要删除的元素，如果不等于0，就不是需要被删除的元素，则把它添加到队列的尾部

代码实现

// 先初始化一个数据
var arr_list = [];
for(var i=0;i< 100;i++){
    arr_list.push(i);
}
// 定义功能函数
function del(arr) {
    let queue = new Queue()
    // 将所有元素入队列
    for(var i=0;i< arr_list.length;i++){
        queue.enqueue(arr_list[i]);
    }
    let index = 0
    while(queue.size() != 1) {
        index ++
        index%3 === 0 ?  queue.enqueue(queue.dequeue()) : queue.dequeue()
    }
    return queue.head() // 返回队列中唯一的元素
}
// 调用
del(arr_list)
复制代码

3.2、用队列来实现一个栈

思路分析

• push， 实现push方法时，如果两个队列都为空，那么默认向queue_1里添加数据，如果有一个不为空，则向这个不为空的队列里添加数据

• top，两个队列，或者都为空，或者有一个不为空，只需要返回不为空的队列的尾部元素即可

• pop，pop方法是比较复杂，pop方法要删除的是栈顶，但这个栈顶元素其实是队列的尾部元素。每一次做pop操作时，将不为空的队列里的元素一次删除并放入到另一个队列中直到遇到队列中只剩下一个元素，删除这个元素，其余的元素都跑到之前为空的队列中了。

代码实现

function queueToStack() {
  let queue_1 = new Queue()
  let queue_2 = new Queue()
  let data_queue = null
  let empty_queue = null
  // 确认每个队列的用途
  let initQueue = () => {
    if (queue_1.isEmpty() && queue_2.isEmpty()) {
      data_queue = queue_1
      empty_queue = queue_2
    } else if (queue_1.isEmpty()) {
      data_queue = queue_2
      empty_queue = queue_1
    } else {
      data_queue = queue_1
      empty_queue = queue_2
    }
  }
  this.push = (item) => {
    initQueue()
    data_queue.enqueue(item)
  }
  this.top = () => {
    initQueue()
    return data_queue.tail()
  }
  this.pop = () => {
    initQueue()
    while (data_queue.size() > 1) {
      empty_queue.enqueue(data_queue.dequeue())
    }
    return data_queue.dequeue()
  }
}
复制代码

队列还有其他很多在面试中可能会问道的面试题比如：打印杨辉三角以及迷宫问题，这些用队列来实现可能会更加的方便。

4、优先队列

function PriorityQueue() {
    let items = []
    function QueueElement(element, priority) {
        this.element = element
        this.priority = priority // 设置优先级别
    }
    this.enqueue = function(element, priority) {
        let queueElement = new QueueElement(element, priority)
        let add = false
        for(let i = 0; i < items.length; i++) { // 遍历队列找到优先级比它小的元素
            if(queueElement.priority > items[i].priority) {
                items.splice(i, 0, queueElement) // 然后添加到该队列
                add = true
                break
            }
        }
        if(!add) { // 如果没有找到直接添加到队列末尾
            items.push(queueElement)
        }
    }
}
复制代码

5、循环队列

function hotPotato(nameList, num) {
    let queue = new Queue()
    for(let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
    }
    let eliminated = ''
    while(queue.size() > 1) {
        for(let i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue)
        }
        eliminated = queue.dequeue()
        console.log(eliminates + 'out')
    }
    return queue.dequeue()
}
复制代码

6、总结

在学习了队列之后与栈对比进一步了解了各个数据结构的用法，以及使用的方便之处。当然也为面试打下了基础。