什么是队列

队列

队列（Queue）是一种数据结构，用于存储一组元素，并且只允许在一端进行添加操作（入队），在另一端进行移除操作（出队）。这种操作方式被称为“先进先出”（FIFO, First In First Out）。这意味着最早添加的元素会最先被移除。队列在计算机科学和编程中有着广泛的应用，例如在任务调度、广度优先搜索、缓冲区管理等场景中。

队列的基本操作

队列主要支持以下几种基本操作：

• 入队（Enqueue）：将一个元素添加到队列的尾部。
• 出队（Dequeue）：移除并返回队列头部的元素。如果队列为空，则操作可能会失败或抛出异常。
• 查看队头元素（Peek 或 Front）：返回队列头部的元素，但不移除它。
• 检查队列是否为空（IsEmpty）：判断队列中是否还有元素。
• 获取队列的大小（Size）：返回队列中元素的个数。

队列的实现

队列可以通过多种方式实现，最常见的是使用数组或链表。

使用数组实现队列

节点类 首先，我们需要一个节点类来表示链表中的每个节点。每个节点包含一个数据部分和一个指向下一个节点的指针。

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

队列类 接下来，我们需要实现队列类。这个类将包含以下方法：

• constructor：初始化队列，设置队头和队尾指针为 null 和元素计数为 0。
• enqueue：将元素加入队列尾部。
• dequeue：从队列头部移除元素。
• peek：查看队头元素，但不移除。
• isEmpty：检查队列是否为空。
• size：获取队列中的元素个数。

class Queue {
    constructor() {
        this.front = null;
        this.rear = null;
        this.count = 0;
    }

    enqueue(item) {
        const newNode = new Node(item);
        if (this.rear) {
            this.rear.next = newNode;
        }
        this.rear = newNode;
        if (!this.front) {
            this.front = newNode;
        }
        this.count += 1;
    }

    dequeue() {
        if (!this.isEmpty()) {
            const item = this.front.data;
            this.front = this.front.next;
            if (!this.front) {
                this.rear = null;
            }
            this.count -= 1;
            return item;
        } else {
            throw new Error("dequeue from empty queue");
        }
    }

    peek() {
        if (!this.isEmpty()) {
            return this.front.data;
        } else {
            throw new Error("peek from empty queue");
        }
    }

    isEmpty() {
        return this.front === null;
    }

    size() {
        return this.count;
    }
}

示例用法

const queue = new Queue();

// 入队
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(`队头元素: ${queue.peek()}`);  // 输出: 队头元素: 1
console.log(`队列大小: ${queue.size()}`);  // 输出: 队列大小: 3

// 出队
console.log(`出队元素: ${queue.dequeue()}`);  // 输出: 出队元素: 1
console.log(`队头元素: ${queue.peek()}`);  // 输出: 队头元素: 2
console.log(`队列大小: ${queue.size()}`);  // 输出: 队列大小: 2

// 检查是否为空
console.log(`队列是否为空: ${queue.isEmpty()}`);  // 输出: 队列是否为空: false

// 继续出队
console.log(`出队元素: ${queue.dequeue()}`);  // 输出: 出队元素: 2
console.log(`出队元素: ${queue.dequeue()}`);  // 输出: 出队元素: 3

// 检查是否为空
console.log(`队列是否为空: ${queue.isEmpty()}`);  // 输出: 队列是否为空: true

详细说明

Node 类：

• data 属性存储节点的数据。
• next 属性指向下一个节点。

Queue 类：

• constructor 方法初始化队列，front 和 rear 属性分别指向队列的头部和尾部，count 属性记录队列中元素的个数。
• enqueue 方法创建一个新节点，将其添加到队列的尾部，并更新 rear 和 count。如果队列为空，还需要更新 front。
• dequeue 方法移除并返回队列头部节点的数据，更新 front 和 count，如果队列为空则抛出异常。如果 front 变为 null，还需要更新 rear 为 null。
• peek 方法返回队列头部节点的数据，但不移除节点，如果队列为空则抛出异常。
• isEmpty 方法检查 front 是否为 null，以确定队列是否为空。
• size 方法返回 count 的值，即队列中元素的个数。

通过上述实现，你可以使用链表来管理队列中的元素，从而实现高效的队列操作。