原理： 先进先出， FIFO, first in first out。 普通队列， 环形队列。

  • 头部指针
  • 尾部指针

方法：

  • 创建/销毁
  • 清空/判空
  • 长度
  • 遍历
  • 插入（队尾）
  • 删除 （队首）

私有：

  • 指针
  • 长度
  • 容量

用途：排号机

剑指 Offer 59 - II. 队列的最大值

解决： 辅助数组
⚠️ 辅助数组与实际队列长度并非一样， 操作有区别。辅助队列 dequedeque 队首元素就是队列的最大值

  1. MaxQueue.prototype.push_back = function(value) {
  2.     this.queue.push(value);
  3.     // 辅助队列队尾<value
  4.     while (this.maxQueue[this.maxQueue.length - 1] < value) {
  5.         this.maxQueue.pop()
  6.     }
  7.     this.maxQueue.push(value)
  8. };
  10. /**
  11.  * @return {number}
  12.  */
  13. MaxQueue.prototype.pop_front = function() {
  14.     let cur = this.queue.shift()
  15.     if (cur && cur == this.maxQueue[0]) {
  16.         this.maxQueue.shift()
  17.     }
  18.     return cur || -1;
  19. };

测试数据
[1, 2]
[15, 9]

LC

1670. 设计前中后队列

题解： 双队列

优先队列

692. 前K个高频单词