双向队列（Double-ended Queue），也称为双端队列或简称为Deque，是一种具有队列和栈性质的数据结构。它允许在队列的两端进行插入和删除操作，因此可以同时支持先进先出（FIFO）和后进先出（LIFO）的操作。

基本介绍

双向队列的特点是可以在队列的前端和后端进行元素的插入和删除。这意味着你可以在队列的头部和尾部都执行入队出队操作和头部和尾部的访问

双向队列（Double-ended Queue）具有以下特点：

1. 插入和删除操作：双向队列允许在队列的前端和后端进行插入和删除操作。这意味着你可以在队列的头部和尾部同时执行入队和出队操作，使得元素的插入和删除更加灵活和高效。
2. 先进先出（FIFO）和后进先出（LIFO）：由于双向队列同时支持队列和栈的操作，你可以根据需要选择先进先出或后进先出的插入和删除方式。你可以将它用作普通队列，按照先进先出的顺序处理元素，也可以将其用作栈，按照后进先出的顺序处理元素。
3. 随机访问：双向队列通常支持随机访问，也就是可以直接访问队列中的任意位置的元素。这意味着你可以通过索引来访问队列中特定位置的元素，而不仅仅限于头部和尾部的操作。
4. 动态扩容：双向队列通常具有动态扩容的能力。当队列满时，可以自动分配更多的内存空间来容纳更多的元素，从而避免了固定容量的限制。
5. 多种应用场景：双向队列在许多应用场景中非常有用。它可以用于实现队列、栈、滑动窗口问题、任务调度、缓存管理等，提供了一种灵活且高效的数据结构选择。

经典实现

基于双向链表的实现

对于双向队列而言，头部和尾部都可以执行入队和出队操作。换句话说，双向队列需要实现另一个对称方向的操作。为此，可以采用“双向链表”作为双向队列的底层数据结构。

/* 双向链表节点 */
class ListNode {
    int val; // 节点值
    ListNode next; // 后继节点引用
    ListNode prev; // 前驱节点引用

    ListNode(int val) {
        this.val = val;
        prev = next = null;
    }
}

/* 基于双向链表实现的双向队列 */
class LinkedListDeque {
    private ListNode front, rear; // 头节点 front ，尾节点 rear
    private int queSize = 0; // 双向队列的长度

    public LinkedListDeque() {
        front = rear = null;
    }

    /* 获取双向队列的长度 */
    public int size() {
        return queSize;
    }

    /* 判断双向队列是否为空 */
    public boolean isEmpty() {
        return size() == 0;
    }

    /* 入队操作 */
    private void push(int num, boolean isFront) {
        ListNode node = new ListNode(num);
        // 若链表为空，则令 front, rear 都指向 node
        if (isEmpty())
            front = rear = node;
        // 队首入队操作
        else if (isFront) {
            // 将 node 添加至链表头部
            front.prev = node;
            node.next = front;
            front = node; // 更新头节点
        // 队尾入队操作
        } else {
            // 将 node 添加至链表尾部
            rear.next = node;
            node.prev = rear;
            rear = node; // 更新尾节点
        }
        queSize++; // 更新队列长度
    }

    /* 队首入队 */
    public void pushFirst(int num) {
        push(num, true);
    }

    /* 队尾入队 */
    public void pushLast(int num) {
        push(num, false);
    }

    /* 出队操作 */
    private int pop(boolean isFront) {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        int val;
        // 队首出队操作
        if (isFront) {
            val = front.val; // 暂存头节点值
            // 删除头节点
            ListNode fNext = front.next;
            if (fNext != null) {
                fNext.prev = null;
                front.next = null;
            }
            front = fNext; // 更新头节点
        // 队尾出队操作
        } else {
            val = rear.val; // 暂存尾节点值
            // 删除尾节点
            ListNode rPrev = rear.prev;
            if (rPrev != null) {
                rPrev.next = null;
                rear.prev = null;
            }
            rear = rPrev; // 更新尾节点
        }
        queSize--; // 更新队列长度
        return val;
    }

    /* 队首出队 */
    public int popFirst() {
        return pop(true);
    }

    /* 队尾出队 */
    public int popLast() {
        return pop(false);
    }

    /* 访问队首元素 */
    public int peekFirst() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return front.val;
    }

    /* 访问队尾元素 */
    public int peekLast() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return rear.val;
    }

    /* 返回数组用于打印 */
    public int[] toArray() {
        ListNode node = front;
        int[] res = new int[size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}

基于数据的实现

与基于数组实现队列类似，我们也可以使用环形数组来实现双向队列

/* 基于环形数组实现的双向队列 */
class ArrayDeque {
    private int[] nums; // 用于存储双向队列元素的数组
    private int front; // 队首指针，指向队首元素
    private int queSize; // 双向队列长度

    /* 构造方法 */
    public ArrayDeque(int capacity) {
        this.nums = new int[capacity];
        front = queSize = 0;
    }

    /* 获取双向队列的容量 */
    public int capacity() {
        return nums.length;
    }

    /* 获取双向队列的长度 */
    public int size() {
        return queSize;
    }

    /* 判断双向队列是否为空 */
    public boolean isEmpty() {
        return queSize == 0;
    }

    /* 计算环形数组索引 */
    private int index(int i) {
        // 通过取余操作实现数组首尾相连
        // 当 i 越过数组尾部后，回到头部
        // 当 i 越过数组头部后，回到尾部
        return (i + capacity()) % capacity();
    }

    /* 队首入队 */
    public void pushFirst(int num) {
        if (queSize == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        // 队首指针向左移动一位
        // 通过取余操作，实现 front 越过数组头部后回到尾部
        front = index(front - 1);
        // 将 num 添加至队首
        nums[front] = num;
        queSize++;
    }

    /* 队尾入队 */
    public void pushLast(int num) {
        if (queSize == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        // 计算尾指针，指向队尾索引 + 1
        int rear = index(front + queSize);
        // 将 num 添加至队尾
        nums[rear] = num;
        queSize++;
    }

    /* 队首出队 */
    public int popFirst() {
        int num = peekFirst();
        // 队首指针向后移动一位
        front = index(front + 1);
        queSize--;
        return num;
    }

    /* 队尾出队 */
    public int popLast() {
        int num = peekLast();
        queSize--;
        return num;
    }

    /* 访问队首元素 */
    public int peekFirst() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return nums[front];
    }

    /* 访问队尾元素 */
    public int peekLast() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        // 计算尾元素索引
        int last = index(front + queSize - 1);
        return nums[last];
    }

    /* 返回数组用于打印 */
    public int[] toArray() {
        // 仅转换有效长度范围内的列表元素
        int[] res = new int[queSize];
        for (int i = 0, j = front; i < queSize; i++, j++) {
            res[i] = nums[index(j)];
        }
        return res;
    }
}

经典应用

1. 滑动窗口问题：双向队列在滑动窗口问题中非常有用。滑动窗口是一个固定大小的窗口，它在一个序列或数组上移动，并用于计算特定范围内的统计信息。通过在双向队列的前端和后端进行元素的插入和删除操作，可以高效地处理滑动窗口中的元素。
2. 缓存管理：双向队列常被用于实现缓存管理。缓存是一种存储数据的高速存储器，用于加速数据访问。当需要将新的数据放入缓存时，可以使用双向队列在队列的前端插入新的数据。当缓存已满时，可以从队列的后端删除最久未使用的数据。
3. 任务调度：在任务调度中，双向队列可用于管理待执行的任务。任务可以根据其优先级在队列的前端或后端插入和删除。这允许高优先级任务更快地得到执行，并保持任务的顺序。
4. 进程调度：在操作系统中，进程调度是将处理器分配给待执行的进程的过程。双向队列可以用于实现进程调度算法，如双端队列调度算法（Double-Ended Queue Scheduling Algorithm），其中可以根据进程的优先级和时间片来插入和删除进程。
5. 斯坦利队列（Stanley Queue）：斯坦利队列是一种基于双向队列的数据结构，用于解决深度优先搜索（DFS）中的非递归遍历问题。它可以在遍历图或树时保持访问的节点，并根据需要在队列的前端或后端插入和删除节点。
6. 双向广度优先搜索（Bidirectional Breadth-First Search）：在某些图搜索问题中，双向队列可以用于实现双向广度优先搜索算法。这种算法同时从起始节点和目标节点开始搜索，并在两个方向上进行扩展，直到它们相遇