手写题：队列

Queue和Stack有一些类似，不同的是Stack是先进后出，而Queue是先进先出。Queue在生活中的例子比如排队上公交，排在第一个的总是最先上车;又比如打印机的打印队列，排在前面的最先打印。

• Queue一般具有以下常见方法：
• enqueue：入列，向队列尾部增加一个元素
• dequeue：出列，移除队列头部的一个元素并返回被移除的元素
• front：获取队列的第一个元素
• isEmpty：判断队列是否为空
• size：获取队列中元素的个数

数组实现

Javascript中的Array已经具备了Queue的一些特性，所以我们可以借助Array实现一个Queue类型：

function Queue() { 
  var collection = []; 
 
  this.print = function () { 
    console.log(collection); 
  } 
 
  this.enqueue = function (element) { 
    collection.push(element); 
  } 
 
  this.dequeue = function () { 
    return collection.shift(); 
  } 
 
  this.front = function () { 
    return collection[0]; 
  } 
 
  this.isEmpty = function () { 
    return collection.length === 0; 
  } 
 
  this.size = function () { 
    return collection.length; 
  } 
} 

简单实现

class Queue {
    constructor() {
        this.list = []
        this.frontIndex = 0
        this.tailIndex = 0
    }
    enqueue(item) {
        this.list[this.tailIndex++] = item
    }
    unqueue() {
        const item  = this.list[this.frontIndex]
        this.frontIndex++        
        return item
    }
}

循环队列

提示💡

1. 定义循环变量 front 和 rear：

   • front 指向队列头部第 1 个有效数据的位置；
   • rear 指向队列尾部（即最后 1 个有效数据）的下一个位置，即下一个从队尾入队元素的位置；

2. 为了避免「队列为空」和「队列为满」的判别条件冲突，有意浪费了一个位置：

   • 判别队列为空的条件是：front == rear；
   • 判别队列为满的条件是：(rear + 1) % capacity == front；可以这样理解，当 rear 循环到数组的前面，要从后面追上 front，还差一格的时候，判定队列为满；

3. 因为有循环的出现，要特别注意处理数组下标可能越界的情况；指针后移的时候 下标 +1 ，并且为了防止数组下标越界要取模；

class Queue {
  constructor(size) {
    this.size = size + 1; // 长度需要限制, 来达到空间的利用, 代表空间的长度
    this.list = [];
    this.font = 0; // 指向首元素
    this.rear = 0; // 指向准备插入元素的位置
  }
  enQueue(value) {
    if (this.isFull() == true) {
      return false;
    }
    this.list[this.rear] = value;
    this.rear = (this.rear + 1) % this.size;
    return true;
  }
  deQueue() {
    if (this.isEmpty()) {
      return false;
    }
    this.font = (this.font + 1) % this.size;
    return true;
  }
  isEmpty() {
    return this.font === this.rear;
  }
  isFull() {
    return (this.rear + 1) % this.size === this.font;
  }
  toString() {
    console.log(this.list.slice(this.font, this.rear));
  }
}

测试代码

const queue = new Queue(5);
queue.enQueue(1);
queue.enQueue(3);
queue.toString();

Priority Queue(优先队列)

Queue还有个升级版本，给每个元素赋予优先级，优先级高的元素入列时将排到低优先级元素之前。区别主要是enqueue方法的实现：

function PriorityQueue() { 
 
  ... 
 
  this.enqueue = function (element) { 
    if (this.isEmpty()) { 
      collection.push(element); 
    } else { 
      var added = false; 
      for (var i = 0; i < collection.length; i++) { 
        if (element[1] < collection[i][1]) { 
          collection.splice(i, 0, element); 
          added = true; 
          break; 
        } 
      } 
      if (!added) { 
        collection.push(element); 
      } 
    } 
  } 
} 

测试代码

var pQ = new PriorityQueue(); 
 
pQ.enqueue(['gannicus', 3]); 
pQ.enqueue(['spartacus', 1]); 
pQ.enqueue(['crixus', 2]); 
pQ.enqueue(['oenomaus', 4]); 
 
pQ.print(); 

结果为：

[ 
  [ 'spartacus', 1 ], 
  [ 'crixus', 2 ], 
  [ 'gannicus', 3 ], 
  [ 'oenomaus', 4 ] 
] 

扩展阅读

• 数组实现的循环队列