队列.md

队列

普通队列

队列是一种受限的线性表，先进先出。它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

使用数组实现队列

function Queue() {
  this.items = [];
  // 将元素添加到队列中
  Queue.prototype.enqueue = function(element) {
    this.items.push(element);
  };

  // 从队列中删除元素
  Queue.prototype.dequeue = function() {
    return this.items.shift();
  };

  // 查看队列第一个的元素
  Queue.prototype.front = function() {
    return this.items[0];
  };

  // 查看队列是否为空
  Queue.prototype.isEmpty = function() {
    return this.items.length === 0;
  };

  // 查看队列中元素的个数
  Queue.prototype.size = function() {
    return this.items.length;
  };

  // toString方法
  Queue.prototype.toString = function() {
    var resultStr = "";
    for (let i = 0; i < this.items.length; i++) {
      resultStr += i;
    }
    return resultStr;
  };
}

优先级队列

队列中出了数据，还包含其数据的优先级。（这里的时间复杂度在入队/出队的时候对应是O(1)或O(n)。而使用堆实现，则其入队和出队时间复杂度都为O(logn)）

function PriorityQueue() {
  this.items = [];

  // 内部类,数据项实例（数据项 = 数据 + 优先级）
  function PriorityElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }

  PriorityQueue.prototype.enqueue = function(element, priority) {
    var tempElement = new PriorityElement(element, priority);

    if (!this.items.length) {
      this.items.push(tempElement);
    } else {
      for (let i = 0; i < this.items.length; i++) {
        if (tempElement.priority > this.items[i].priority) {
          this.items.splice(i, 0, tempElement); // 指定位置i处添加数据项
          return;
        }
      }
      this.items.push(tempElement); // 当前数据项优先级最低，直接末尾插入
    }
  };
}

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue(1, 1);
priorityQueue.enqueue(3, 3);
priorityQueue.enqueue(2, 2);
console.log(priorityQueue);