02-队列

认识

队列（Queue） 是一种 线性数据结构，遵循先进先出（FIFO, First-In-First-Out） 的原则。

也就是说，队列中的元素按照它们被加入的顺序排列，先加入队列的元素先被移除，后加入队列的元素后被移除。

JavaScript中没有队列，但是可以用Array实现队列的所有功能。

JS实现

// 数组实现队列数据结构
const queue = []

// 入队
stack.push(0)
stack.push(1)
stack.push(2)

// 出队
const shiftVal = stack.shift() // shiftVal 为 0

使用场景

• 场景一：日常测核酸排队
• 场景二：JS异步中的任务队列
• 场景三：计算最近请求次数

LeetCode题目

933  最近的请求次数

基本操作

1. 入队（Enqueue）：向队列的尾部添加一个元素。
2. 出队（Dequeue）：从队列的头部移除一个元素。
3. 查看队首元素（Peek/Front）：返回队列头部的元素，但不移除它。
4. 判断队列是否为空（IsEmpty）：检查队列中是否有元素。
5. 队列的大小（Size）：返回队列中元素的数量。

应用场景

队列广泛应用于需要按顺序处理任务的场景，以下是一些典型的应用：

• 任务调度：操作系统中的任务调度常常使用队列来管理进程或线程，按照先到先处理的原则执行任务。
• 消息队列：在分布式系统或异步通信中，消息队列用于存储和传递消息，保证消息按顺序被处理。
• 打印任务：打印机的打印任务通常是排队的，先发送的任务先打印。
• 广度优先搜索（BFS）：在图的广度优先遍历中，队列用来管理访问节点的顺序。

实现

队列可以用数组、链表或者其他数据结构来实现。常见的两种实现方式是：

1. 数组实现：队列可以用一个数组来存储元素，使用两个指针（头指针和尾指针）来表示队列的两端。
   • 优点：实现简单。
   • 缺点：在数组中间删除元素可能会导致大量元素移动，效率较低。
2. 链表实现：队列也可以使用链表来实现，通过链表的头部进行出队操作，通过尾部进行入队操作。
   • 优点：无固定大小限制，可以高效地进行插入和删除。
   • 缺点：需要额外的内存来存储指针。

操作

class Queue {
    constructor() {
        this.items = [];
    }

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

    // 出队
    dequeue() {
        if (this.isEmpty()) {
            return 'Queue is empty';
        }
        return this.items.shift(); // 从头部移除元素
    }

    // 查看队首元素
    front() {
        if (this.isEmpty()) {
            return 'Queue is empty';
        }
        return this.items[0];
    }

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

    // 返回队列大小
    size() {
        return this.items.length;
    }
}

// 测试队列操作
let queue = new Queue();
queue.enqueue(1);  // 入队 1
queue.enqueue(2);  // 入队 2
queue.enqueue(3);  // 入队 3

console.log(queue.dequeue());  // 出队 1
console.log(queue.front());    // 队首元素 2
console.log(queue.size());     // 队列大小 2
console.log(queue.isEmpty()); // 是否为空 false

队列的变种

• 双端队列（Deque）：双端队列允许从队列的两端进行插入和删除操作，因此它既可以作为队列使用，也可以作为栈使用。
• 优先级队列（Priority Queue）：优先级队列中的元素有优先级，出队时不是按顺序（FIFO）执行，而是根据元素的优先级进行处理，优先级高的元素先出队。