队列

队列（Queue）是一种常见的数据结构，它遵循先进先出（FIFO，First-In-First-Out）的原则，即最先进入队列的元素将最先被移出。

队列可以看作是一种线性的数据结构，类似于排队购物或排队等候的过程。

常规队列

队列有两个主要操作：

入队（enqueue）：将元素添加到队列的末尾。
出队（dequeue）：从队列的前端移除元素。

队列的实现可以基于不同的数据结构，常见的有数组和链表两种实现方式。

在数组实现中，通常使用两个指针来标识队列的头部和尾部，并且需要处理队列大小超出数组容量的情况。

而在链表实现中，每个节点包含一个元素和一个指向下一个节点的指针，入队和出队操作只需要更新链表的头部和尾部指针即可。

队列常见的应用包括

任务调度：操作系统中的任务调度算法通常使用队列来管理待执行的任务。
广度优先搜索：图算法中广度优先搜索（BFS）通常使用队列来管理待访问的顶点。
消息传递：在并发编程中，队列常用于线程间的通信，以传递消息或任务。
缓冲：队列用作缓冲区，帮助平衡生产者和消费者之间的速度差异。

在JavaScript中，数组本身内置了队列相关的功能

const queue = []
queue.push(1)
queue.push(2)
queue.push(3)

queue.shift() // 1
queue.shift() // 2

问题：约瑟夫环

1823. 找出游戏的获胜者

使用队列来模拟约瑟夫环游戏是一个比较常见的做法，将数到的人放在队列末尾，然后将队首的元素弹出，这样可以避免使用数组模拟时出现空位的情况

var findTheWinner = function (n, k) {
    const queue = [];
    for (let i = 1; i <= n; i++) {
        queue.push(i);
    }
    while (queue.length > 1) {
        for (let i = 1; i < k; i++) {
            queue.push(queue.shift());
        }
        queue.shift();
    }
    return queue[0];
};

优先队列

优先队列（Priority Queue）是一种特殊类型的队列，它的每个元素都关联有一个优先级。

在普通队列中，元素按照进入队列的先后顺序移出。

在优先队列中，元素按照优先级的顺序排列，优先级高的元素先被移出队列。

优先队列的应用十分广泛，例如：

任务调度：根据任务的优先级执行任务。
路由算法：选择网络中的最佳路径。
操作系统调度：根据进程的优先级进行调度。

不同的实现方式和数据结构可以用来支持优先队列，每种实现都有其优势和适用场景。

可以使用堆来实现优先队列，在最大堆中，优先级最高的元素位于堆的根节点；在最小堆中，优先级最低的元素位于堆的根节点。这种实现方式具有较好的性能，插入和删除操作的时间复杂度为 O(log n)，其中 n 是优先队列中的元素数量。

letcode内置了priority-queue，因此可以直接使用PriorityQueue类，但是参考这个issue，大概是由于内置库的版本问题，某些api支持不太好。

单调队列

单调队列（Monotonic Queue）是一种特殊类型的队列，其维护的元素具有单调性，即递增或递减。它通常用于解决一些与滑动窗口相关的问题，其中需要在一个移动窗口中找到特定条件的最大或最小值。

单调队列的主要特点是，队列中的元素保持一定的顺序，以便快速找到当前窗口中的最大或最小值。在实际应用中，单调队列经常用于解决一些数组或序列上的问题，如在一个数组中找到每个窗口的最大值或最小值。

实现单调队列时，通常会保持队列中的元素按照单调递增或递减的顺序排列。在进行入队和出队操作时，维护这一单调性，以确保队列中的元素始终保持有序。

单调递增序列是指序列中的元素从左到右依次递增的情况，也就是说，序列中的每个元素都比它前面的元素大
单调递减序列是指序列中的元素从左到右依次递减的情况，也就是说，序列中的每个元素都比它前面的元素小

下面是一个单调递减队列的实现

class MonotonicQueue {
  constructor() {
    this.queue = [];
  }

  // 入队操作，保持队列单调递减
  push(val) {
    // 修改此处的 val 判断，就可以将队列修改为单调递增队列
    while (this.queue.length > 0 && this.queue[this.queue.length - 1] < val) {
      this.queue.pop();
    }
    this.queue.push(val);
    console.log(this.queue)
  }

  // 出队操作
  pop() {
    if (this.queue.length > 0) {
      this.queue.shift();
    }
  }

  // 获取队首元素
  front() {
    if (this.queue.length > 0) {
      return this.queue[0];
    }
    return null;
  }

  // 获取队尾元素
  back() {
    if (this.queue.length > 0) {
      return this.queue[this.queue.length - 1];
    }
    return null;
  }

  // 获取队列大小
  size() {
    return this.queue.length;
  }
}

// 示例用法
const monoQueue = new MonotonicQueue();
monoQueue.push(3);
monoQueue.push(1);
monoQueue.push(5);
monoQueue.push(2);
console.log("Front element:", monoQueue.front()); // 3
console.log("Back element:", monoQueue.back()); // 5
console.log("Queue size:", monoQueue.size()); // 4

monoQueue.pop();
console.log("Queue size after popping:", monoQueue.size()); // 3

循环队列

循环队列（Circular Queue）：循环队列是一种具有固定大小的队列，其底层数据结构通常是数组。

与普通队列不同的是，循环队列允许在队列的头部和尾部之间循环利用数组空间，当队列的尾部元素达到数组的末尾时，可以将新元素插入到数组的开头，以实现循环存储。

循环队列常用于实现具有循环缓冲区需求的系统，例如计算机网络中的数据传输、操作系统中的缓冲区管理等。

双端队列

双端队列（Deque，Double-ended Queue）：双端队列是一种允许从队列的两端插入和删除元素的队列，可以在队列的头部和尾部进行插入和删除操作。

双端队列的底层数据结构通常是链表或数组，它可以支持更多种类的操作，例如在队列的头部和尾部插入或删除元素、获取队列的头部和尾部元素等。

双端队列常用于具有双向数据流需求的系统，例如实现栈、队列、调度器等。

队列 ​

常规队列 ​

问题：约瑟夫环 ​

优先队列 ​

单调队列 ​

循环队列 ​

双端队列 ​

队列