队列的概念和用途

队列的概念和用途

• 队列是一种特殊的列表。

• 队列可以想像成银行前排队的人群，排在最前面的人第一个办理业务，新来的人在后面排队，直到轮到他为止。

• 队列被用在很多地方，比如打印任务池，提交操作系统执行的一系列流程。

队列的一些关键点

• 队列只能在队尾插入元素，在队首删除元素。

• 队列是一种先进先出（FIFO，First-In-First-Out）的数据结构。

• 插入新元素称作入队，删除元素称作出队。

注意

有一些特殊情况，在删除元素时不必遵守先进先出的约定，比如急诊。这种场景我们需要使用优先队列这种数据结构来模拟。

队列的代码实现

function Queue() {
  this.dataStore = [];
  this.enqueue = enqueue; // 入队
  this.dequeue = dequeue; // 出队
  this.head = head; // 获取队首元素
  this.tail = tail; // 获取队尾元素
  this.length = length; // 获取队列长度
  this.isEmpty = isEmpty; // 判断队列是否为空
  this.clear = clear; // 清空队列
  this.toString = toString; // 显示队列中的所有元素
}

// 入队
function enqueue(element) {
  this.dataStore.push(element);
}

// 出队
function dequeue() {
  return this.dataStore.shift();
}

// 获取队首元素
function head() {
  return this.dataStore[0];
}

// 获取队尾元素
function tail() {
  return this.dataStore[this.dataStore.length - 1];
}

// 获取队列长度
function length() {
  return this.dataStore.length;
}

// 判断队列是否为空
function isEmpty() {
  return this.dataStore.length === 0;
}

// 清空队列
function clear() {
  this.dataStore = [];
}

// 显示队列中的所有元素
function toString() {
  var str = "";
  for (var i = 0; i < this.dataStore.length; i++) {
    str += this.dataStore[i] + "\n";
  }
  return str;
}

var queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.toString()); // 1 2
queue.dequeue();
console.log(queue.toString()); // 2

用两个队列实现栈

题目地址 (opens new window)

function QueueStack() {
  var queue1 = new Queue();
  var queue2 = new Queue();
  var data_queue = new Queue(); // 存放数据的队列
  var empty_queue = new Queue(); // 空队列

  // 初始化队列，用来改变 data_queue 和 empty_queue 的指向
  // 让 data_queue 始终指向有数据的队列，empty_queue 始终指向空队列
  var init_queue = function() {
    if (queue1.isEmpty() && queue2.isEmpty()) {
      data_queue = queue1;
      empty_queue = queue2;
    } else if (queue1.isEmpty()) {
      data_queue = queue2;
      empty_queue = queue1;
    } else {
      data_queue = queue1;
      empty_queue = queue2;
    }
  };

  // 入栈
  this.push = function(item) {
    init_queue();
    data_queue.enqueue(item);
  };

  // 栈顶元素
  this.top = function() {
    init_queue();
    return data_queue.tail();
  };

  // 出栈
  this.pop = function() {
    init_queue();
    while (data_queue.length() > 1) {
      empty_queue.enqueue(data_queue.dequeue());
    }
    return data_queue.dequeue();
  };

  // 栈是否为空
  this.empty = function() {
    return data_queue.isEmpty();
  };
}
var qStack = new QueueStack();
qStack.push(1);
console.log(qStack.top()); // 1
qStack.push(2);
console.log(qStack.top()); // 2
qStack.push(3);
console.log(qStack.top()); // 3
console.log(qStack.pop()); // 3
console.log(qStack.pop()); // 2
console.log(qStack.top()); // 1
console.log(qStack.empty()); // false
console.log(qStack.pop()); // 1
console.log(qStack.empty()); // true

最近的请求次数 ✅

题目地址 (opens new window)

// 时间和空间复杂度都是 O(n)
var RecentCounter = function() {
  this.queue = [];
};
RecentCounter.prototype.ping = function(t) {
  this.queue.push(t);
  while (this.queue[0] < t - 3000) {
    this.queue.shift();
  }
  return this.queue.length;
};

约瑟夫环

function del_ring(arr_list) {
  var queue = new Queue();
  // 将数组里的元素放入队列
  for (var i = 0; i < arr_list.length; i++) {
    queue.enqueue(arr_list[i]);
  }
  var index = 0;
  while (queue.length() !== 1) {
    // 弹出一个元素，判断是否需要删除
    var item = queue.dequeue();
    index += 1;
    // 每隔两个就要删除掉⼀一个，那么不不是被删除的元素就放回到队列列尾部
    if (index % 3 !== 0) {
      queue.enqueue(item);
    }
  }
  return queue.head();
}
var arr_list = [];
for (var i = 0; i < 100; i++) {
  arr_list.push(i);
}
console.log(del_ring(arr_list));

斐波那契数列

function fibonacci(n) {
  queue = new Queue();
  var index = 0;
  // 先放入斐波那契序列的前两个数
  queue.enqueue(1);
  queue.enqueue(1);
  while (index < n - 2) {
    // 出一个队列元素
    var del_item = queue.dequeue();
    // 取队列头部元素
    var head_item = queue.head();
    var next_item = del_item + head_item;
    // 将计算结果放入队列
    queue.enqueue(next_item);
    index += 1;
  }
  return queue.tail();
}
console.log(fibonacci(8)); // 21

循环队列，实现击鼓传花

function drumming(names, number) {
  var queue = new Queue();
  for (var i = 0; i < names.length; i++) {
    queue.enqueue(names[i]);
  }
  while (queue.length() > 1) {
    for (var i = 0; i < number - 1; i++) {
      queue.enqueue(queue.dequeue());
    }
    var dieout = queue.dequeue();
    console.log("此轮被淘汰的玩家是：" + dieout);
  }
  console.log("游戏的最终赢家是：" + queue.dequeue());
}
// 玩家列表
var names = ["a", "b", "c", "d", "e", "f"];
// 游戏规则：从一名玩家开始传花，当传到第3次的时候，花在谁手里，谁就被淘汰，直到最后只剩一名玩家。
var number = 3;
drumming(names, number);

实现优先队列

// 优先队列：出队的时候跟普通队列一样，主要是入队的时候比较麻烦，要考虑到优先级的问题
function PriorityQueue() {
  var items = [];

  // 辅助类
  var QueueItem = function(item, priority) {
    this.item = item; // 元素
    this.priority = priority; // 优先级
  };

  // 入队
  this.enqueue = function(item, priority) {
    var queueItem = new QueueItem(item, priority);
    var isAdd = false; // 判断是否插入成功
    for (var i = 0; i < items.length; i++) {
      if (queueItem.priority > items[i].priority) {
        // 遍历元素比较优先级
        items.splice(i, 0, queueItem); // 重点！从索引为 i 的位置开始切，切 0 个，并替换成 queueItem。巧妙地使用 splice 这个函数实现了元素的插入
        isAdd = true;
        break;
      }
    }
    if (!isAdd) {
      // 貌似有点懂了
      items.push(queueItem);
    }
  };

  this.getItems = function() {
    return items;
  };
}
var pq = new PriorityQueue();
pq.enqueue("小红", 12);
pq.enqueue("小明", 10);
pq.enqueue("小黑", 11);
console.log(pq.getItems());

优先队列的特点

正常入队，按照优先级出队。

优先队列不再遵循先入先出（FIFO）的原则，而是分为两种情况。

• 最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队。

• 最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队。

要实现以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高。

优先队列的实现

优先队列的实现一般有两种机制：堆和二叉搜索树。

回顾一下二叉堆的特性。

• 最大堆的堆顶是整个堆中的最大元素。

• 最小堆的堆顶是整个堆中的最小元素。

因此，可以用最大堆来实现最大优先队列，这样的话，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

优先队列的时间复杂度

由于二叉堆节点 “上浮” 和 “下沉” 的时间复杂度都是 O(logn)，所以优先队列入队和出队的时间复杂度也是 O(logn)。

// 用最大堆来实现最大优先队列
function PriorityQueue() {
  this.array = []; // 存储队列元素
  this.enqueue = enqueue; // 入队
  this.dequeue = dequeue; // 出队
  this.upAdjust = upAdjust; // 堆“上浮”操作
  this.downAdjust = downAdjust; // 堆“下沉”操作
}

/*
 * 入队
 * @param key 入队元素
 */
function enqueue(key) {
  this.array.push(key);
  this.upAdjust();
}

/*
 * 出队
 */
function dequeue() {
  // 获取堆顶元素
  const head = this.array[0];
  // 让最后一个元素移动到堆顶
  this.array[0] = this.array[this.array.length - 1];
  this.downAdjust();
  return head;
}

/*
 * “上浮”调整
 */
function upAdjust() {
  let childIndex = this.array.length - 1;
  let parentIndex = Math.floor((childIndex - 1) / 2);
  // temp 保存插入的叶子节点值，用于最后的赋值
  const temp = this.array[childIndex];
  while (childIndex > 0 && temp > this.array[parentIndex]) {
    // 无须真正交换，单向赋值即可
    this.array[childIndex] = this.array[parentIndex];
    childIndex = parentIndex;
    parentIndex = Math.floor(parentIndex / 2);
  }
  this.array[childIndex] = temp;
}

/*
 * “下沉”调整
 */
function downAdjust() {
  // temp 保存父节点的值，用于最后的赋值
  let parentIndex = 0;
  const temp = this.array[parentIndex];
  let childIndex = 1;

  while (childIndex < this.array.length - 1) {
    // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
    if (
      childIndex + 1 < this.array.length - 1 &&
      this.array[childIndex + 1] > this.array[childIndex]
    ) {
      childIndex++;
    }
    // 如果父节点大于任何一个孩子的值，直接跳出
    if (temp >= this.array[childIndex]) break;
    // 无须真正交换，单向赋值即可
    this.array[parentIndex] = this.array[childIndex];
    parentIndex = childIndex;
    childIndex = 2 * childIndex + 1;
  }
  this.array[parentIndex] = temp;
}

const priorityQueue = new PriorityQueue();
priorityQueue.enqueue(3);
priorityQueue.enqueue(5);
priorityQueue.enqueue(10);
priorityQueue.enqueue(2);
priorityQueue.enqueue(7);
console.log(priorityQueue.array);
console.log("出队元素：" + priorityQueue.dequeue()); // 出队元素：10
console.log("出队元素：" + priorityQueue.dequeue()); // 出队元素：7

数据流中的第 K 大元素

题目地址 (opens new window)

方法一：将现有数据流中的元素从大到小进行排序，每次取到的第 K 个元素就是数据流中的第 K 大元素。这种方法的时间复杂度为：O(nlogn)。

方法二：可以维护一个最小堆（最小优先队列），并且堆的大小等于 K，每次有新的数据进来时，都跟堆顶元素进行比较。如果小于堆顶元素，就不用管；如果大于堆顶元素，就将现有的堆顶元素干掉，新数据加进堆中，并调整堆中元素的顺序，保证堆顶元素永远是最小的。这种方法初始化的时间复杂度为：O(nlogk) ，单次插入的时间复杂度为：O(logk)，相比方法一效率提高很多。

滑动窗口最大值

题目地址 (opens new window)

方法一：维护一个最大堆（最大优先队列）。时间复杂度为：O(nlogn)。

方法二：使用具有单调性的双端队列（单调队列）。时间复杂度为：O(n)。

var maxSlidingWindow = function(nums, k) {
  const n = nums.length;
  const queue = []; // 存放单调队列的下标，对应 nums 中的元素是严格单调递减的
  for (let i = 0; i < k; i++) {
    // 新加入的元素大于等于队尾元素时，就可以弹出队尾元素，直到新加入元素小于队尾元素或者队列为空。这样就能保证队首元素对应的 nums 中的值是最大的
    while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
      queue.pop();
    }
    queue.push(i);
  }
  const res = [nums[queue[0]]];
  for (let i = k; i < n; i++) {
    while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
      queue.pop();
    }
    queue.push(i);
    // 如果队首元素不在滑动窗口中，也应该去掉
    while (queue[0] <= i - k) {
      queue.shift();
    }
    res.push(nums[queue[0]]);
  }
  return res;
};