队列汇总

队列分类

单向队列 Queue

介绍

  1. Queue 接口代表了一个先进先出（First-In-First-Out）的队列。它继承自 Collection 接口，并提供了一系列用于插入、删除和检查元素的方法，比如 offer()、poll() 和 peek()。常见的实现类有 LinkedList 和 PriorityQueue。

常用方法

  1. 示例：

    1
    2
    3
    4
    5
    // 使用 Queue 接口
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(1);         // 在队列尾部插入元素
    int firstElement = queue.poll();     // 从队列头部弹出并获取元素
    int peekedElement = queue.peek();    // 查看队列头部元素，但不弹出

  2. 队列（Queue）常用方法：

    • offer(E e)：将元素插入到队列的尾部。
    • poll()：从队列的头部弹出并返回元素，如果队列为空则返回 null。
    • peek()：查看队列头部的元素，但不对队列做修改。

双端队列 Dequeue

介绍

  1. Deque 接口继承自 Queue 接口，代表了一个双端队列（Double Ended Queue），它既可以从头部插入和删除元素，也可以从尾部插入和删除元素。除了继承自 Queue 的方法外，Deque 还提供了一些额外的方法，比如 addFirst()、removeFirst()、addLast() 和 removeLast()。常见的实现类有 ArrayDeque 和 LinkedList。

常用方法

  1. 示例：

    1
    2
    3
    4
    5
    6
    // 使用 Deque 接口
    Deque<Integer> deque = new ArrayDeque<>();
    deque.addFirst(1);              // 在队列头部插入元素
    deque.removeLast();             // 从队列尾部删除元素
    int firstElement = deque.getFirst();    // 获取队列头部元素
    int lastElement = deque.getLast();      // 获取队列尾部元素

  2. 双端队列（Deque）常用方法：

    • addFirst(E e)：将元素插入到双端队列的头部。
    • addLast(E e)：将元素插入到双端队列的尾部。
    • removeFirst()：从双端队列的头部删除并返回元素，如果队列为空则抛出异常。
    • removeLast()：从双端队列的尾部删除并返回元素，如果队列为空则抛出异常。
    • getFirst()：获取双端队列头部的元素，如果队列为空则抛出异常。
    • getLast()：获取双端队列尾部的元素，如果队列为空则抛出异常。

初始化

  1. 使用 LinkedList 类初始化：

    1
    2
    Queue<Integer> queue = new LinkedList<>();  // 初始化一个先进先出的队列
    Deque<Integer> deque = new LinkedList<>();  // 初始化一个双端队列

  2. 使用 ArrayDeque 类初始化：

    1
    2
    Queue<Integer> queue = new ArrayDeque<>();  // 初始化一个先进先出的队列
    Deque<Integer> deque = new ArrayDeque<>();  // 初始化一个双端队列

  3. 如何选择

    选择使用 LinkedList 或 ArrayDeque 的具体实现类取决于你的需求和性能要求。下面是一些常见的场景和性能差异的说明：

    1. 在 Java 中，LinkedList 和 ArrayDeque 都可以在队列的首部和尾部进行高效的插入和删除操作，时间复杂度接近 O(1)。ArrayDeque 是一个由数组实现的双端队列，而 LinkedList 是一个双向链表实现的双端队列。

      因此，在需要频繁地在队列的两端进行插入或删除操作时，两者的性能差别不大，可以根据个人喜好和代码可读性来选择。

      对于按索引访问和操作队列中的元素，LinkedList 的确支持通过索引访问，但是时间复杂度为 O(n)，因为它需要从头或尾部开始遍历到目标位置。而 ArrayDeque 并不支持直接按索引访问，所以在需要频繁按索引访问的情况下，LinkedList 更适合。

      总结来说：

      • 如果需要频繁地在队列的两端进行插入或删除操作，并且对性能要求较高，两者都可选。
      • 如果需要按索引访问和操作队列中的元素，或者需要频繁地进行随机访问，LinkedList 更适合。

    2. 需求：

      • 如果需要频繁地在队列的两端进行插入或删除操作（即首部和尾部），同时希望操作的时间复杂度接近 O(1)，则可以选择 ArrayDeque。ArrayDeque 在两端操作上具有较好的性能。
      • 如果需要按索引访问和操作队列中的元素，例如获取第 n 个元素，或者需要随机访问队列中的元素，那么 LinkedList 可能更合适。LinkedList 支持通过索引访问，但是时间复杂度为 O(n)，因为它需要从头或尾部开始遍历。

    3. 性能差别：

      • ArrayDeque 在大多数操作上具有更好的性能，因为它使用了基于数组的数据结构。它具有固定的容量大小，可以在数组中快速进行插入和删除操作，时间复杂度接近 O(1)。
      • LinkedList 使用了双向链表的数据结构，可以在任意位置进行插入和删除操作，但是访问某个位置的元素需要从头或尾部开始遍历，时间复杂度为 O(n)。

    总结来说，如果你对队列的操作主要集中在首尾两端，并且对性能有较高要求，建议选择 ArrayDeque。而如果你需要在队列中进行频繁的索引访问或操作，并且对插入和删除操作的性能要求不高，可以选择 LinkedList。

    实际选择时，还应考虑其他因素，如代码的可读性、维护性以及具体应用场景中的需求。

其他

  1. Queue 和 Deque 是 Java 中用于表示队列的接口。
  2. 除了上述常用方法外，这些接口还继承了其他接口，如 Collection、Iterable 和 Iterator，因此也可以使用与集合相关的方法，如 size()、isEmpty()、iterator() 等。
  3. 需要注意的是，Queue 和 Deque 是接口，不能直接实例化。你可以使用它们的实现类（如 LinkedList、ArrayDeque 或 PriorityQueue）来创建具体的队列对象。具体使用哪种实现类取决于你的需求和性能要求。