概念

队列是遵循先进先出（FIFO）原则的一组有序的项。队列在尾部添加新的元素，并从顶部移除元素。

队列实现

普通队列

  1. function Queue() {
  2.     let items = [];
  4.   // 相对列添加新的元素
  5.   this.enqueue = function(element) {
  6.       items.push(element);
  7.   }
  9.   // 从队列移除元素
  10.   this.dequeue = function() {
  11.       return items.shift();
  12.   }
  14.   // 查看队列头元素
  15.   this.front = function() {
  16.       return items[0];
  17.   }
  19.   // 检查队列是否为空
  20.   this.isEmpty = function() {
  21.       return items.length == 0;
  22.   }
  24.   // 打印队列元素
  25.   this.print = function() {
  26.       console.log(items.toString());
  27.   }
  29.   // 队列的长度
  30.   this.size = function() {
  31.       return items.length;
  32.   }
  33. }

优先队列

  1. function PriorityQueue() {
  2.     let items = [];
  4.     function QueueItem(ele, priority) {
  5.         this.element = ele;
  6.         this.priority = priority;
  7.     }
  9.     // 入队 要考虑优先级
  10.     this.enqueue = function (ele, priority) {
  11.         let queueItem = new QueueItem(ele, priority);
  12.         let added = false;
  14.         for (let i = 0; i < items.length; i++) {
  15.             if (queueItem.priority < items[i].priority) {
  16.                 items.splice(i, 0, queueItem);
  17.                 added = true;
  18.                 break;
  19.             }
  20.         }
  21.         if (!added) {
  22.             items.push(queueItem);
  23.         }
  24.     };
  26.     this.print = function () {
  27.         for (let i = 0; i < items.length; i++) {
  28.             console.log(`${items[i].element} - ${items[i].priority}`)
  29.         }
  30.     };
  32.     // 其他的方法，逻辑和普通队列相同
  33. }
  35. // 注：优先级 1 > 2
  36. let priorityQueue = new PriorityQueue();
  37. priorityQueue.enqueue("John", 2);
  38. priorityQueue.enqueue("Jack", 1);
  39. priorityQueue.enqueue("Camila", 1);
  40. priorityQueue.print();

循环队列

  1. // 击鼓传花游戏
  2. function hotPotato(nameList, num) {
  3.     let queue = new Queue();
  5.   for (let i=0; i<nameList.length; i++) {
  6.       queue.enqueue(nameList[i]);
  7.   }
  9.   let eliminated = '';
  11.   while(queue.size() > 1) {
  12.       for (let i=0; i<num; i++) {
  13.       // 将队列首尾进行连接
  14.         queue.enqueue(queue.dequeue());
  15.     }
  16.     eliminated = queue.dequeue();
  17.     console.log(eliminated + '被淘汰。');
  18.   }
  20.   return queue.dequeue();
  21. }
  23. let names = ['John','Jack','Camila','Ingrid','Carl'];
  24. let winner = hotPotato(names, 7);
  25. console.log(winner)  // 输出：John