双端队列（Deque）的基本操作、实现与应用场景 | 数据结构指南

双端队列（Double-ended Queue，简称Deque）是一种具有队列和栈的性质的数据结构。它允许在队列的两端（前端和后端）进行插入和删除操作。这种灵活性使得双端队列在很多场景下非常有用，例如在实现滑动窗口算法、缓存机制（如LRU缓存）等。

双端队列的基本操作

1. 插入操作：

   • addFront(element)：在队列的前端插入一个元素。
   • addRear(element)：在队列的后端插入一个元素。

2. 删除操作：

   • removeFront()：删除并返回队列前端的元素。
   • removeRear()：删除并返回队列后端的元素。

3. 查看操作：

   • peekFront()：返回队列前端的元素，但不删除它。
   • peekRear()：返回队列后端的元素，但不删除它。

4. 其他操作：

   • isEmpty()：检查队列是否为空。
   • size()：返回队列中元素的数量。

双端队列的实现

双端队列可以通过多种方式实现，常见的有：

1. 数组实现：使用数组来存储元素，通过维护两个指针（front和rear）来管理队列的两端。
2. 链表实现：使用双向链表来存储元素，这样可以方便地在两端进行插入和删除操作。

示例代码（JavaScript）

以下是一个简单的双端队列的JavaScript实现：

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

    // 在前端插入元素
    addFront(element) {
        this.items.unshift(element);
    }

    // 在后端插入元素
    addRear(element) {
        this.items.push(element);
    }

    // 删除前端元素
    removeFront() {
        if (this.isEmpty()) {
            return "Deque is empty";
        }
        return this.items.shift();
    }

    // 删除后端元素
    removeRear() {
        if (this.isEmpty()) {
            return "Deque is empty";
        }
        return this.items.pop();
    }

    // 查看前端元素
    peekFront() {
        if (this.isEmpty()) {
            return "Deque is empty";
        }
        return this.items[0];
    }

    // 查看后端元素
    peekRear() {
        if (this.isEmpty()) {
            return "Deque is empty";
        }
        return this.items[this.items.length - 1];
    }

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

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

    // 打印队列内容
    print() {
        console.log(this.items.toString());
    }
}

// 使用示例
const deque = new Deque();
deque.addFront(10);
deque.addRear(20);
deque.addFront(30);
deque.print(); // 输出: 30,10,20
console.log(deque.removeFront()); // 输出: 30
console.log(deque.removeRear()); // 输出: 20
deque.print(); // 输出: 10

应用场景

1. 滑动窗口算法：在解决一些数组或字符串相关的问题时，双端队列可以用来维护一个滑动窗口，从而高效地找到窗口中的最大值或最小值。
2. 缓存机制：在实现LRU（Least Recently Used）缓存时，双端队列可以用来维护缓存项的访问顺序。
3. 任务调度：在某些任务调度算法中，双端队列可以用来管理待执行的任务，允许从队列的两端添加或移除任务。

双端队列的灵活性和高效性使其在前端开发中也有广泛的应用，尤其是在处理复杂的数据流和任务调度时。