队列 & 双端队列

队列（Queue）和双端队列（Deque）都是线性数据结构，但各自的特性使它们适用于不同场景。队列是一种先进先出（FIFO, First In First Out）的数据结构，而双端队列则允许在两端进行插入和删除操作，提供更大的灵活性。

一、队列（Queue）

队列是一种先进先出的线性数据结构，意味着第一个进入队列的元素最先被处理。这种特性使得队列常用于任务处理、消息传递等场景。

1. 队列的基本特性

• 先进先出：队列的第一个元素最先被移出。
• 单向访问：数据的插入操作只能在队尾（Rear）进行，数据的删除操作只能在队首（Front）进行。

2. 队列的基本操作

队列的基本操作包括：

1. Enqueue（入队）：在队尾插入一个新元素。
2. Dequeue（出队）：移除并返回队首的元素。
3. Peek：返回队首的元素但不移除它。
4. IsEmpty：检查队列是否为空。

3. 队列的实现方式

队列通常可以使用数组或链表实现。以下是两种实现方法的示例代码：

基于数组实现队列

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

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

    // 出队
    dequeue() {
        if (this.isEmpty()) {
            throw new Error("Queue Underflow");
        }
        return this.items.shift();  // 移除并返回队首元素
    }

    // 查看队首元素
    peek() {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.items[0];
    }

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

// 示例
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue());  // 输出: 1
console.log(queue.peek());     // 输出: 2

基于链表实现队列

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

class Queue {
    constructor() {
        this.front = null;  // 队首
        this.rear = null;   // 队尾
    }

    // 入队
    enqueue(value) {
        const newNode = new Node(value);
        if (this.rear) {
            this.rear.next = newNode;
        } else {
            this.front = newNode;
        }
        this.rear = newNode;
    }

    // 出队
    dequeue() {
        if (this.isEmpty()) {
            throw new Error("Queue Underflow");
        }
        const value = this.front.value;
        this.front = this.front.next;
        if (!this.front) {
            this.rear = null;
        }
        return value;
    }

    // 查看队首元素
    peek() {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.front.value;
    }

    // 检查队列是否为空
    isEmpty() {
        return this.front === null;
    }
}

// 示例
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue());  // 输出: 1
console.log(queue.peek());     // 输出: 2

4. 队列的应用场景

1. 任务调度：任务调度器会将任务依次插入队列，按顺序执行。
2. 广度优先搜索（BFS）：在 BFS 中，队列用于存储下一层的节点。
3. 消息队列：在分布式系统中，消息队列用于异步消息传递。
4. 缓冲区：在数据流处理过程中，缓冲区通常通过队列实现数据的有序处理。

二、双端队列（Deque）

双端队列（Deque, Double-Ended Queue）是一种两端都可以插入和删除的线性数据结构。与队列和栈不同，双端队列既支持先进先出（FIFO），也支持后进先出（LIFO），因此它的使用场景更为灵活。

1. 双端队列的基本特性

• 双端插入和删除：元素可以在队首或队尾插入或删除。
• 灵活的访问方式：既可以作为队列使用（两端之一插入，另一端删除），也可以作为栈使用（同一端进行插入和删除）。

2. 双端队列的基本操作

1. AddFront：在队首插入一个元素。
2. AddRear：在队尾插入一个元素。
3. RemoveFront：移除并返回队首的元素。
4. RemoveRear：移除并返回队尾的元素。
5. PeekFront：返回队首的元素但不移除它。
6. PeekRear：返回队尾的元素但不移除它。
7. IsEmpty：检查双端队列是否为空。

3. 双端队列的实现方式

双端队列可以通过双向链表或数组实现。以下是基于数组实现的示例代码：

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

    // 在队首添加元素
    addFront(element) {
        this.items.unshift(element);
    }

    // 在队尾添加元素
    addRear(element) {
        this.items.push(element);
    }

    // 从队首移除元素
    removeFront() {
        if (this.isEmpty()) {
            throw new Error("Deque Underflow");
        }
        return this.items.shift();
    }

    // 从队尾移除元素
    removeRear() {
        if (this.isEmpty()) {
            throw new Error("Deque Underflow");
        }
        return this.items.pop();
    }

    // 查看队首元素
    peekFront() {
        if (this.isEmpty()) {
            throw new Error("Deque is empty");
        }
        return this.items[0];
    }

    // 查看队尾元素
    peekRear() {
        if (this.isEmpty()) {
            throw new Error("Deque is empty");
        }
        return this.items[this.items.length - 1];
    }

    // 检查双端队列是否为空
    isEmpty() {
        return this.items.length === 0;
    }
}

// 示例
const deque = new Deque();
deque.addFront(1);
deque.addRear(2);
console.log(deque.removeFront()); // 输出: 1
console.log(deque.peekRear());    // 输出: 2

4. 双端队列的应用场景

1. 滑动窗口：在滑动窗口问题中（例如求最大/最小值），双端队列可以有效管理窗口范围内的元素。
2. 回文检查：双端队列允许从两端检查字符串是否为回文。
3. 任务调度：双端队列可以用于调度任务，既可以按照优先级顺序处理任务，也可以在任意端处理。

三、总结：队列 vs 双端队列

特性	队列	双端队列
插入位置	只能在队尾插入	可以在队首和队尾插入
删除位置	只能在队首删除	可以在队首和队尾删除
适用场景	任务调度、BFS、消息队列等	滑动窗口、回文检查、灵活任务调度
访问方式	先进先出	既可以先进先出，也可以后进先出

队列和双端队列各自有不同的用途。队列适用于需要按顺序处理的场景，而双端队列的双向操作特性使其在需要灵活访问的场景中表现出色。