Java双端队列实现技巧与代码解析

双端队列可在两端进行插入和删除操作，Java中通过实现Deque接口支持该结构，常用ArrayDeque（基于数组，访问快）和LinkedList（基于链表，增删快）实现，前者适用于元素数量固定且访问频繁的场景，后者适合频繁增删且容量变化大的场景；二者在性能上主要差异在于访问速度与内存占用，选择需根据具体需求权衡；此外，还可通过自定义数组、循环数组或第三方库实现双端队列，以满足特定性能或功能要求。

双端队列，顾名思义，就是可以在队列的两端进行插入和删除操作的数据结构。Java中java.util.Deque接口提供了双端队列的功能。实现双端队列，本质上就是实现这个接口。

解决方案

Java中，可以使用ArrayDeque或LinkedList来实现Deque接口。ArrayDeque基于数组实现，更高效，但容量有限制。LinkedList基于链表实现，容量理论上无限制，但效率稍低。

使用 ArrayDeque 实现双端队列：

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {

    public static void main(String[] args) {
        Deque deque = new ArrayDeque<>();

        // 从队头添加元素
        deque.addFirst("Element 1");
        deque.offerFirst("Element 0"); // offerFirst不会抛出异常，如果队列满了会返回false

        // 从队尾添加元素
        deque.addLast("Element 2");
        deque.offerLast("Element 3");

        System.out.println("Deque: " + deque); // 输出: Deque: [Element 0, Element 1, Element 2, Element 3]

        // 从队头移除元素
        String first = deque.removeFirst(); // 如果队列为空，会抛出NoSuchElementException
        String firstOrNull = deque.pollFirst(); // 如果队列为空，返回null

        // 从队尾移除元素
        String last = deque.removeLast(); // 如果队列为空，会抛出NoSuchElementException
        String lastOrNull = deque.pollLast(); // 如果队列为空，返回null

        System.out.println("Removed first: " + first); // 输出: Removed first: Element 0
        System.out.println("Removed last: " + last); // 输出: Removed last: Element 3
        System.out.println("Deque after removals: " + deque); // 输出: Deque after removals: [Element 1, Element 2]

        // 检查队列头部元素但不移除
        String peekFirst = deque.peekFirst();
        String getFirst = deque.getFirst();

        // 检查队列尾部元素但不移除
        String peekLast = deque.peekLast();
        String getLast = deque.getLast();

        System.out.println("Peek First: " + peekFirst); // 输出: Peek First: Element 1
        System.out.println("Peek Last: " + peekLast); // 输出: Peek Last: Element 2
    }
}

使用 LinkedList 实现双端队列：

import java.util.Deque;
import java.util.LinkedList;

public class LinkedListDequeExample {

    public static void main(String[] args) {
        Deque deque = new LinkedList<>();

        deque.addFirst("A");
        deque.addLast("B");
        deque.push("C"); // 等价于 addFirst
        deque.offer("D"); // 等价于 addLast

        System.out.println("Deque: " + deque); // 输出: Deque: [C, A, B, D]

        System.out.println("Removed first: " + deque.removeFirst()); // 输出: Removed first: C
        System.out.println("Removed last: " + deque.removeLast()); // 输出: Removed last: D
        System.out.println("Deque after removals: " + deque); // 输出: Deque after removals: [A, B]

        System.out.println("Peek first: " + deque.peekFirst()); // 输出: Peek first: A
        System.out.println("Peek last: " + deque.peekLast()); // 输出: Peek last: B

    }
}

双端队列相比普通队列的优势是什么？应用场景有哪些？

双端队列最大的优势在于灵活性。普通队列只能在一端插入，另一端删除，而双端队列两端都可以进行插入和删除。这种灵活性使得双端队列可以应用于更多场景。

应用场景：

• 回溯算法： 在回溯算法中，需要在搜索路径上进行前进和后退的操作，双端队列可以方便地实现这些操作。比如，网页浏览器的前进后退功能就可以用双端队列实现。
• 任务调度： 可以根据任务的优先级，将高优先级任务插入到队头，低优先级任务插入到队尾。
• 数据缓存： 可以使用双端队列来实现LRU（Least Recently Used）缓存。最近使用的数据放在队头，最久未使用的数据放在队尾，当缓存满时，从队尾移除数据。
• 解析器： 在某些解析器中，需要同时从头和尾处理数据。

ArrayDeque 和 LinkedList 在实现双端队列时，性能上有哪些差异？如何选择？

ArrayDeque和LinkedList在实现Deque接口时，底层数据结构不同，导致性能差异。

• ArrayDeque： 基于动态数组实现。
  • 优点： 访问元素速度快（O(1)），因为数组在内存中是连续存储的。在已知元素数量的情况下，内存占用更少。
  • 缺点： 插入和删除元素时，可能需要移动其他元素，时间复杂度为O(n)。扩容时需要复制整个数组，开销较大。
• LinkedList： 基于链表实现。
  • 优点： 插入和删除元素速度快（O(1)），只需要修改指针即可。容量理论上无限制。
  • 缺点： 访问元素速度慢（O(n)），需要从头或尾遍历链表。每个元素都需要额外的空间存储指针，内存占用较多。

如何选择：

• 如果需要频繁访问队列中的元素，且对内存占用比较敏感，选择ArrayDeque。
• 如果需要频繁插入和删除元素，且对内存占用不敏感，选择LinkedList。
• 如果事先知道队列的元素数量，且元素数量变化不大，选择ArrayDeque。
• 如果队列的元素数量变化很大，且无法预知，选择LinkedList。

举个例子，假设你需要实现一个LRU缓存，缓存大小固定，且访问频率很高，那么ArrayDeque可能更适合。如果缓存大小不固定，且插入和删除操作频繁，那么LinkedList可能更适合。

除了 ArrayDeque 和 LinkedList，还有没有其他方式实现双端队列？

理论上，任何可以支持两端插入和删除操作的数据结构都可以用来实现双端队列。

• 自定义数组实现： 可以自己实现一个基于数组的双端队列，通过维护两个指针，分别指向队头和队尾，来实现两端的插入和删除。这种方式可以更加灵活地控制内存使用和性能，但需要更多的代码实现。
• 循环数组： 使用循环数组可以更有效地利用空间，避免数组扩容带来的开销。通过取模运算来确定队头和队尾的位置。
• 使用第三方库： 一些第三方库可能提供了更高级的双端队列实现，例如并发安全的双端队列。

选择哪种方式取决于具体的应用场景和需求。如果对性能有极致的要求，可能需要自定义实现。如果只是需要简单的双端队列功能，使用ArrayDeque或LinkedList即可。